Load balancing is among the basic primitives in distributed computing. In this paper, we consider this problem when executed locally on a network with nodes prone to failures. We show that there exist lightweight network topologies that are immune to message delivery failures incurred by (at most) a constant fraction of all nodes. More precisely, we design a novel deterministic fault-tolerant local load balancing (LLB) algorithm, which, similarly to their classical counterparts working in fault-free networks, has a relatively simple structure and guarantees exponentially fast convergence to the average value despite crash and omission failures.

Discovering elements of a hidden set, also known as Group Testing (GT), is a well-established area in which one party tries to discover elements hidden by the other party by asking queries and analyzing feedback. The feedback is a function of the intersection of the query with the hidden set - in our case, it is a classical double-threshold function, which returns i if the intersection is a singleton i and "null" otherwise (i.e., when the intersection is empty or of size at least 2). In this work, we enhance GT by two features. First, we introduce a local feedback framework to this problem: each hidden element is an "autonomous" element and can analyze feedback itself, but only for the queries to which it belongs. The goal is to design a deterministic non-adaptive sequence of queries that enables each non-hidden element to learn about all other hidden elements. We show that, surprisingly, this task requires substantially more queries than the classic group testing -- by proving a super-cubic (in terms of the number of hidden elements) lower bound and by constructing a specific query sequence of slightly longer length. Such a query system is also an extension of a well-known superimposed code, in a way that the decoding can be done only by the owners of the codewords. Second, we extend the results to the model where elements may belong to certain clusters and retrieving them could be done only via queries avoiding elements from "interfering" clusters. The main challenge is in not knowing which interfering clusters are non-empty (and thus, need to be avoided) and how to speed up the retrieval process by asking queries across many clusters. Our algorithms can be generalized to other feedback functions, to adversarial/stochastic fault-prone scenarios, implemented in a distributed setting and applied to the information theory and codes.

