Beeping Network (BN) is a popular graph-based model of wireless computation, which applies the OR operation to one-bit messages sent simultaneously by neighbors. It admits fast (polylogarithmic in the number of nodes n) randomized solutions to many graph problems, but all known deterministic algorithms for non-trivial graph problems are at least polynomial in the maximum node degree Δ. We improve known results for deterministic algorithms by showing that this polynomial can be as low as Õ(Δ²). More precisely, we show how to simulate a single round of any CONGEST algorithm in any network in O(Δ² polylog n) beeping rounds, each accommodating at most one beep per node, even if the nodes intend to send different messages to different neighbors. This upper bound reduces polynomially the time for a deterministic simulation of CONGEST in a Beeping Network, comparing to the best known algorithms, and nearly matches the time obtained recently using randomization (up to a poly-logarithmic factor) as well as the lower bound. Specifically, any algorithm designed for the CONGEST networks can be run in BNs with O(Δ² polylog n) multiplicative overhead, e.g., we can now deterministically compute an MIS in any BN in O(Δ² polylog n) beeping rounds, improving the previous best Θ(Δ³)-round solution. For h-hop simulations, we prove a lower bound Ω(Δ^{h+1}), and we design a nearly matching algorithm that is able to "pipeline" the node-to-node information in a faster way than beeping layer-by-layer.

Radio Networks (RN) is one of the fundamental models for network communication where nodes can broadcast messages locally but their simultaneous transmissions can interfere with each other at their shared neighbors. This work focuses on performing the very fundamental primitive of Local Broadcast, in spite of the interferences. We investigate to what extent local knowledge, called advice, relating to the 2-local domination number γ₂ may speed up Local Broadcast. Specifically for each node and some dominating set, knowledge about some neighboring dominating node and the local number among the neighbors of that dominating node. We show that such advice is sufficient to build an efficient oblivious transmission schedule. Along those lines, we present three algorithms trading the level of adaptiveness (from oblivious to adaptive) for bits of advice per node (from O(log (Δγ₂)) to 1). All our algorithms complete Local Broadcast in Õ(Δγ₂²) rounds, where Δ is the maximum degree of the network. On the side of lower bounds, we show that, for each quasi-adaptive deterministic Local Broadcast algorithm, there is some RN that requires Ω(min{(min{Δ,γ₂}/log n)²,n}) communication rounds, where n is the number of network nodes. In quasi-adaptive protocols nodes may stop executing once its computational task is completed. To the best of our knowledge, this is the first (nearly) quadratic Local Broadcast (same message for all neighbors) lower bound in the RN model. Our lower bound is stronger than previous works in multiple ways: i) it is nearly quadratically better than the best known general lower bound for this class of algorithms, ii) it applies to a wider class of algorithms than previous work for fully oblivious, iii) it achieves similar time lower bound than previous work proved for a much more demanding Local Broadcast where each node sends a possibly different message to each neighbor, and iv) it takes into account the local domination parameter γ₂.

A phase clock is a basic synchronization mechanism that keeps distributed nodes closely synchronized to execute the same phase of a distributed algorithm. A phase clock is typically implemented with a local logical counter that keeps track of the current phase count. Phase clocks are particularly useful in population protocols for implementing leader election and majority selection. We study phase clocks that tolerate Byzantine faults. We show that there is a phase clock that tolerates up to f < n/3 faulty nodes, where n is the number of nodes, such that the gap of the local counter values is O(n²log n). The gap can be further lowered to O(log n) when f ≤ n/8. We also show that if f > n/3, then the gap grows to infinity as time increases. While analyzing phase clock we introduce novel techniques and bounds for balls into bins processes, which might be of independent interest. Using the phase clock, we obtain a majority selection population protocol that tolerates up to f faults and decides on the majority value in O(log² n) parallel time using poly-log states per node.

A large volume of work has already studied various aspects of a synchronous multiple access channel (MAC). However, synchronization is costly and far from reality. Very little is known in the case when stations communicating on the channel may observe asynchronous behavior. Unfortunately, in certain strong asynchrony settings it is impossible to ensure even a small positive throughput (deterministically). Hence, in this paper, we study whether a limited amount of synchrony is already enough for obtaining stability and high throughput. More specifically, we present a novel model to capture a bounded asynchrony, where the “bounded” aspect is captured by an upper bound$R$on the length of any asynchronous time slot. We design two distributed deterministic algorithms to schedule transmissions of dynamically arriving packets at asynchronous stations, which guarantee optimal throughput for all but one packet injection rates and bounded queues at any time (this combination is sometimes known as optimal stable throughput). One of these algorithms is collision-free, while the other, instead, avoids control messages. Combining these results with our impossibility results we characterize exactly the very limited case where there is an inherent difference between synchronous and asynchronous networks for obtaining optimal stable throughput for this problem. As a subroutine, we design a new leader election algorithm for this model and prove upper and lower bounds on the number of slots. Interestingly, when$R$is a constant, our results match (asymptotically) the known results in synchronous slotted networks, while if$R$is a larger parameter, our lower bound proves that an additional factor of$\Omega(\frac{R}{\log R})$is necessary in the formula on the number of slots.

