We study how to schedule data sources in a wireless time-sensitive information system with multiple heterogeneous and unreliable channels to minimize the total expected Age-of-Information (AoI). Although one could formulate this problem as a discrete-time Markov Decision Process (MDP), such an approach suffers from the curse of dimensionality and lack of insights. For single-channel systems, prior studies have developed lower-complexity solutions based on the Whittle index. However, Whittle index has not been studied for systems with multiple heterogeneous channels, mainly because indexability is not well defined when there are multiple dual cost values, one for each channel. To overcome this difficulty, we introduce new notions of partial indexability and partial index, which are defined with respect to one channel’s cost, given all other channels’ costs. We then combine the ideas of partial indices and max-weight matching to develop a Sum Weighted Index Matching (SWIM) policy, which iteratively updates the dual costs and partial indices. The proposed policy is shown to be asymptotically optimal in minimizing the total expected AoI, under a technical condition on a global attractor property. We also propose an interpolation-based algorithm to quickly compute (approximate) partial indices in real time. Extensive performance simulations demonstrate that the proposed policy offers significant gains over conventional approaches by achieving a near-optimal AoI. Further, the notion of partial index is of independent interest and could be useful for other problems with multiple heterogeneous resources.

At internet scale companies like ByteDance, data is generated and consumed at enormously high speed by many different applications. Achieving low latency on such big data jobs is an important problem. However, the naive approach of aggregating all the data required by a job to a single location is not always feasible in a geo-distributed environment. Similarly, existing approaches in geo-distributed job scheduling often try to minimize WAN usage, which may come at the cost of latency. Another crucial element to ensure low latency is resource load balancing among DCs, which enables flexibility in job scheduling and avoids resource bottlenecks. Therefore, to minimize latency, optimizing job completion time (JCT) while maintaining resource utilization balance is important. To this end, we propose ResLake , a global scheduling platform for data-intensive workloads. ResLake aims to reduce JCT of geo-distributed applications while balancing the compute (CPU/Memory) and storage (Disk) usages across DCs and efficiently using WAN interconnections. We have deployed ResLake in ByteDance's production for over 1.5 years. ResLake has scheduled billions of jobs since its deployment. We find that ResLake improves JCT of jobs by at least 20%, and can improve resource utilization balance across DCs by up to 53%.

We study how to schedule data sources in a wireless time-sensitive information system with multiple heterogeneous and unreliable channels to minimize the total expected Age-of-Information (AoI). Although one could formulate this problem as a discrete-time Markov Decision Process (MDP), such an approach suffers from the curse of dimensionality and lack of insights. For single-channel systems, prior studies have developed lower-complexity solutions based on the Whittle index. However, Whittle index has not been studied for systems with multiple heterogeneous channels, mainly because indexability is not well defined when there are multiple dual cost values, one for each channel. To overcome this difficulty, we introduce new notions of partial indexability and partial index, which are defined with respect to one channel's cost, given all other channels' costs. We then combine the ideas of partial indices and max-weight matching to develop a Sum Weighted Index Matching (SWIM) policy, which iteratively updates the dual costs and partial indices. The proposed policy is shown to be asymptotically optimal in minimizing the total expected AoI, under a technical condition on a global attractor property. Extensive performance simulations demonstrate that the proposed policy offers significant gains over conventional approaches by achieving a near-optimal AoI. Further, the notion of partial index is of independent interest and could be useful for other problems with multiple heterogeneous resources.

We study low-overhead uplink multi-access algorithms for massive Internet-of-Things (IoT) that can exploit the MIMO performance gain. Although MIMO improves system capacity, it usually requires high overhead due to Channel State Information (CSI) feedback, which is unsuitable for IoT. Recently, a Pseudo-Random Beam-Forming (PRBF) scheme was proposed to exploit the MIMO performance gain for uplink IoT access with uniform channel and load, without collecting CSI at the BS. For non-uniform channel and load, new adaptive beamselection and random-access algorithms are needed to efficiently utilize the system capacity with low overhead. Most existing algorithms for a related multi-channel scheduling problem require each node to at least know some information of the queue length of all contending nodes. In contrast, we propose a new Low-overhead Multi-Channel Joint Channel-Assignment and Random-Access (L-MC-JCARA) algorithm that reduces the overhead to be independent of the number of interfering nodes. A key novelty is to let the BS estimate the total backlog in each contention group by only observing the random-access events, so that no queue-length feedback is needed from IoT devices. We prove that L-MC-JCARA can achieve at least `0.24`` of the capacity region of the optimal centralized scheduler for the corresponding multi-channel system.

A pseudo-random beamforming (PRBF) based random access (RA) system is proposed to enable uplink (UL) machine-type communications (MTC) with ultra low signaling overheads. Specifically, a pseudo random (PR) sequence is used as public information to coordinate the beamforming vectors used at the base station (BS) and the devices. Within the coherence time window, each device distributively determines in advance the ''good'' time slots and receiving beams for transmission. This UL protocol reduces the overheads due to the feedback of channel state information and the control signals for centralized scheduling. This paper derives the throughput and user scaling of the proposed M- PRBF-CA protocol for achieving spatial multiplexing gain, under both an i.i.d. slow fading channel and a correlated slow fading channel. Our simulation results confirm the analysis in both fading channel models.

The uncertainty and variability of renewable generation pose significant challenges to reliable power-grid operations. This paper designs robust online strategies for jointly operating energy storage units and fossil-fuel generators to achieve provably reliable grid operations at all times under high renewable uncertainty, without the need of renewable curtailment. In particular, we jointly consider two power system operations, namely day-ahead reliability assessment commitment (RAC) and real-time dispatch. We first extend the concept of “safe-dispatch sets” to our setting. While finding such safe-dispatch sets and checking their non-emptiness provide crucial answers to both RAC and real-time dispatch, their computation incurs high complexity in general. To develop computationally-efficient solutions, we first study a single-bus case with one generator-storage pair, where we derive necessary conditions and sufficient conditions for the safe-dispatch sets. Our results reveal fundamental trade-offs between storage capacity and generator ramp-up/-down limits to ensure grid reliability. Then, for the more general multi-bus scenario, we split the net-demand among virtual generator-storage pairs (VGSPs) and apply our single-bus decision strategy to each VGSP. Simulation results on an IEEE 30-bus system show that, compared with state-of-art solutions, our scheme requires significantly less storage to ensure reliable grid operation without any renewable curtailment.