One of the classic problems in online decision-making is the secretary problem, where the goal is to hire the best secretary out of n rankable applicants or, in a natural extension, to maximize the probability of selecting the largest number from a sequence arriving in random order. Many works have considered generalizations of this problem where one can accept multiple values subject to a combinatorial constraint. The seminal work of Babaioff, Immorlica, Kempe, and Kleinberg (SODA'07, JACM'18) proposed the matroid secretary conjecture, suggesting that there exists an O(1)-competitive algorithm for the matroid constraint, and many works since have attempted to obtain algorithms for both general matroids and specific classes of matroids. The ultimate goal of these results is to obtain an e-competitive algorithm, and the strong matroid secretary conjecture states that this is possible for general matroids. One of the most important classes of matroids is the graphic matroid, where a set of edges in a graph is deemed independent if it contains no cycle. Given the rich combinatorial structure of graphs, obtaining algorithms for these matroids is often seen as a good first step towards solving the problem for general matroids. For matroid secretary, Babaioff et al. (SODA'07, JACM'18) first studied graphic matroid case and obtained a 16-competitive algorithm. Subsequent works have improved the competitive ratio, most recently to 4 by Soto, Turkieltaub, and Verdugo (SODA'18). In this paper, we break the 4-competitive barrier for the problem, obtaining a new algorithm with a competitive ratio of 3.95. For the special case of simple graphs (i.e., graphs that do not contain parallel edges) we further improve this to 3.77. Intuitively, solving the problem for simple graphs is easier as they do not contain cycles of length two. A natural question that arises is whether we can obtain a ratio arbitrarily close to e by assuming the graph has a large enough girth. We answer this question affirmatively, proving that one can obtain a competitive ratio arbitrarily close to e even for constant values of girth, providing further evidence for the strong matroid secretary conjecture. We further show that this bound is tight: for any constant g, one cannot obtain a competitive ratio better than e even if we assume that the input graph has girth at least g. To our knowledge, such a bound was not previously known even for simple graphs.

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.

We study the problem of distributed construction of efficient de-centralized communication schedules for ad-hoc wireless networks. We consider a model which is close to real scenarios: (1) the SINR interference model, which covers most important distinctive features of contemporary wireless communication, such as signal fading, collisions and accumulation of signal, and (2) any underlying metric of bounded growth, which includes Euclidean space with certain type of obstacles. Most of efficient solutions in the SINR model rely on probabilistic algorithms, assuming access of nodes to the sources of independent truly random bits, which in practice is hard to get by wireless devices.In this paper we show that key efficient de-centralized communication abstraction primitives, such as aggregation and broadcast schedules (which are bases of many other communication tasks), can be efficiently built by distributed algorithms in SINR networks without using any randomization. In particular, the length of the built communication schedules are asymptotically as efficient as those significantly relying on randomization, and close to the theoretic lower bounds. Importantly, the time (round) complexity of our solutions grows only logarithmically with respect to the growth of the density of a network, which makes them scalable in real-life scenarios.

We consider a fundamental problem for communication in multi-hop wireless networks, called Distributed Link Scheduling (DLS): each node may have packet(s) addressed to some of its reachable neighbors and the goal is to deliver all packets to their destinations. The challenge in distributed realization of DLS is the interference between simultaneous transmissions.All efficiently scalable DLS solutions so far relied heavily on substantial amount of true randomness, which is, however, intrinsically difficult to get in wireless devices. Therefore, in this work we focus on deterministic solutions, their worst-case complexity measured in the number of communication rounds, and whether it could be improved for some classes of wireless network topologies. We first prove that, in general, deterministic solutions could be even nearly-quadratically (i.e., up to a polylogarithmic factor) worse than the best randomized ones. On the other hand, we show that deterministic solutions could be efficient if the underlying wireless network topology is defined by a metric of small growth. More precisely, we show nearly-tight upper and lower bounds on the length of the schedules, constructed and run in a distributed way by wireless nodes located in a metric space. These bounds depend on both the wireless interference of the set of links on each other, called affectance, and the growth parameter of the underlying metric space. In particular, for metrics of constant growth (so called, bounded growth metrics, e.g., constant-dimension Euclidean spaces, even with some obstacles, or sparse graphs), the length of our deterministic schedule is almost as short as the best known randomized ones.

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.

We study the Distributed Wireless Link Scheduling (DWLS) problem: there is a set ofnautonomous stations, called senders, each with a message to be delivered to some other station, called receiver. The names and locations of all stations are arbitrarily selected and unknown to each other, to mirror an arbitrary scenario that may occur in mobile communication. Each pair ((sender,receiver),message) is called a request, and the event of successfully delivering the message is called the realization of the request. In the DWLS problem, the requests are realized through wireless communication links (which is a conceptual notion of two nodes being capable of direct wireless delivery of a message) between the stations. The decision to transmit a message is made locally by each station. We consider networks where communication links may interfere with each other, where the interference is an arbitrary input function of each pair of links, customarily called affectance; if the total affectance of other links whose senders are currently transmitting is above a given threshold, the considered transmission is not successful. In the above context, we study the impact of the number of truly random bits used by each link/sender, on the length of the transmission schedules. Specifically, for any setLofnrequests with maximum average affectance$A(L)$, we present a deterministic algorithm (i.e., 0 random bits) and a randomized algorithm using$O(\log A(L)\log n)$random bits per link. (In this abstract we present formulas in simplified forms, for brevity.) The lengths of their transmission schedules are$O(A(L)^{2}\log ^{3} n)$and$O(A(L)\log n)$, respectively. We then combine both approaches to get a randomized solution using$O(\log W \log n)$truly random bits per station with schedules of length$O\left ({{\frac {A(L)^{2}}{W}\log n}}\right)$, for any$W\le A(L)$. To the best of our knowledge, our study is a first step towards understanding the trade-offs between randomness and time complexity of Link Scheduling under arbitrary interference. It is particularly important as currently used (in practice) wireless protocols are either deterministic or use a very small random seed of (truly) random bits.

Fault-tolerant Consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communication medium. This problem is particularly challenging and costly against an adaptive adversary with full information. Bar-Joseph and Ben-Or (PODC'98) were the first who proved an absolute lower bound Ω(√{n/log n}) on expected time complexity of Consensus in any classical (i.e., randomized or deterministic) message-passing network with n processes succeeding with probability 1 against such a strong adaptive adversary crashing processes. Seminal work of Ben-Or and Hassidim (STOC'05) broke the Ω(√{n/log n}) barrier for consensus in the classical (deterministic and randomized) networks by enhancing the model with quantum channels. In such networks, quantum communication between every pair of processes participating in the protocol is also allowed. They showed an (expected) constant-time quantum algorithm for a linear number of crashes t < n/3. In this paper, we improve upon that seminal work by reducing the number of quantum and communication bits to an arbitrarily small polynomial, and even more, to a polylogarithmic number - though, the latter in the cost of a slightly larger polylogarithmic time (still exponentially smaller than the time lower bound Ω(√{n/log n}) for the classical computation models).

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.

We give the first non-trivial decremental dynamic embedding of a weighted, undirected graph $G$ into $\ell_p$ space. Given a weighted graph $G$ undergoing a sequence of edge weight increases, the goal of this problem is to maintain a (randomized) mapping $\phi: (G,d) \to (X,\ell_p)$ from the set of vertices of the graph to the $\ell_p$ space such that for every pair of vertices $u$ and $v$, the expected distance between $\phi(u)$ and $\phi(v)$ in the $\ell_p$ metric is within a small multiplicative factor, referred to as the distortion, of their distance in $G$. Our main result is a dynamic algorithm with expected distortion $O(\log^2 n)$ and total update time $O\left((m^{1+o(1)} \log^2 W + Q)\log(nW) \right)$, where $W$ is the maximum weight of the edges, $Q$ is the total number of updates and $n, m$ denote the number of vertices and edges in $G$ respectively. This is the first result of its kind, extending the seminal result of Bourgain ’85 to the expanding field of dynamic algorithms. Moreover, we demonstrate that in the fully dynamic regime, where we tolerate edge insertions as well as deletions, no algorithm can explicitly maintain an embedding into $\ell_p$ space that has a low distortion with high probability.

We study the complexity of the problem of reaching agreement in a synchronous distributed system, also called consensus, by n autonomous parties, when the communication links from/to faulty parties can omit messages. The faulty parties are selected and controlled by an adaptive, full-information, computationally unbounded adversary. We design a randomized algorithm that works in [EQUATION] rounds and sends O(n2 log3 n) total number of communication bits, where the number of faulty parties can be Θ(n). When the number of faulty parties is linear in n, our result is simultaneously tight for both these measures within polylogarithmic factors: due to the Ω(n2) lower bound on the number of messages send by any Monte Carlo solution, by Abraham et al. (PODC'19), and due to the [EQUATION] lower bound on the number of rounds of any Las Vegas solution, by Bar-Joseph and Ben-Or (PODC'98). Thereby, this work settles the landscape of the consensus problem in the omission failures model, which stood as an open question since the work of Dolev and Strong (SICOMP'83).

We study the power of posted pricing mechanisms for Bayesian online optimization problems subject to combinatorial feasibility constraints. When the objective is to maximize social welfare, the problem is widely studied in the literature on prophet inequalities. While most (though not all) existing algorithms for prophet inequalities are implemented using a pricing mechanism, whether or not this can be done in general is unknown, and was formally left as an open question by Dutting, Feldman, Kesselheim, and Lucier (FOCS 2017, SICOMP 2020). Understanding the power and limitations of posted prices is important from a mechanism design perspective because any posted price mechanism is truthful, and is also interesting in its own right as it can guide future research on prophet inequalities.

Sharding is used to improve the scalability and performance of blockchain systems. We investigate the stability of blockchain sharding, where transactions are continuously generated by an adversarial model. The system consists of n processing nodes that are divided into s shards. Following the paradigm of classical adversarial queuing theory, transactions are continuously received at injection rate ρ ≤ 1 and burstiness b > 0. We give an absolute upper bound max{2/k+1, 2⌊√2s⌋} on the maximum injection rate for which any scheduler could guarantee bounded queues and latency of transactions, where k is the number of shards that each transaction accesses. We next give a basic distributed scheduling algorithm for uniform systems where shards are equally close to each other. To guarantee stability, the injection rate is limited to ρ ≤ max{1/18k, 1/ ⌈18√s⌉}. We then provide a fully distributed scheduling algorithm for non-uniform systems where shards are arbitrarily far from each other. By using a hierarchical clustering of the shards, stability is guaranteed with injection rate ρ ≤ 1/(c1d log2 s) ⋅ max{1/k, 1/√s}, where d is the worst distance of any transaction to the shards it will access, and c1 is some positive constant. We also conduct simulations to evaluate the algorithms and measure the average queue sizes and latency throughout the system. To our knowledge, this is the first adversarial stability analysis of sharded blockchain systems.

Given a graph G, a classical problem in graph theory is the construction of a spanner H -- a sparse subgraph of G that closely approximates the distances between nodes in G. The distance stretch~α of H is the factor of how much the distances in H increase versus G. Here, we consider sparse spanner constructions that can also preserve the node congestion of routing problems in G. The congestion stretch β of H is the factor of how much the (smallest) congestion of a routing problem increases in H versus G. We introduce the notion of (α, β)-DC-spanner (i.e., a Distance-Congestion-spanner) that simultaneously controls the stretches for distance and congestion. We show that for expander graphs with n nodes, there is a (3, O(log n))-DC-spanner with O(n5/3) edges. We also examine Δ-regular graphs with Δ ≥ n2/3, where we show how to obtain a (3, O(√Δ ⋅ log n))-DC-spanner with O(n5/3 log2n) edges. Finally, we show that there is a graph such that any optimal size 3-distance spanner has Ω(n7/6) edges and is a (3, Ω(n1/6))-DC-spanner.

We study contention resolution (CR) on a shared channel modelled as a game with selfish players. There are n agents and the adversary chooses some k smaller than n of them as players. Each participating player in a CR game has a packet to transmit. A transmission is successful if it is performed as the only one at a round. Each player aims to minimize its packet latency. We introduce the notion of adversarial equilibrium (AE), which incorporates adversarial selection of players. We develop efficient deterministic communication algorithms that are also AE. We characterize the price of anarchy in the CR games with respect to AE.

We study the Distributed Wireless Link Scheduling (DWLS) problem: there is a set of n autonomous stations, called senders, each with a packet to be delivered to some other station, called receiver. The names and locations of all stations are arbitrarily selected and unknown to each other, to mirror an arbitrary scenario that may occur in mobile communication. Each pair sender-receiver and the message to be sent is called a request, and the event of successfully delivering the message is called the realization of the request.In the DWLS problem, the requests are realized through wireless communication links (which is a conceptual notion of two nodes being capable of direct wireless delivery of a message) between the stations. The decision to transmit a message is made locally by each station. We consider networks where communication links may interfere with each other, where the interference is an arbitrary input function of each pair of links, customarily called affectance; if the total affectance of other links whose senders are currently transmitting is above a given threshold, the considered transmission is not successful.In the above context, we study the impact of algorithms’ min-entropy, measured as the number of truly random bits used by each link/sender, on the length of the transmission schedules. Specifically, for any set L of n requests with maximum average affectance A(L), we present a deterministic algorithm (i.e., 0 random bits) and a randomized algorithm using O(logA(L)logn) random bits per link. (In this abstract we present formulas in simplified forms, for brevity.) The lengths of their transmission schedules are O(A(L)2log3n) and O(A(L)logn), respectively. We then combine both approaches to get a randomized solution with min-entropy O(logW logn) per station that uses schedules of length $O\left( {\frac{{A{{(L)}^2}}}{W}\log n} \right)$, for any W ≤ A(L).To the best of our knowledge, our study is a first step towards understanding the trade-offs between randomness and time complexity of Link Scheduling under arbitrary interference. It is particularly important as currently used (in practise) wireless protocols are either deterministic or use a very small random seed of (truly) random bits.

We study the Combinatorial Group Testing (CGT) problem in a novel game-theoretic framework, with a solution concept of Adversarial Equilibrium (AE). In this new framework, we have $n$ selfish agents corresponding to the elements of the universe $[n] =\{0,1,\ldots,n-1\}$ and a hidden set $K \subseteq [n]$ of active agents of size $|K| = k \ll n$. In each round of the game, each active agent decides if it is present in a query $Q \subseteq [n]$, and all agents receive feedback on $Q \cap K$. The goal of each active agent is to assure that its id could be learned from the feedback as early as possible. We present a comprehensive set of results in this new game, where we design and analyze adaptive algorithmic strategies of agents which are AE's. In particular, if $k$ is known to the agents, then we design adaptive AE strategies with provably near optimal learning time of $O(k \log(n/k))$. In the case of unknown $k$, we design an adaptive AE strategies with learning time of order $n^k$, and we prove a lower bound of $\Omega(n)$ on the learning time of any such algorithmic strategies. This shows a strong separations between the two models of known and unknown $k$, as well as between the classic CGT, i.e., without selfish agents, and our game theoretic CGT model.

We develop deterministic algorithms for the problems of consensus, gossiping and checkpointing with nodes prone to failing. Distributed systems are modeled as synchronous complete networks. Failures are represented either as crashes or Byzantine faults with authentication. The algorithmic goal is to have both linear running time and linear amount of communication for as large an upper bound t on the number of faults as possible, with respect to the number of nodes n. For crash failures, these bounds of optimality are t = O(n / (log n)) for consensus and t = O(n / (log2 n)) for gossiping and checkpointing. For the model of Byzantine faults with authentication, we show how to reach consensus in both linear running time and communication for t = O(√n). We show how to implement the consensus algorithm for crash failures in the single-port model such as to preserve the range of t for which both the running time and communication are optimal. We prove a lower bound Ω (t+log n) on the running time of algorithms for each of the considered problems.

Fault-tolerant consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communication medium. This problem is particularly challenging and costly against an adaptive adversary with full information. Bar-Joseph and Ben-Or [7] (PODC'98) were the first who proved an absolute lower bound [EQUATION] on expected time complexity of consensus in any classic (i.e., randomized or deterministic) message-passing network with n processes succeeding with probability 1 against such a strong adaptive adversary crashing processes.

Agent-based crawlers are commonly used in network maintenance and information gathering. In order not to disturb the main functionality of the system, whether acting at nodes or being in transit, they need to operate online, perform a single operation fast and use small memory. They should also be preferably deterministic, as crawling agents have limited capabilities of generating a large number of truly random bits. We consider a system in which an agent receives an update, typically an insertion or deletion, of some information upon visiting a node. On request, the agent needs to output hot information, i.e., with the net occurrence above certain frequency threshold. A desired time and memory complexity of such agent should be poly-logarithmic in the number of visited nodes and inversely proportional to the frequency threshold. Ours is the first such agent with rigorous analysis and a complementary almost-matching lower bound.

Group Testing (GT) is about learning a (hidden) subset $K$, of size $k$, of some large domain $N$, of size $n \gg k$, using a sequence of queries. A result of a query provides some information about the intersection of the query with the unknown set $K$. The goal is to design efficient (polynomial time) and scalable (polylogarithmic number of queries per element in $K$) algorithms for constructing queries that allow to decode every hidden set $K$ based on the results of the queries. A vast majority of the previous work focused on randomized algorithms minimizing the number of queries; however, in case of large domains N, randomization may result in asignificant deviation from the expected precision of learning the set $K$. Others assumed unlimited computational power (existential results) or adaptiveness of queries (next query could be constructed taking into account the results of the previous queries) – the former approach is less practical due to non-efficiency, and the latter has several drawbacks including non-parallelization. To avoid all the abovementioned drawbacks, for Quantitative Group Testing (QGT) where query result is the size of its intersection with the hidden set, we present the first efficient and scalable non-adaptive deterministic algorithms for constructing queries and decoding a hidden set K from the results of the queries – these solutions do not use any randomization, adaptiveness or unlimited computational power.

We study consensus and checkpointing in synchronous distributed systems. There are n nodes that communicate by sending messages, and any two nodes can communicate directly. The nodes are prone to crashing, with an upper bound t on the number of crashes. Algorithms use overlay networks of choice to save on the amount of communication. We explore using Ramanujan graphs as such overlay networks. We demonstrate that Ramanujan graphs have topological properties conducive to fault-tolerance and time/communication efficiency of distributed algorithms. Our consensus algorithm assumes binary input values, runs in O(t) time and sends O(n+t log t) bits. The algorithm sends the optimum number O(n) of bits for t=O(n/log n), thus for this range of t it improves on the algorithm by Galil, Mayer and Yung [FOCS 1995] that also sends O(n) bits but works in exponential time. The consensus algorithm can be implemented such that a node sends a message to at most one node at a round while maintaining the asymptotic time and communication performance bounds. Our checkpointing algorithm runs in linear time O(n) and with O(n log7 n) messages. It improves on the most communication-efficient and time-optimal algorithm by Galil, Mayer and Yung [FOCS 1995], which may have O(n1+ε) messages sent, for any chosen constant ε>0.

Consensus is one of the most thoroughly studied problems in distributed computing, yet there are still complexity gaps that have not been bridged for decades. In particular, in the classical message-passing setting with processes’ crashes, since the seminal works of Bar-Joseph and Ben-Or [PODC 1998] and Aspnes and Waarts [SICOMP 1996, JACM 1998] in the previous century, there is still a fundamental unresolved question about communication complexity of fast randomized Consensus against a (strong) adaptive adversary crashing processes arbitrarily online. The best known upper bound on the number of communication bits is Θ(n3/2/√logn) per process, while the best lower bound is Ω(1). This is in contrast to randomized Consensus against a (weak) oblivious adversary, for which time-almost-optimal algorithms guarantee amortized O(1) communication bits per process. We design an algorithm against adaptive adversary that reduces the communication gap by nearly linear factor to O(√n· n) bits per process, while keeping almost-optimal (up to factor O(log3 n)) time complexity O(√n·log5/2 n).

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.

We study the problem of randomized Leader Election in synchronous distributed networks with indistinguishable nodes. We consider algorithms that work on networks of arbitrary topology in two settings, depending on whether the size of the network, i.e., the number of nodes$n$, is known or not. In the former setting, we present a new Leader Election protocol that improves over previous work by lowering message complexity and making it close to a lower bound by a factor in$\widetilde{O}(\sqrt{t_{mix}\sqrt{\Phi}})$, where$\Phi$is the conductance and$t_{mix}$is the mixing time of the network graph. We then show that lacking the network size no Leader Election algorithm can guarantee that the election is final with constant probability, even with unbounded communication. Hence, we further classify the problem as Leader Election (the classic one, requiring knowledge of$n$- as is our first protocol) or Revocable Leader Election, and present a new polynomial time and message complexity Revocable Leader Election algorithm in the setting without knowledge of network size. We analyze time and message complexity of our protocols in the CONGEST model of communication.

This paper studies the Contention resolution problem on a shared channel (also known as a multiple access channel). A set of$n$stations are connected to a common device and are able to communicate by transmitting and listening. Each station may have a message to broadcast. At any round, a transmission is successful if and only if exactly one station is transmitting at that round. Simultaneous transmissions interfere one another and, as a result, the respective messages are lost. The Contention resolution is the fundamental problem of scheduling the transmissions into rounds in such a way that any station delivers successfully its message on the channel. We consider a general dynamic distributed setting. We assume that the stations can join (or be activated on) the channel at arbitrary times (dynamic scenario). This has to be contrasted with the simplified static scenario, in which all stations are assumed to be activated simultaneously. We also assume that the stations are not able to detect whether a collision among simultaneous transmissions occurred (model without collision detection). Finally, there is no global clock in the system: each station measures the time using its own local clock which starts when the station is activated and is possibly out of sync with respect to the other stations. We study non-adaptive deterministic distributed algorithms for the contention resolution problem and assess their efficiency both in terms of channel utilization (also called throughput) and energy consumption. While this topic has been quite extensively examined for randomized algorithms, this is, to the best of our knowledge, the first paper to discuss to which extent deterministic contention resolution algorithms can be efficient in terms of both channel utilization and energy consumption. Our results imply an exponential separation gap between static and dynamic setting with respect to channel utilization. We also show that the knowledge of the number of participating stations k (or an upper bound on it) has a substantial impact on the energy consumption.

A majority of research in communication in wireless networks is devoted to maximizing information flow, improving connectivity, or making the system robust against physical perturbations such as jamming. In this work we study how intentional jamming can be used for assuring privacy of wireless communication under the popular Signal-to-Interference-plus- Noise-Ratio (SINR) model. The considered problem, called Zone-restriction with Max-coverage, is as follows: how to place a number of jamming stations in order to generate interference that block the signal of given genuine stations in a specified restricted area, i.e., by making the SINR value of the genuine stations’ signal below a pre-defined threshold in that area. In the construction of algorithms, we aim at optimizing both the accuracy – by minimizing the impact of the jamming stations to the area of genuine communication and by maximizing their influence to the area that should be jammed, as well as the energy consumption of the jamming stations. We present several solutions in various settings of the network, which often lead to challenging analysis even in relatively simple cases. Among others, we show that, surprisingly, it is possible to jam arbitrarily large areas by jammers using total energy arbitrarily close to zero.

How to reach consensus on an average value in a dynamic crowd without revealing identity? In this work, we study the problem of Average Network Consensus in Anonymous Dynamic Networks (ADN). Network dynamicity is specified by the sequence of topology-graph isoperimetric numbers occurring over time, which we call the isoperimetric dynamicity of the network. The consensus variable is the average of values initially held by nodes, which is customary in the Network-consensus literature. Given that having an algorithm to compute the average one can compute the network size (i.e. the Counting problem) and viceversa, we further focus on the latter.

We examine deterministic contention resolution on a multiple-access channel when packets are injected continuously by an adversary to the buffers of n available stations in the system, arbitrarily at rate at most ρ packets per round. The aim is to successfully transmit packets and maintain system stability, that is, bounded queues, even in infinite executions. The largest injection rate for which a given contention resolution algorithm guaranties stability is called (algorithm's) throughput. In contrast to the previous work, we consider a channel in which there is a strict limit k on the total number of stations allowed to transmit or listen to the channel at a given time, that can never be exceeded; we call such channel a k-restrained channel. We construct adaptive and full sensing protocols with optimal throughput 1 and almost optimal throughput 1-1/n, respectively, in a constant-restrained channel. By contrast, we show that restricted protocols based on schedules known in advance obtain throughput at most min{[k/n], [1/3logn]}. We also support our theoretical analysis by simulation results of our algorithms in systems of moderate, realistic sizes and scenarios, and compare them with popular backoff protocols.

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).

We study Consensus in synchronous networks with arbitrary connected topologies. Nodes may be faulty, in the sense of either Byzantine or proneness to crashing. Let t denote a known upper bound on the number of faulty nodes, and D_s denote a maximum diameter of a network obtained by removing up to s nodes, assuming the network is (s+1)-connected. We give an algorithm for Consensus running in time t + D_{2t} with nodes subject to Byzantine faults. We show that, for any algorithm solving Consensus for Byzantine nodes, there is a network G and an execution of the algorithm on this network that takes Ω(t + D_{2t}) rounds. We give an algorithm solving Consensus in t + D_{t} communication rounds with Byzantine nodes using authenticated messages of polynomial size. We show that for any numbers t and d > 4, there exists a network G and an algorithm solving Consensus with Byzantine nodes using authenticated messages in fewer than t + 3 rounds on G, but all algorithms solving Consensus without message authentication require at least t + d rounds on G. This separates Consensus with Byzantine nodes from Consensus with Byzantine nodes using message authentication, with respect to asymptotic time performance in networks of arbitrary connected topologies, which is unlike complete networks. Let f denote the number of failures actually occurring in an execution and unknown to the nodes. We develop an algorithm solving Consensus against crash failures and running in time 𝒪(f + D_{f}), assuming only that nodes know their names and can differentiate among ports; this algorithm is also communication-efficient, by using messages of size 𝒪(mlog n), where n is the number of nodes and m is the number of edges. We give a lower bound t+D_t-2 on the running time of any deterministic solution to Consensus in (t+1)-connected networks, if t nodes may crash.

Starting with with work of Michail et al., the problem of Counting the number of nodes in Anonymous Dynamic Networks has attracted a lot of attention. The problem is challenging because nodes are indistinguishable (they lack identifiers and execute the same program), and the topology may change arbitrarily from round to round of communication, as long as the network is connected in each round. The problem is central in distributed computing, as the number of participants is frequently needed to make important decisions, including termination, agreement, synchronization, among others. A variety of distributed algorithms built on top of mass-distribution techniques have been presented, analyzed, and experimentally evaluated; some of them assumed additional knowledge of network characteristics, such as bounded degree or given upper bound on the network size. However, the question of whether Counting can be solved deterministically in sub-exponential time remained open. In this work, we answer this question positively by presenting M ethodical C ounting , which runs in polynomial time and requires no knowledge of network characteristics. Moreover, we also show how to extend M ethodical C ounting to compute the sum of input values and more complex functions without extra cost. Our analysis leverages previous work on random walks in evolving graphs, combined with carefully chosen alarms in the algorithm that control the process and its parameters. To the best of our knowledge, our Counting algorithm and its extensions to other algebraic and Boolean functions are the first that can be implemented in practice with worst-case guarantees.

Millimeter wave (mmWave) communication not only provides ultra-high speed radio access but is also ideally suited for efficient and flexible wireless backhauling. Specifically for dense deployments, a mmWave macro base station (MBS) that serves a large number of mmWave micro base stations (μBSs) is much more cost effective than legacy cellular architectures which connect μBSs to the core network through fibers. In addition, μBSs can cooperate with each other by acting as relay nodes. The directional nature of mmWave communication allows for spatial reuse, even in the presence of interference, which can be exploited to optimize mmWave wireless backhaul performance. The optimization opportunistically prioritizes the use of good connections at the MBS and further leverages compact and concurrent transmissions between μBS. Relays and directional antennas speed up communication, but increase the complexity of the scheduling problem. In this work, we study the mmWave backhaul scheduling problem and derive an MILP formulation for it as well as upper and lower bounds. We prove that the problem is NP-hard and can be approximated, but only if interference is negligible. By means of numerical simulations, we compare theoretical results with heuristics in small system sizes. Results validate the analysis and demonstrate the high performance of our heuristics in realistic cellular settings.

Counting the number of nodes in {Anonymous Dynamic Networks} is enticing from an algorithmic perspective: an important computation in a restricted platform with promising applications. Starting with Michail, Chatzigiannakis, and Spirakis [Michail et al., 2013], a flurry of papers sped up the running time guarantees from doubly-exponential to polynomial [Dariusz R. Kowalski and Miguel A. Mosteiro, 2018]. There is a common theme across all those works: a distinguished node is assumed to be present, because Counting cannot be solved deterministically without at least one. In the present work we study challenging questions that naturally follow: how to efficiently count with more than one distinguished node, or how to count without any distinguished node. More importantly, what is the minimal information needed about these distinguished nodes and what is the best we can aim for (count precision, stochastic guarantees, etc.) without any. We present negative and positive results to answer these questions. To the best of our knowledge, this is the first work that addresses them.

A shared communication channel (also known as a multiple access channel) is among the most popular and widely studied models of communication and distributed computing. In this model, stations are able to communicate by transmitting and listening to a shared channel. A fundamental problem, called contention resolution, is to allow any station to successfully deliver its message by resolving the conflicts that arise when several stations transmit simultaneously on the channel. Despite a long history, many fundamental questions remain open in the realistic scenario when up to k stations out of n join the channel at different times. In this work we explore the impact of asynchrony, knowledge (or linear estimate) of contenders, and acknowledgments, on latency and channel utilization of non-adaptive deterministic algorithms. We show that if the number of contenders k (or a linear upper bound on it) is known and the stations switch-off after acknowledgment of their successful transmissions, the channel admits efficient solutions. In the same settings, we show that the ignorance of contention k makes the channel nearly quadratically less efficient, even if the stations could switch-off after acknowledgments. We present an algorithm which nearly matches this complexity (for unknown k) which is achieved even if acknowledgments are not provided. We show how the above algorithm could be further improved if stations could switch off upon acknowledgment. Surprisingly, our results imply an exponential impact of knowledge of contention on deterministic utilization of asynchronous channel by deterministic algorithms - it is known that for synchronized channel this feature does not influence asymptotically the channel utilization. The second implication concerns the impact of acknowledgments - they exponentially improve deterministic channel utilization if (some estimate of) k is known, unlike in the case of randomized algorithms where the improvement is only polynomial, while they are not particularly helpful in case of unknown contention. Finally, note that non-adaptive algorithms use fixed transmission schedules, which could be naturally translate into codes in the radio or beeping model - in this context our results indicate under which conditions such codes could be efficient.

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.

We consider broadcasting on multiple access channels under adversarial packet injection modeled by leaky-bucket adversaries. We study the impact of individual injection rates on latency, as compared to general leaky bucket adversaries. It is demonstrated that some broadcast algorithms designed for ad-hoc channels have bounded latency for wider ranges of injection rates when executed on channels with a fixed number of stations against adversaries that can activate at most one station per round. We give outcomes of simulations comparing the performance of broadcast algorithms against randomized adversaries, including comparisons to randomized backoff algorithms.

We study the problem of scheduling n similar jobs on m machines, with respect to the fact that jobs are dependent and some of them must be performed before others. Dependencies between jobs are modeled as a partial order relation. Machines are prone to crashes, induced by an Adaptive f-Bounded adversary who can fail up to f machines, where . Communication takes place via a Multiple-Access Channel (MAC), which restricts simultaneous transmissions. We show an optimal solution (with respect to total work of all machines) for partially ordered sets of jobs forming chains and an algorithm and lower bound for trees.

We investigate routing on networks modeled as multiple access channels, when packets are injected continually. An energy cap is a component of the system, understood as a bound on the number of stations that can be switched on simultaneously. Each packet is injected into some station and needs to be delivered to its destination station via the channel. A station has to be switched on in order to receive a packet when it is heard on the channel. Each station manages when it is switched on and off by way of a programmable wake-up mechanism, which is scheduled by a routing algorithm. Packet injection is governed by adversarial models that determine upper bounds on injection rates and burstiness. We develop deterministic distributed routing algorithms and assess their performance in the worst-case sense. An algorithm knows the number of stations but does not know the adversary. One of the algorithms maintains bounded queues for the maximum injection rate 1 subject only to the energy cap 3. This energy cap is provably optimal, in that obtaining the same throughput with the energy cap 2 is impossible. We give algorithms subject to the minimum energy cap 2 that have latency polynomial in the total number of stations~n for each fixed adversary of injection rate less than 1. An algorithm is k-energy-oblivious if at most k stations are switched on in a round and for each station the rounds when it will be switched on are determined in advance. We give a k-energy-oblivious algorithm that has packet delay O(n) for adversaries of injection rates less than (k-1)/(n-1), and show that there is no k-energy-oblivious stable algorithm against adversaries with injection rates greater than k/n. An algorithm routes directly when each packet makes only one hop from the station into which it is injected straight to its destination. We give a k-energy-oblivious algorithm routing directly, which has latency O(n^2/k) for adversaries of sufficiently small injection rates that are O(k^2/n^2). We develop a k-energy-oblivious algorithm routing directly, which is stable for injection rate k(k-1)/n(n-1), and show that no k-energy-oblivious algorithm routing directly can be stable against adversaries with injection rates greater than k(k-1)/n(n-1).

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). {}

An execution of a distributed algorithm is often seen as a game between the algorithm and a conceptual adversary causing specific distractions to the computation. In this work we define a class of ordered adaptive adversaries, which cause distractions—in particular crashes—online according to some partial order of the participating stations, which is fixed by the adversary before the execution. We distinguish: Linearly-Ordered adversary, restricted by some pre-defined linear order of (potentially) crashing stations; Anti-Chain-Ordered adversary, previously known as the Weakly-Adaptive adversary, which is restricted by some pre-defined set of crash-prone stations (it can be seen as an ordered adversary with the order being an anti-chain, i.e., a collection of incomparable elements, consisting of these stations); k-Thick-Ordered adversary restricted by partial orders of stations with a maximum anti-chain of size k. We initiate a study of how they affect performance of algorithms. For this purpose, we focus on the well-known Do-All problem of performing t tasks by p synchronous crash-prone stations communicating on a shared channel. The channel restricts communication by the fact that no message is delivered to the operational stations if more than one station transmits at the same time. The question addressed in this work is how the ordered adversaries controlling crashes of stations influence work performance, defined as the total number of available processor steps during the whole execution and introduced by Kanellakis and Shvartsman (Distrib Comput 5(4):201–217, 1992) in the context of Write-All algorithms. The first presented algorithm solves the Do-All problem with work $${\mathcal {O}}(t+p \sqrt{t}\log p)$$ against the Linearly-Ordered adversary. Surprisingly, the upper bound on performance of this algorithm does not depend on the number of crashes f and is close to the absolute lower bound $$\varOmega (t+p\sqrt{t})$$ proved in Chlebus et al. (Distrib Comput 18(6):435–451, 2006). Another algorithm is developed against the Weakly-Adaptive adversary. Work done by this algorithm is $$\mathcal {O}(t + p\sqrt{t} + p\min \left\{ p/(p-f),t\right\} \log p ),$$ which is close to the lower bound $$\varOmega (t + p\sqrt{t} + p\min \left\{ p/(p-f),t\right\} )$$ proved in [11] and answers the open questions posed there. We generalize this result to the class of k-Thick-Ordered adversaries, in which case the work of the algorithm is bounded by $$\mathcal {O}(t + p\sqrt{t} + p\min \left\{ p/(p-f),k,t\right\} \log p ).$$ We complement this result by proving the almost matching lower bound $$\begin{aligned} \varOmega (t + p\sqrt{t} + p\min \left\{ p/(p-f),k,t\right\} ). \end{aligned}$$ Independently from the results for the ordered adversaries, we consider a class of delayed adaptive adversaries, which could see random choices with some delay. We present an algorithm that works efficiently against the 1-RD adversary, which could see random choices of stations with one round delay, achieving close to optimal $${\mathcal {O}}(t+p \sqrt{t}\log ^{2} p)$$ work complexity. This shows that restricting the adversary by not allowing it to react on random decisions immediately makes it significantly weaker, in the sense that there is an algorithm achieving (almost) optimal work performance.

We consider deterministic distributed communication in wireless ad hoc networks of identical devices in the SINR model without predefined infrastructure. Most algorithmic results in this model rely on additional features or capabilities, e.g., randomization, access to geographic coordinates, power control, carrier sensing with various precision of measurements, and interference cancellation. We study a pure scenario, when no such features are available.

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.

A shared channel, also called multiple-access channel, is one of the fundamental communication models. Autonomous entities communicate over a shared medium, and one of the main challenges is how to efficiently resolve collisions occurring when more than one entity attempts to access the channel at the same time. In this work we explore the impact of asynchrony, knowledge (or linear estimate) of the number of contenders, and acknowledgments, on both latency and channel utilization for the Contention resolution problem with non-adaptive deterministic algorithms.

We consider the problems of online and stochastic packet queueing in a distributed system of n nodes with queues, where the communication between the nodes is done via a multiple access channel. In the online setting, in each round, an arbitrary number of packets can be injected to nodes’ queues. Two measures of performance are considered: the total number of packets in all queues, called the total load , and the maximum queue size, called the maximum load . We develop a deterministic distributed algorithm that is asymptotically optimal with respect to both complexity measures, in a competitive way. More precisely, the total load of our algorithm is bigger than the total load of any other algorithm, including centralized online solutions, by only an additive term of O ( n 2 ), whereas the maximum queue size of our algorithm is at most n times bigger than the maximum queue size of any other algorithm, with an extra additive O ( n ). The optimality for both measures is justified by proving the corresponding lower bounds, which also separates nearly exponentially distributed solutions from the centralized ones. Next, we show that our algorithm is also stochastically stable for any expected injection rate smaller or equal to 1. This is the first solution to the stochastic queueing problem on a multiple access channel that achieves such stability for the (highest possible) rate equal to 1.

In this paper we consider the mutual exclusion problem on a multiple access channel. Mutual exclusion is one of the fundamental problems in distributed computing. In the classic version of this problem, n processes execute a concurrent program that occasionally triggers some of them to use shared resources, such as memory, communication channel, device, etc. The goal is to design a distributed algorithm to control entries and exits to/from the shared resource (also called a critical section), in such a way that at any time, there is at most one process accessing it. In our considerations, the shared resource is the shared communication channel itself (multiple access channel), and the main challenge arises because the channel is also the only mean of communication between these processes. We consider both the classic and a slightly weaker version of mutual exclusion, called $$\varepsilon $$ -mutual-exclusion, where for each period of a process staying in the critical section the probability that there is some other process in the critical section is at most $$\varepsilon $$ . We show that there are channel settings, where the classic mutual exclusion is not feasible even for randomized algorithms, while the $$\varepsilon $$ -mutual-exclusion is. In more relaxed channel settings, we prove an exponential gap between the makespan complexity of the classic mutual exclusion problem and its weaker $$\varepsilon $$ -exclusion version. We also show how to guarantee fairness of mutual exclusion algorithms, i.e., that each process that wants to enter the critical section will eventually succeed.

We consider single-hop radio networks with multiple channels as a model of wireless networks. There are n stations connected to b radio channels that do not provide collision detection. A station uses all the channels concurrently and independently. Some k stations may become active spontaneously at arbitrary times. The goal is to wake up the network, which occurs when all the stations hear a successful transmission on some channel. Duration of a waking-up execution is measured starting from the first spontaneous activation. We present a deterministic algorithm that wakes up a network in O(klog1/b⁡klog⁡n) time, where k is unknown. We give a deterministic scalable algorithm for the special case when b>dlog⁡log⁡n, for some constant d>1, which wakes up a network in O(kblog⁡nlog⁡(blog⁡n)) time, with k unknown. This algorithm misses time optimality by at most a factor of O(log⁡n(log⁡b+log⁡log⁡n)), because any deterministic algorithm requires Ω(kblog⁡nk) time. We give a randomized algorithm that wakes up a network within O(k1/bln⁡1ϵ) rounds with a probability that is at least 1−ϵ, for any 0<ϵ<1, where k is known. We also consider a model of jamming, in which each channel in any round may be jammed to prevent a successful transmission, which happens with some known parameter probability p, independently across all channels and rounds. For this model, we give two deterministic algorithms for unknown k: one wakes up a network in time O(log−1⁡(1p)klog⁡nlog1/b⁡k), and the other in time O(log−1⁡(1p)kblog⁡nlog⁡(blog⁡n)) when the inequality b>log⁡(128blog⁡n) holds, both with probabilities that are at least 1−1/poly(n).

We consider the task of assigning time slots on a user-dependent and time-varying wireless channel. This scheduling problem occurs in cellular networks due to the presence of channel fading and user mobility. We introduce a simple notion of global fairness, where each of n users is guaranteed a 1/(n + ε) fraction of its total possible throughput, for some approximation parameter ε ≥ 0, and study its limitations from theoretical and experimental perspectives. We formally prove that a slight modification of the standard proportional fair algorithm satisfies the global fairness constraint. To the best of our knowledge, this is the first formal analysis providing global fairness property to the channel in any execution and any channel conditions. As confirmed by our simulations, our global fairness constraint is in fact satisfied by a wide class of algorithms. Our framework allows optimization of an arbitrary metric subject to the global fairness constraint. In particular, we have analyzed a variant of the provably fair algorithm that optimizes the total throughput. It turned out that the channel utilization of this algorithm is significantly better than that of the classical Proportional Fair algorithm.

This paper studies the task of setting up ad hoc wireless networks. In such networks, it is often the case that nodes become active at different times, without coordination or knowledge about network topology. We consider the following tasks: wake-up, clock synchronization, leader election, and multimessage broadcast. We show how to achieve these goals in scalable O(D polylog(n)) time. As a tool we define and give a solution to a quasi-backbone problem, which aims to set up transmission probabilities at nodes in a way that they can be efficiently used to solve other tasks. Our results are obtained by minimalistic algorithms, which do not require power control or carrier sensing capabilities, use very small energy, local computation and memory. Moreover, unlike many previous work, they remain scalable even if the network is not highly connected.

We consider the impact of scheduling disciplines on performance of routing in the framework of adversarial queuing. We propose an adversarial model which reflects stalling of packets due to transient failures and explicitly incorporates feedback produced by a network when packets are stalled. This adversarial model provides a methodology to study stability of routing protocols when flow-control and congestion-control mechanisms affect the volume of traffic. We show that any scheduling policy that is universally stable, in the regular model of routing that additionally allows packets to have two priorities, remains stable in the proposed adversarial model. © 2015 Wiley Periodicals, Inc.NETWORKS, Vol. 66(2), 88–97 2015

A classical problem in addressing a decentralized multiple-access channel is resolving conflicts when a set of stations attempt to transmit at the same time on a shared communication channel. In a static scenario, i.e., when all stations are activated simultaneously, Komlós and Greenberg [IEEE Trans. Inform. Theory, 31 (1985), pp. 302--306] in their seminal work showed that it is possible to resolve the conflict among $k$ stations from an ensemble of $n$, with a nonadaptive deterministic algorithm in time $O(k + k \log(n/k))$ in the worst case. In this paper we show that in a dynamic scenario, when the stations can join the channel at arbitrary rounds, there is a nonadaptive deterministic algorithm guaranteeing a successful transmission for each station in only a slightly bigger time: $O(k\log n\log\log n)$ in the worst case. This almost matches the $\Omega(k\log n/\log k)$ lower bound by Greenberg and Winograd [J. ACM, 32 (1985), pp. 589--596] that holds even in much stronger settings: for adaptive algorithms, in the static scenario, and with additional channel feedback--collision detection. In terms of channel utilization, our result implies throughput, understood as the average number of successful transmissions per time unit, $\Omega(1/(\log n\log\log n))$ on the dynamic deterministic channel.

In this work we address the question how important is the knowledge of geometric location and network density to the efficiency of (distributed) wireless communication in ad hoc networks. We study fundamental communication task of broadcast and develop well-scalable, randomized algorithms that do not rely on GPS information, and which efficiency formulas do not depend on how dense the geometric network is. We consider two settings: with and without spontaneous wake-up of nodes. In the former setting, in which all nodes start the protocol at the same time, our algorithm accomplishes broadcast in O(D log n + log2 n) rounds under the SINR model, with high probability (whp), where D is the diameter of the communication graph and n is the number of stations. In the latter setting, in which only the source node containing the original message is active in the beginning, we develop a slightly slower algorithm working in O(D log2 n) rounds whp. Both algorithms are based on a novel distributed coloring method, which is of independent interest and potential applicability to other communication tasks under the SINR wireless model.

In much of the theoretical literature on global broadcast algorithms for wireless networks, issues of message dissemination are considered together with issues of contention management. This combination leads to complicated algorithms and analysis, and makes it difficult to extend the work to more difficult communication problems. In this paper, we present results aimed at simplifying such algorithms and analysis by decomposing the treatment into two levels, using abstract “MAC layer” specifications to encapsulate contention management. We use two different abstract MAC layers: the basic layer of [1], [2] and a new probabilistic layer. We first present a typical randomized contention-management algorithm for a standard graph-based radio network model and show that it implements both abstract MAC layers. Then we combine this algorithm with greedy algorithms for single-message and multi-message global broadcast and analyze the combinations, using both abstract MAC layers as intermediate layers. Using the basic MAC layer, we prove a bound of ODlogn∊log(Δ) for the time to deliver a single message everywhere with probability 1 − ∊, where D is the network diameter, n is the number of nodes, and Δ is the maximum node degree. Using the probabilistic layer, we prove a bound of OD+logn∊log(Δ), which matches the best previously-known bound for single-message broadcast over the physical network model. For multi-message broadcast, we obtain bounds of O(D+kΔ)logn∊log(Δ) using the basic layer and OD+kΔlogn∊log(Δ) using the probabilistic layer, for the time to deliver a message everywhere in the presence of at most k concurrent messages.

Multiple access channel is a well-known communication model that deploys properties of many network systems, such as Aloha multi-access systems, local area Ethernet networks, satellite communication systems, packet radio networks. The fundamental aspect of this model is to provide efficient communication and computation in the presence of restricted access to the communication resource: at most one station can successfully transmit at a time, and a wasted round occurs when more than one station attempts to transmit at the same time. In this work we consider the problem of contention resolution in a multiple access channel in a realistic scenario when up to k stations out of n join the channel at different times. The goal is to let at least one station to transmit alone, which results in successful delivery of the message through the channel. We present three deterministic algorithms: two of them working under some constrained scenarios, and achieving asymptotically optimal time complexity Θ(k log(n/k)), while the third general algorithm accomplishes the goal in time O(k logn log log n).

This paper studies the problem of Byzantine consensus in a synchronous message-passing system of n processes. The first deterministic algorithm, and also the simplest in its principles, was the Exponential Information Gathering protocol (EIG) proposed by Pease, Shostak and Lamport in [19]. The algorithm requires processes to send exponentially long messages. Many follow-up works reduced the cost of the algorithm. However, they had to either lower the maximum number of faulty processes t from the optimal range t < n/3 to some smaller range of t [4, 11, 18], or increase the maximum worst-case number of rounds needed for termination (the lower bound being t + 1) [3, 9, 20].

We study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. We show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. The algorithmic techniques proposed in this article can be used for improving the message complexity of distributed algorithms that rely on an all-to-all message exchange paradigm and are designed for an asynchronous environment. As an example, we show how to improve the message complexity of asynchronous randomized consensus.

We study deterministic broadcasting on multiple access channels when packets are injected continuously. The quality of service is considered in the framework of adversarial queuing. An adversary is determined by injection rate and burstiness, the latter denoting the number of packets that can be injected simultaneously in a round. We consider only injection rates that are less than 1. A protocol is stable when the numbers of packets in queues stay bounded at all rounds, and it is of fair latency when waiting times of packets in queues are O (burstiness/rate). For channels with collision detection, we give a full-sensing protocol of fair latency for injection rates that are at most 1 2(⌈lg n ⌉ + 1), where n is the number of stations, and show that fair latency is impossible to achieve for injection rates that are ω (1 log n ). For channels without collision detection, we present a full-sensing protocol of fair latency for injection rates that are at most 1 c lg 2 n , for some c > 0. We show that there exists an acknowledgment-based protocol that has fair latency for injection rates that are at most 1 cn lg 2 n , for some c > 0, and develop an explicit acknowledgment-based protocol of fair latency for injection rates that are at most 1 27 n 2 ln n . Regarding impossibility to achieve just stability by restricted protocols, we prove that no acknowledgment-based protocol can be stable for injection rates larger than 3 1 + lg n .

Epidemic gossip has proven a reliable and efficient technique for sharing information in a distributed network. Much of the reliability and efficiency derives from processes collaborating, sharing the work of distributing information. As a result of this collaboration, processes may receive information that was not originally intended for them. For example, a process may act as an intermediary, aggregating and forwarding messages from some set of sources to some set of destinations. But what if rumors are confidential? In that case, only processes that were originally intended to receive a rumor should be allowed to learn the rumor. This blatantly contradicts the basic premise of epidemic gossip, which assumes that processes can collaborate. In fact, if only processes in a rumor's "destination set" participate in gossiping that rumor, we show that high message complexity is unavoidable. We propose a scheme in which each rumor is broken into multiple fragments using a simple coding scheme: any given fragment provides no information about the rumor, while together, they allow the original rumor to be reassembled. The processes collaborate in disseminating the rumor fragments while ensuring that no process receives all the fragments of a rumor unless it is in that rumor's destination set. Our solution operates in an environment where rumors are dynamically and continuously injected into the system and processes are subject to crashes and restarts. In addition, the scheme presented can tolerate a moderate amount of collusion among curious processes without too large an increase in cost.

Multiple-message broadcast, or k-broadcast, is one of the fundamental problems in network communication. In short, there are k packets distributed across the network, each of them has to be delivered to all other nodes. We consider this task in the model of multi-hop radio network, in which n nodes interact by transmitting and receiving messages. A message transmitted at a round reaches all neighbors of the transmitter at the end of the same round, but may not be successfully received by some, or even all, of these neighbors. More specifically, a node receives a message at a round if this is the only message that has reached this node in this round. Due to this specific interference-prone nature of radio networks, many communication tasks become more challenging and more costly than in other types of networks, especially in ad-hoc setting in which each node knows only its own id and linear estimates on the basic network parameters, such as the number of nodes n, diameter D and maximum node degree Δ. We design a new randomized k-broadcast algorithm combining the bestof two worlds: efficient randomized transmission schedules and network coding. We show that our algorithm accomplishes multi-broadcast in O(log Δ) amortized number of communication rounds per packet, with high probability. This improves over the best previous solution of Bar-Yehuda, Israeli and Itai, which guarantees only O(log Δ log n) of amortized number of rounds per packet, with high probability.

We consider deterministic feasibility and time complexity of two fundamental tasks in distributed computing: consensus and mutual exclusion. Processes have different labels and communicate through a multiple access channel. The adversary wakes up some processes in possibly different rounds. In any round, every awake process either listens or transmits. The message of a process i is heard by all other awake processes, if i is the only process to transmit in a given round. If more than one process transmits simultaneously, there is a collision and no message is heard. We consider three characteristics that may or may not exist in the channel: collision detection (listening processes can distinguish collision from silence), the availability of a global clock showing the round number, and the knowledge of the number n of all processes. If none of the above three characteristics is available in the channel, we prove that consensus and mutual exclusion are infeasible; if at least one of them is available, both tasks are feasible, and we study their time complexity. Collision detection is shown to cause an exponential gap in complexity: if it is available, both tasks can be performed in time logarithmic in n, which is optimal, and without collision detection both tasks require linear time. We then investigate both consensus and mutual exclusion in the absence of collision detection, but under alternative presence of the two other features. With global clock, we give an algorithm whose time complexity linearly depends on n and on the wake-up time, and an algorithm whose complexity does not depend on the wake-up time and differs from the linear lower bound only by a factor O(log2n). If n is known, we also show an algorithm whose complexity differs from the linear lower bound only by a factor O(log2n).

We are given $n$ stations of which $k$ are active, while the remaining $n-k$ are asleep. The active stations communicate via a multiple-access channel. If a subset $Q$ of active stations transmits in the same round, all active stations can recognize from the signal strength how many stations have transmitted (i.e., they learn the size of set $Q$), even though they may not be able to decode the contents of transmitted messages. The goal is to let each active station to learn about the set of all active stations. It is well known that $\Theta(k\log_{k+1} n)$ rounds are enough, even for non-adaptive deterministic algorithms. A natural interesting generalization arises when we are required to identify a subset of $m\leq k$ active stations. We show that while for randomized or for adaptive deterministic algorithms $O(m \log_{m+1} n)$ rounds are sufficient, the non-adaptive deterministic counterpart still requires $\Theta(k\log_{k+1} n)$ rounds, therefore, finding any subset of active stations is not easier than finding all of them by a non-adaptive deterministic algorithm. We prove our results in the more general framework of combinatorial search theory, where the problem of identifying active stations on a multiple-access channel can be viewed as a variant of the well-known counterfeit coin problem.

We study broadcasting on multiple access channels by deterministic distributed protocols. Data arrivals are governed by an adversary. The power of the adversary is constrained by the average rate of data injection and a bound on the number of different packets that can be injected in one round. The injection rate is at most 1, which forbids the adversary from overloading the channel. We consider a number of deterministic protocols. For each of them we give an upper bound on the worst-case packet latency, as a function of the constraints imposed on the adversary. We present results of experiments by simulations to compare packet latency of the deterministic protocols and of backoff-type randomized protocols. The experiments are carried out in a simulation environment that captures the burstiness of data injection and the resulting traffic by admissibility condition defined by the fraction of active stations and the rate of changing the status of active versus passive among the stations.

In this paper, we introduce the problem of Continuous Gossip in which rumors are continually and dynamically injected throughout the network. Each rumor has a deadline, and the goal of a continuous gossip protocol is to ensure good "Quality of Delivery," i.e., to deliver every rumor to every process before the deadline expires. Thus, a trivial solution to the problem of Continuous Gossip is simply for every process to broadcast every rumor as soon as it is injected. Unfortunately, this solution has a high per-round message complexity. Complicating matters, we focus our attention on a highly dynamic network in which processes may continually crash and recover. In order to achieve good per-round message complexity in a dynamic network, processes need to continually form and re-form coalitions that cooperate to spread their rumors throughout the network. The key challenge for a Continuous Gossip protocol is the ongoing adaptation to the ever-changing set of active rumors and non-crashed process. In this work we show how to address this challenge; we develop randomized and deterministic protocols for Continuous Gossip and prove lower bounds on the per-round message-complexity, indicating that our protocols are close to optimal.

We consider the problem of fault-tolerant agreement in a crash-prone synchronous system. We present a new randomized consensus algorithm that achieves optimal communication efficiency, using only O(n) bits of communication, and terminates in (almost optimal) time O(log n), with high probability. The same protocol, with minor modifications, can also be used in partially synchronous networks, guaranteeing correct behavior even in asynchronous executions, while maintaining efficient performance in synchronous executions. Finally, the same techniques also yield a randomized, fault-tolerant gossip protocol that terminates in O(log* n) rounds using O(n) messages (with bit complexity that depends on the data being gossiped).

In this paper we consider the mutual exclusion problem on a multiple access channel. Mutual exclusion is one of the fundamental problems in distributed computing. In the classic version of this problem, $n$ processes perform a concurrent program which occasionally triggers some of them to use shared resources, such as memory, communication channel, device, etc. The goal is to design a distributed algorithm to control entries and exits to/from the shared resource in such a way that in any time there is at most one process accessing it. We consider both the classic and a slightly weaker version of mutual exclusion, called $\ep$-mutual-exclusion, where for each period of a process staying in the critical section the probability that there is some other process in the critical section is at most $\ep$. We show that there are channel settings, where the classic mutual exclusion is not feasible even for randomized algorithms, while $\ep$-mutual-exclusion is. In more relaxed channel settings, we prove an exponential gap between the makespan complexity of the classic mutual exclusion problem and its weaker $\ep$-exclusion version. We also show how to guarantee fairness of mutual exclusion algorithms, i.e., that each process that wants to enter the critical section will eventually succeed.

This paper presents an efficient protocol for reliably exchanging information in a single-hop, multi-channel radio network subject to unpredictable interference. We model the interference by an adversary that can simultaneously disrupt up to t of the C available channels. We assume no shared secret keys or third-party infrastructure. The running time of our protocol depends on the gap between C and t: when the number of channels C = Q,(t2), the running time is linear; when only C = t +1 channels are available, the running time is exponential. We prove that exponential-time is unavoidable in the latter case. At the core of our protocol lies a combinatorial function, possibly of independent interest, described for the first time in this paper: the multi-selector. A multi-selector generates a sequence of channel assignments for each device such that every sufficiently large subset of devices is partitioned onto distinct channels by at least one of these assignments.

We study communication complexity of consensus in synchronous message-passing systems with processes prone to crashes. The goal in the consensus problem is to have all the nonfaulty processes agree on a common value from among the input ones, after each process has been initialized with a binary input value. The system consists of n processes and it is assumed that at most t < n processes crash in an execution. A consensus algorithm that tolerates up to t failures is called fast when its time complexity is O(t). All the previously known fast deterministic consensus solutions sent Ω(n2) bits in messages. We give a fast deterministic consensus algorithm that has processes send only O(n log4 n) bits. In our solution, processes exchange messages according to topologies of overlay graphs that have suitable robustness and connectivity properties related to graph expansion.

We consider bit communication complexity of binary consensus in synchronous message passing systems with processes prone to crashes. A distributed algorithm is locally scalable when each process contributes to the complexity measure an amount that is poly-logarithmic in the size~n of the system, and it is globally scalable when the average contribution per process to the complexity measure is such. We show that consensus can be solved by a randomized algorithm that is locally scalable with respect to both time and bit communication complexities against oblivious adversaries. If a bound t on the number of crashes is a constant fraction of the number n of processes then our randomized consensus solution terminates in the expected O(log n) time while the expected number of bits that each process sends and receives is O(log n). Our solution uses overlay networks with topologies that are explicitly defined and have suitable connectivity and robustness properties related to graph expansion. To compare our results to deterministic consensus solutions, it is known [20] that consensus cannot be solved deterministically by an algorithm that is locally scalable with respect to message complexity and that deterministic solutions globally scalable with respect to bit communication complexity exist for any bound t

The distributed setting of this paper is an asynchronous system consisting of n processes prone to crashes and a number of shared read-write registers. We consider problems regarding assigning integer values to processes in an exclusive way, in the sense that no integer is assigned to two distinct processes. In the problem of renaming, any k ≤ n processes, that hold original names from a range [N]={1,...,N}, contend to acquire unique integers as new names in a smaller range [M] using some r shared registers. When k and N are known, our wait-free solution operates in O(log k (log N + log k log log N)) local steps, for M=O(k), and with r=O(k log(N/k)) auxiliary shared registers. Processes obtain new names by exploring their neighbors in bipartite graphs of suitable expansion properties, with nodes representing names and processes competing for the name of each visited node. We show that 1+min{k-2,log2r(N/2M)} local steps are required in the worst case to wait-free solve renaming, when k and N are known and r and M are given constraints. We give a fully adaptive solution, with neither k nor N known, having M=8k-lg k-1 as a bound on the range of new names, operating in O(k) steps and using O(n2) registers. We apply renaming algorithms to obtain solutions to the Store&Collect problem. When both k and N are known, then storing can be performed in O(log k (log N + log k log log N)) steps and collecting in O(k) steps, for r=O(k log(N/k)) registers.

In this paper, we study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. In short, we show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. This latter fact implies that there exist message-efficient asynchronous (randomized) consensus protocols, in the context of an oblivious adversary.

We study the problem of waking up a collection of n processors connected by a multihop ad hoc ratio network with unknown topology, no access to a global clock, and no collision detection mechanism available. Each node in the network either wakes up spontaneously or gets activated by receiving a wake‐up signal from another node. All active nodes transmit the wake‐up signals according to a given protocol $\calW$. The running time of $\calW$ is the number of steps counted from the first spontaneous wake‐up until all nodes become activated. We provide two protocols for this problem. The first one is a deterministic protocol with running time $O(n^{5/3}\log n)$. Our protocol is based on a novel concept of a shift‐tolerant selector to which we refer as a (radio) synchronizer. The second protocol is randomized, and its expected running time is $O(D \log^2 n)$, where D is the diameter of the network. Subsequently we show how to employ our wake‐up protocols to solve two other communication primitives: leader election and clock synchronization.

We consider broadcasting on the multiple-access channel when packets are injected continuously. Multiple-access channel is a synchronous system with the properties that a single transmission at a round delivers the message to all nodes, while multiple simultaneous transmissions result in a conflict which prevents delivering messages to any among the recipients. The traditional approach to dynamic broadcasting has been concerned with stability of protocols under suitable stochastic assumptions about injection rates. We study deterministic protocols competing against adversaries restricted by injection rate and burstiness of traffic. Stability means that the number of packets in queues is bounded by a constant in any execution, for a given number of stations, protocol, and adversary. Strong stability denotes the property that the number of queued packets is proportional to the burstiness of traffic, that is, the maximum number of packets an adversary may inject simultaneously. There are three natural classes of protocols we consider. The weakest acknowledgement-based protocols have a station rely on its local clock and on a feedback from the channel during its own attempts of transmissions. Full-sensing protocols allow a station to rely on a global clock and to store the history of all the previous successes/failures of transmissions in the course of an execution. A station running an adaptive protocol can rely on a global clock, may add control bits to be piggybacked on messages, and may store the complete history of the feedback from the channel during an execution. It turns out that there is no adaptive broadcast protocol stable for the injection rate λ = 1 for the multiple-access channel with at least n ≥ 4 stations, even when collision detection is available. We show that a simple full-sensing protocol is universally stable, which means it can handle any constant injection rate λ ‹ 1 in a stable manner. A more involved full-sensing protocol is shown to be both universally stable and strongly-stable for injection rate ρ (n) ≤ 1over>d lg2 n, where d>0 is a sufficiently large constant and n is the number of stations. We show that there is an acknowledgement-based protocol that is strongly stable for injection rate ρ(n)≤ 1 d lg2 n, for a sufficiently large constant d0. Regarding the stability of acknowledgement-based protocols, we show that no such a protocol is stable for injection rate ρ(n)> 2 1+lg n. This implies that there are no universally stable acknowledgement-based protocols. We show that when collision detection is available, then a simple full-sensing protocol is both universally stable and strongly stable for injection rate ρ(n)≤ 1 2 lgn. As a complementary fact, we prove that no adaptive protocol for a channel with collision detection can be strongly stable for the injection rate that satisfies ρ (n) = ω (1 log n). This shows that the protocol we give is optimal with respect to injection rates it handles in a strongly stable manner.

We consider a game that models the creation of a wireless ad hoc network, where nodes are owned by selfish agents. We study a novel cost sharing model in which agents may pay for the transmission power of the other nodes. Each agent has to satisfy some connectivity requirement in the final network and the goal is to minimize its payment with no regard to the overall system performance. We analyze two fundamental connectivity games, namely broadcast and convergecast. We study pure Nash equilibria and quantify the degradation in the network performance called the price of anarchy resulting from selfish behavior. We derive asymptotically tight bounds on the price of anarchy for these games. We also study centralized network design. One of the most important problems in wireless ad hoc networks is the minimum-energy broadcast. Recently, there appeared many new applications such as real-time multimedia, battlefield communications and rescue operations that impose stringent end-to-end latency requirement on the broadcasting time. However, the existing algorithms that minimize the broadcasting energy tend to produce solutions with high latency. We consider the problem of bounded-hop broadcast. We present approximation algorithms for this problem.

Cooperation in distributed settings often involves activities that must be performed at least once by the participating processors. When processor failures or delays occur, it becomes unavoidable that some tasks are done redundantly. To make efficient use of the available processors, several distributed algorithms schedule the activities of the processors in terms of permutations of tasks that need to be performed at least once. This paper presents the first explicit practical deterministic construction of sets of permutations with certain combinatorial properties that immediately make practical several deterministic distributed algorithms. These algorithms solve a variety of problems, for example, cooperation in shared-memory and message-passing settings, and the gossip problem. Prior to this work, the most efficient algorithms for some of these problems were primarily of theoretical interest - they relied on permutations that are known to exist, but very expensive to construct, with the cost of construction being at least exponential in the size of the permutations. In this paper, the explicitly constructed permutations are ultimately used directly to produce practical instances of several classes of efficient deterministic algorithms. Most importantly, for all of these algorithms, the schedule construction cost is reduced from exponential to polynomial, at the expense of slight detuning, at most polylogarithmic, of the efficiency of these algorithms

A selection problem is among the basic communication primitives in networks. In this problem at most k participating stations have to broadcast successfully their messages. This problem is especially important in packet radio networks, where simultaneous transmissions of many neighbors result in interference among delivered messages. This work focuses on a single-hop radio networks with n-stations, also called a multiple access channel, and considers both static and dynamic versions of the selection problem. We construct a family of efficient oblivious deterministic protocols based on selectors, one of them with selection time cO(klog(n/k)), and the second explicit construction with selection time cO(k polylog n). The first construction matches the lower bound Ω(klog(n/k)) on deterministic oblivious selection, while the second one is the first known explicit construction better than Θ(k2). In the dynamic case we introduce the model of dynamic requests, called k-streams, which generalizes the static model and the dynamic requests with at most k participants. We prove that each oblivious deterministic protocol has latency Ω(k2/log k), and on the other hand we prove the existence of the oblivious deterministic protocol with latency cO(k2log n). In view of the existence of the randomized oblivious protocol with expected latency cO(klog(n/k)), this shows that randomization is substantially better than determinism for dynamic setting. Selection problem can be applied to implement other communication primitives --- we demonstrate it in the example of broadcast problem in multi-hop ad-hoc radio networks. In particular, we design an adaptive deterministic protocol broadcasting in time cO(nlog D) in every D-hop radio network of n-stations.

The Write-All problem for an asynchronous shared-memory system has the objective for the processes to update the contents of a set of shared registers, while minimizing the total number of read and write operations. First abstracted by Kanellakis and Shvartsman [12], Write-All is among the standard problems in distributed computing. The model consists of $n$ asynchronous processes and n registers, where every process can read and write to any register. Processes may fail by crashing. The most efficient previously known deterministic algorithm performs O(n1+ε) reads and writes, for an arbitrary fixed constant ε>0, and is due to Anderson and Woll [4]. This paper presents a new deterministic algorithm that performs O(n polylog n) read/write operations, thus improving the best previously known upper bound from polynomial to polylogarithmic in the average number of read/write operations per process. Using an approach to store and retrieve information about progress made in auxiliary registers, the novelty of the new algorithm is in using a family of multi-partite graphs with expansion properties to structure a set of registers as a graph and then have each asynchronous process explore a part of the graph according to its pattern of traversals. An explicit instantiation of our Write-All algorithm, based on best-known polynomial-time constructions of lossless expanders and a-expanding graphs, performs n • 2O(log3 log n) reads and writes. In this explicit solution to Write-All, the processes perform asymptotically less read/write operations than the most efficient non-explicit solution known before.

Distributed algorithms in dynamic networks often employ communication patterns whose purpose is to disseminate information among the participants. Gossiping is one form of such communication pattern. In dynamic settings, the set of participants can change substantially as new participants join, and as failures and voluntary departures remove those who have joined previously. A natural question for such settings is: how soon can newly joined nodes discover each other by means of gossiping? This paper abstracts and studies the join problem for dynamic systems that use all-to-all gossip. The problem is studied in terms of join-connectivity graphs where vertices represent the participants and where each edge represents one participant's knowledge about another. Ideally, such a graph has diameter one, i.e., all participants know each other. The diameter can grow as new participants join, and as failures remove edges from the graph. Gossip helps participants discover one another, decreasing the diameter. The results describe the lower and upper bounds on the number of communication rounds such that the participants who have previously joined discover one another, under a variety of assumptions about the joining and failures. For example, in the case when new participants join at multiple participants and participants may crash, the number of rounds cannot be bounded. In the more benign cases when the failures can be controlled or when new participants join at only one participant, the bound on rounds is shown to be logarithmic in the diameter of the initial configuration.

We present an improved algorithm to wake up a multi-hop ad-hoc radio network. The goal is to have all the nodes activated, when some of them may wake up spontaneously at arbitrary times and the remaining nodes need to be awoken by the already active ones. The best previously known wakeup algorithm was given by Chrobak, Gasieniec and Kowalski [11], and operated in time log n), where n is the number of nodes. We give an algorithm with the running time log n). This also yields better algorithms for other synchronization-type primitives, like leader election and localclocks synchronization, each with a time performance that di#ers from that of wake-up by an extra factor of O(log n) only, and improves the best previously known method for the problem by a factor of n . A wake-up algorithm is a schedule of transmissions for each node. It can be represented as a collection of binary sequences. Useful properties of such collections have been abstracted to define a (radio) synchronizer. It has been known that good radio synchronizers exist and previous algorithms [17, 11] relied on this. We show how to construct such synchronizers in polynomial time, from suitable constructible expanders. As an application, we obtain a wake-up protocol for a multiple-access channel that activates the network in time polylog n), where k is the number of stations that wake up spontaneously, and which can be found in time polynomial in n. We extend the notion of synchronizers to universal synchronizers. We show that there exist universal synchronizers with parameters that guarantee time log n) of wake-up.