Stability is an important issue in order to characterize the performance of a network, and it has become a major topic of study in the last decade. Roughly speaking, a communication network system is said to be stable if the number of packets waiting to be delivered (backlog) is finitely bounded at any one time. In this paper we introduce a number of routing scheduling algorithms which, making use of certain knowledge about the network's structure, guarantee stability for certain injection rates. First, we introduce two new families of combinatorial structures, which we call universally strong selectors and generalized universally strong selectors, that are used to provide a set of transmission schedules. Making use of these structures, we propose two local-knowledge packet-oblivious routing scheduling algorithms. The first proposed routing scheduling algorithm only needs to know some upper bounds on the number of links and on the network's degree, and is asymptotically optimal regarding the injection rate for which stability is guaranteed. The second proposed routing scheduling algorithm is close to be asymptotically optimal, but it only needs to know an upper bound on the number of links. For such algorithms, we also provide some results regarding both the maximum latencies and queue lengths. Furthermore, we also evaluate how the lack of global knowledge about the system topology affects the performance of the routing scheduling algorithms.

Shah, Shin and Tetali [25] initiated the study of queuing systems on the medium access channel with arbitrary interference graph. The graph models dependencies between the channel members -- any two connected by an edge are dependent. This problem could be also re-stated as a query system with dependent elements or local scheduling of dependent packets/jobs. In short, if two dependent units, also called stations, want to transmit (or be in the same query, or do jobs in parallel), there is a conflict and none of them succeeds. The problem is particularly challenging, if the units need to make their decisions locally, without any coordination. Prior the paper by Shah, Shin and Tetali [FOCS 2011], the main focus was on the clique graph -- even in this simple topology, many problems related to stability remain open. While the solution by Shah, Shin and Tetali [FOCS 2011] is semi-local, as nodes make use of information about interfering neighbors in the graph, we provide the first purely local stable algorithms. In particular, in our algorithms stations make their decision whether to transmit or not based only on looking at their local queues. Based only on this feature, and without using a priori knowledge of topology, we design an algorithm that allows all stations for implicit transferring information to and from all other stations. We use it as a tool for developing universally stable algorithms for the problem of queuing messages -- i.e., guaranteeing bounded queues when, on average, less than one independent set is injected per round. The first one is stable in adversarial (worst-case) sense, the second one -- in stochastic sense (average-case). We also prove optimality of our algorithm in adversarial sense: no algorithm can be stable against injections with rate ρ=1 (when, on average, one independent set is injected per round). Moreover, for the class of non-adaptive protocols, we show that it is not possible to achieve stability for any injection rate Ω(1/log m), where m is the size of the largest clique in the interference graph. We extend the result by showing that such protocols are not stable on some interference graphs with no cliques of size at least 3 even for injection rates Ω(√[3](log n)/n). This result separates the model with general interference graphs from the classical model of a multiple access channel (in which the interference graph is a clique), in which there exist non-adaptive algorithms stable for adversarial injection rates O(1/log2 n).

Millimeter wave communication (mmWave) allows high-speed access to the radio channel. Given the highly-directional nature of mmWave, dense deployments can be implemented with a macro base station serving many micro base stations, rather than connecting micro base stations directly to the core network as in legacy cellular systems. Moreover, micro base stations may cooperate in relaying packets to other micro base stations. Relays and spatial reuse speed up communication, but increase the complexity of scheduling. In this work, we study the mmWave wireless backhaul scheduling problem in the described architecture, assuming stochastic arrival of packets at the macro base station to be delivered to micro base stations. We present various results concerning system stability, defined as a bounded expected queue sizes of macro base station and micro base stations, under different patterns of random traffic. In particular, that almost all admissible arrival patterns could be handled by some universally stable algorithms, while non-admissible arrival patterns do not allow stability for any algorithm.