The problem of performing n tasks on p asynchronous or undependable processors is a basic problem in distributed computing. This paper considers an abstraction of this problem called Write-All: using p processors write 1's into all locations of an array of size n. In this problem writing 1 abstracts the notion of performing a simple task. Despite substantial research, there is a dearth of efficient deterministic asynchronous algorithms for Write-All. Efficiency of algorithms is measured in terms of work that accounts for all local steps performed by the processors in solving the problem. Thus an optimal algorithm would have work Θ(n), however it is known that optimality cannot be achieved when p=Ω(n). The quest then is to obtain work-optimal solutions for this problem using a non-trivial, compared to n, number of processors p. Recently it was shown that optimality can be achieved using a non-trivial number M of processors, where M=4√n/log n. The new result in this paper significantly extends the range of processors for which optimality is achieved. The result shows that optimality can be achieved using close to M2 processors; more precisely, using (M log M)2-ε processors, for any ε > 0. Additionally, the new result uses only the atomic read/write memory, without resorting to using the test-and-set primitive that was necessary in the previous solution. This paper presents the algorithm and gives its analysis showing that the work complexity of the algorithm is O(n+p2+ε), which is optimal when p = O(n1/(2+ε)), while all prior deterministic algorithms require super-linear work when p=Ω(n1/4).