In this work we study stability of local memoryless packet scheduling policies in a distributed system of n nodes/queues under contention. The local policies at nodes may only access their current local queues, and have no other feedback from the underlying distributed system. Moreover, their memory is limited to some basic parameters. The packets arrive at queues according to arrival patterns controlled by an adversary restricted only by injection rate rho and burstiness b, or driven by a stochastic process; the former model analyzes worst-case stability while the latter - average case. We assume that the underlying distributed system is a classic shared channel, in which no two packets could be successfully scheduled (and removed from queues) at the same time. We show that there is a local memoryless scheduling policy which is both adversarially and stochastically stable for injection rates Omega(1/log n). Another algorithm achieves even higher - constant - stable injection rate, but only for a bounded range of burstiness. The first algorithm is utilizing properties of interleaved ultra-selectors, for which we prove stronger properties than known so far, while the second one is based on entirely new concept of selector with thresholds, unlike previously considered binary selectors/codes in the literature. Note that popular Backoff algorithms, some of which achieve stability for constant (stochastic) injection rates [Johan Håstad et al., 1996], use memory to record current state (e.g., the number of unsuccessful transmissions or the result of random sampling in each window) as well as randomization and feedback from the channel; unlike solutions in this work, which are memoryless and do not rely on randomization or channel feedback (thus, could be used independently from the link layer protocols). {}

We study stability of local packet scheduling policies in a distributed system of n nodes. The local policies at nodes may only access their local queues, and have no other feedback from the underlying distributed system. The packets arrive at queues according to arrival patterns controlled by an adversary restricted only by injection rate rho and burstiness b. In this work, we assume that the underlying distributed system is a shared channel, in which in order to get rid of a packet from the queue, a node needs to schedule it for transmission on the channel and no other packet is scheduled for transmission at the same time. We show that there is a local adaptive scheduling policy with relatively small memory, which is universally stable on a shared channel, that is, it has bounded queues for any rho<1 and b >= 0. On the other hand, without memory the maximal stable injection rate is O(1/log n). We show a local memoryless (non-adaptive) scheduling policy based on novel idea of ultra strong selectors which is stable for slightly smaller injection c/log^2 n, for some constant c>0.

It is crucial to ensure reliability, security and stability of cloud services without sacrificing too much resources in the area of workload management in clouds. The paper evaluates and compares lightweight decentralized algorithms for scheduling a workload part of which could be unreliable, in the context of {\em heterogeneous} cloud data centers. This unreliability could be caused by various types of failures or attacks. The framework for robust workload scheduling efficiently combines classic fault tolerant and security tools, such as packet/job scanning, with workload scheduling, and it does not use any heavy resource consuming tools, e.g., cryptography or non-linear optimization. More specifically, the framework uses a novel objective function to allocate jobs to servers and constantly decides which job to scan based on a formula associated with the objective function. In previous work it was shown how to set up the objective function and the corresponding scanning procedure of the {\em central job scheduler} to make the system provably stable, provided a specific capacity condition is satisfied. As a result, it was shown that the framework assures cloud stability even though naive scanning-all and scanning-none strategies are not stable for both centralized and decentralized scheduling in {\em homogeneous} data centers. In this work we extend the work to {\em heterogeneous} data centers, for which we show that decentralized algorithms based on Join Shortest Queue and Join Shortest Work policies are {\em stable} for every workload within the system capacity, while the algorithms based on popular Power of Two Choices, Round Robin and Uniform Random policies are {\em not stable} for a substantial amount of workloads even within the system capacity.

We consider the problem of scheduling packets of different lengths via k directed parallel communication links. The links are prone to simultaneous errors --- if an error occurs, all links are affected. Dynamic packet arrivals and errors are modelled by a worst-case adversary. The goal is to optimize competitive throughput of online scheduling algorithms. Two types of failures are considered: jamming, when currently scheduled packets are simply not delivered, and crashes, when additionally the channel scheduler crashes losing its current state. For the former, milder type of failures, we prove an upper bound on competitive throughput of 3/4 - 1/(4k) for odd values of k, and 3/4 - 1/(4k+4) for even values of k. On constructive side, we design an online algorithm that, for packets of two different lengths, matches the upper bound on competitive throughput. To compare, scheduling on independent channels, that is, when adversary could cause errors on each channel independently, reaches throughput of 1/2. This shows that scheduling under simultaneous jamming is provably more efficient than scheduling under channel-independent jamming. In the setting with crash failures we prove a general upper bound for competitive throughput of (√5-1)/2 and design an algorithm achieving it for packets of two different lengths. This result has two interesting implications. First, simultaneous crashes are significantly stronger than simultaneous jamming. Second, due to the above mentioned upper bound of 1/2 on throughput under channel-independenterrors, scheduling under simultaneous crashes is significantly stronger than channel-independent crashes, similarly as in the case of jamming errors.