The Collect problem for an asynchronous shared-memory system has the objective for the processors to learn all values of a collection of shared registers, while minimizing the total number of read and write operations. First abstracted by Saks, Shavit, and Woll [37], Collect is among the standard problems in distributed computing, The model consists of $n$ asynchronous processes, each with a single-writer multi-reader register of a polynomial capacity. The best previously known deterministic solution performs O(n3/2log n) reads and writes, and it is due to Ajtai, Aspnes, Dwork, and Waarts [3]. This paper presents a new deterministic algorithm that performs O(n log7 n) read/write operations, thus substantially improving the best previous upper bound. Using an approach based on epidemic rumor-spreading, the novelty of the new algorithm is in using a family of expander graphs and ensuring that each of the successive groups of processes collect and propagate sufficiently many rumors to the next group. The algorithm is adapted to the Repeatable Collect problem, which is an on-line version. The competitive latency of the new algorithm is O(log7 n) vs. the much higher competitive latency O(√nlog n) given in [3]. A result of independent interest in this paper abstracts a gossiping game that is played on a graph and that gives its payoff in terms of expansion.

We consider broadcasting in radio networks, modeled as undirected graphs, whose nodes know only their own label and labels of their neighbors. In every step every node acts either as a transmitter or as a receiver. A node acting as a transmitter sends a message which can potentially reach all of its neighbors. A node acting as a receiver in a given step gets a message if and only if exactly one of its neighbors transmits in this step. Bar-Yehuda, Goldreich, and Itai [J. Comput. System Sci., 45 (1992), pp. 104--126] considered broadcasting in this model. They claimed a linear lower bound on the time of deterministic broadcasting in such radio networks of diameter 3. This claim turns out to be incorrect in this model (although it is valid in a more pessimistic model [R. Bar-Yehuda, O. Goldreich, and A. Itai, Errata Regarding "On the time complexity of broadcast in radio networks: An exponential gap between determinism and randomization," http://www.wisdom.weizmann.ac.il/mathusers/oded/p\_bgi.html, 2002]). We construct an algorithm that broadcasts in logarithmic time on all graphs from the Bar-Yehuda, Goldreich, and Itai paper (BGI). Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter $o(\log \log n)$. On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time $\Omega(\sqrt[4]{n})$ on these graphs. In view of the randomized algorithm from BGI, running in expected time ${\cal O}(D \log n + \log ^2 n)$ on all n-node graphs of diameter D (cf. also a recent ${\cal O}(D \log (n/D) + \log ^2 n)$-time algorithm from [D. Kowalski and A. Pelc, Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing, Boston, 2003, pp. 73--82; A. Czumaj and W. Rytter, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, MA, 2003, pp. 492--501]), our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting, under the considered model of radio communication.

We consider radio networks modeled as directed graphs. In ad hoc radio networks, every node knows only its own label and a linear bound on the size of the network but is unaware of the topology of the network or even of its own neighborhood. The fastest currently known deterministic broadcasting algorithm working for arbitrary n-node ad hoc radio networks has running time $\cO$ (n log2n). Our main result is a broadcasting algorithm working in time $\cO$ (n log n log D) for arbitrary n-node ad hoc radio networks of radius D. The best currently known lower bound on broadcasting time in ad hoc radio networks is $\Omega$ (n log D); hence our algorithm is the first to shrink the gap between bounds on broadcasting time in radio networks of arbitrary radius to a logarithmic factor. We also show a broadcasting algorithm working in time $\cO$ (n log D) for complete layeredn -node ad hoc radio networks of radius D. The latter complexity is optimal.

We consider distributed broadcasting in radio networks, modeled as undirected graphs, whose nodes have no information on the topology of the network, nor even on their immediate neighborhood. For randomized broadcasting, we give an algorithm working in expected time O(D log(n/D) + log2 n) in n-node radio networks of diameter D, which is optimal, as it matches the lower bounds of Alon et al. [1] and Kushilevitz and Mansour [14]. Our algorithm improves the best previously known randomized broadcasting algorithm of Bar-Yehuda, Goldreich and Itai [3], running in expected time O(D log n + log2 n). For deterministic broadcasting, we show the lower bound Ω(n(log n)/(log (n/D)))) on broadcasting time in n-node radio networks of diameter D. This implies previously known lower bounds of Bar-Yehuda, Goldreich and Itai [3] and Bruschi and Del Pinto [5], and is sharper than any of them in many cases. We also give an algorithm working in time O(n log n), thus shrinking -- for the first time -- the gap between the upper and the lower bound on deterministic broadcasting time to a logarithmic factor.

This paper considers the problem of performing tasks in asynchronous distributed settings. This problem, called Do-All, has been substantially studied in synchronous models, but there is a dearth of efficient algorithms for asynchronous message-passing processors. Do-All can be trivially solved without any communication by an algorithm where each processor performs all tasks. Assuming p processors and t tasks, this requires work Θ(p · t). Thus it is important to develop subquadratic solutions (when p and t are comparable) by trading computation for communication. Following the observation that it is not possible to obtain subquadratic work when the message delay d is substantial, e.g., d = Θ(t), this work pursues a message-delay-sensitive approach. Here the upper bounds on work and communication are given as functions of p, t, and d, the upper bound on message delays, however algorithms have no knowledge of d and they cannot rely on the existence of an upper bound on d. This paper presents two families of asynchronous algorithms achieving, for the first time, subquadratie work as long as d = o(t). The first family uses as its basis a shared-memory algorithm without having to emulate atomic registers assumed by that algorithm. The second family uses specific permutations of tasks, with certain combinatorial properties, to sequence the work of the processors. Another important contribution in this work is the first delay-sensitive lower bound for this problem that helps explain the behavior of our algorithms.

In a seminal paper, Bar-Yehuda et al. (1992) considered broadcasting in radio networks whose nodes know only their own label and labels of their neighbors. They claimed a linear lower bound on the time of deterministic broadcasting in such radio networks, by constructing a class of graphs of diameter 3, with the property that every broadcasting algorithm requires linear time on one of these graphs. Due to a subtle error in the argument, this result is incorrect. We construct an algorithm that broadcasts in logarithmic time on all graphs from the work of Bar-Yehuda et al. Moreover, we show how to broadcast in sublinear time on all n-node graphs of diameter o(log log n). On the other hand, we construct a class of graphs of diameter 4, such that every broadcasting algorithm requires time /spl Omega/(4/spl radic/n) on one of these graphs. In view of the randomized algorithm, running in expected time O(D log n + log/sup 2/ n) on all n-node graphs of diameter D, our lower bound gives the first correct proof of an exponential gap between determinism and randomization in the time of radio broadcasting.

We consider the problem of gossiping when dynamic node crashes are controlled by adaptive adversaries. We develop gossiping algorithms which are efficient with respect to both the time and communication measured as the number of point-to-point messages. If the adversary is allowed to fail up to $t$ nodes, among the total of $n$, where additionally $n-t=\Omega(n/\textpolylog n)$, then one among our algorithms completes gossiping in time $\cO(\log^2 t)$ and with $\cO(n\text polylog t)$ messages. We prove a lower bound which states that the time has to be at least $\Omega\Big(\frac\log n\log(n\log n)-\log t\Big)$ if the communication is restricted to be $\cO(n\text polylog n)$.We also show that one can solve efficiently a more demanding consensus problem with crash failures by resorting to one of our gossiping algorithms. If the adversary is allowed to fail $t$ nodes, where $n-t=\Omega(n/\textpolylog n)$, we obtain a time-optimal solution that is away from the communication optimality by at most a polylogarithmic factor.

The problem of performing t tasks in a distributed system on p failure-prone processors is one of the fundamental problems in distributed computing. If the tasks are similar and independent and the processors communicate by sending messages then the problem is called Do-All. In our work the communication is over a multiple-access channel, and the attached stations may fail by crashing. The measure of performance is work, defined as the number of the available processor steps. Algorithms are required to be reliable in that they perform all the tasks as long as at least one station remains operational. We show that each reliable algorithm always needs to perform at least the minimum amount Ω(t + p√t) of work. We develop an optimal deterministic algorithm for the channel with collision detection performing only the minimum work Θ(t + p√t). Another algorithm is given for the channel without collision detection, it performs work O(t + p√t + p · min {f, t}), where f < p is the number of failures. It is proved to be optimal if the number of faults is the only restriction on the adversary. Finally we consider the question if randomization helps for the channel without collision detection against weaker adversaries. We develop a randomized algorithm which needs to perform only the expected minimum work if the adversary may fail a constant fraction of stations, but it has to select the failure-prone stations prior to the start of an algorithm.

The problem of performing t tasks on n asynchronous or undependable processors is a basic problem in parallel and distributed computing. We consider an abstraction of this problem called the Write-All problem— using n processors write 1's into all locations of an array of size t. The most efficient known deterministic asynchronous algorithms for this problem are due to Anderson and Woll. The first class of algorithms has work complexity of Ο(t . n ε), for n ≰ ty and any ε > 0, and they are the best known for the full range of processors (n = t). To schedule the work of the processors, the algorithms use sets of q permutations on [q] (q ≰ n) that have certain combinatorial properties. Instantiating such an algorithm for a specific ε either requires substantial pre-processing (exponential in 1/ε2) to find the requisite permutations, or imposes a prohibitive constant (exponential in 1/ε3) hidden by the asymptotic analysis. The second class deals with the specific case of t = nu, u ≰ 2, and these algorithms have work complexity of Ο(t log t). They also use sets of permutations with the same combinatorial properties. However instantiating these algorithms requires exponential in n preprocessing to find the permutations. To alleviate this costly instantiation Kanellakis and Shvartsman proposed a simple way of computing the permutation schedules. They conjectured that their construction has the desired properties but they provided no analysis.