Distributed Computing

Numerous problems in Theoretical Computer Science can be solved very efficiently using powerful algebraic constructions. Computing shortest paths, constructing expanders, and proving the PCP Theorem, are just few examples of this phenomenon. The quest for combinatorial algorithms that do not use heavy algebraic machinery, but are roughly as efficient, has become a central field of study in this area. Combinatorial algorithms are often simpler than their algebraic counterparts. Moreover, in many cases, combinatorial algorithms and proofs provide additional understanding of studied problems. In this paper we initiate the study of combinatorial algorithms for Distributed Graph Coloring problems. In a distributed setting a communication network is modeled by a graph $$G=(V,E)$$ of maximum degree $$\varDelta $$ . The vertices of $$G$$ host the processors, and communication is performed over the edges of $$G$$ . The goal of distributed vertex coloring is to color $$V$$ with $$(\varDelta + 1)$$ colors such that any two neighbors are colored with distinct colors. Currently, efficient algorithms for vertex coloring that require $$O(\varDelta + \log ^* n)$$ time are based on the algebraic algorithm of Linial (SIAM J Comput 21(1):193–201, 1992) that employs set-systems. The best currently-known combinatorial set-system free algorithm, due to Goldberg et al. (SIAM J Discret Math 1(4):434–446, 1988), requires $$O(\varDelta ^2+\log ^*n)$$ time. We significantly improve over this by devising a combinatorial $$(\varDelta + 1)$$ -coloring algorithm that runs in $$O(\varDelta + \log ^* n)$$ time. This exactly matches the running time of the best-known algebraic algorithm. In addition, we devise a tradeoff for computing $$O(\varDelta \cdot t)$$ -coloring in $$O(\varDelta /t + \log ^* n)$$ time, for almost the entire range $$1 < t < \varDelta $$ . We also compute a Maximal Independent Set in $$O(\varDelta + \log ^* n)$$ time on general graphs, and in $$O(\log n/ \log \log n)$$ time on graphs of bounded arboricity. Prior to our work, these results could be only achieved using algebraic techniques. We believe that our algorithms are more suitable for real-life networks with limited resources, such as sensor networks.

We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the adversary. We describe a new randomized consensus protocol with expected message complexity $$O( n^2 \log ^2 n )$$ when fewer than n / 2 processes may fail by crashing. This is an almost-linear improvement over the best previously known protocol, and within logarithmic factors of a known $$\Omega ( n^2 )$$ message lower bound. The protocol further ensures that no process sends more than $$O( n \log ^3 n )$$ messages in expectation, which is again within logarithmic factors of optimal. We also present a generalization of the algorithm to an arbitrary number of failures t, which uses expected $$O( n t + t^2 \log ^{2} t )$$ total messages. Our approach is to build a message-efficient, resilient mechanism for aggregating individual processor votes, implementing the message-passing equivalent of a weak shared coin. Roughly, in our protocol, a processor first announces its votes to small groups, then propagates them to increasingly larger groups as it generates more and more votes. To bound the number of messages that an individual process might have to send or receive, the protocol progressively increases the weight of generated votes. The main technical challenge is bounding the impact of votes that are still “in flight” (generated, but not fully propagated) on the final outcome of the shared coin, especially since such votes might have different weights. We achieve this by leveraging the structure of the algorithm, and a technical argument based on martingale concentration bounds. Overall, we show that it is possible to build an efficient message-passing implementation of a shared coin, and in the process (almost-optimally) solve the classic consensus problem in the asynchronous message-passing model.

It is shown that, in a precise sense, if there is no bound on the number of faulty processes in a system with unreliable but fair communication, Uniform Distributed Coordination (UDC) can be attained if and only if a system has perfect failure detectors. This result is generalized to the case where there is a bound t on the number of faulty processes. It is shown that a certain type of generalized failure detector is necessary and sufficient for achieving UDC in a context with at most t faulty processes. Reasoning about processes’ knowledge as to which other processes are faulty plays a key role in the analysis.

This paper presents exhaustive analysis and simulation for distributed systems validation. Exhaustive analysis makes possible to detect quickly several types of errors, for instance, unspecified reception of signals, errors in timer management, deadlock, errors in precedence, etc. But, in general, exhaustive analysis can only be applied to a simplified model of the distributed system due to the state explosion problem. On the other hand, simulation permits accurate tests and confronts the distributed system to complex situations. We think both forms of validation are complementary. Validation was done on systems specified in the SDL language, using OVAL, a tool for specification validation developed at CNET, Paris A. This tool allows exhaustive analysis and simulation of SDL specified systems. We illustrate our results with several examples.

Distributed computing models typically assume reliable communication between processors. While such assumptions often hold for engineered networks, e.g., due to underlying error correction protocols, their relevance to biological systems, wherein messages are often distorted before reaching their destination, is quite limited. In this study we take a first step towards reducing this gap by rigorously analyzing a model of communication in large anonymous populations composed of simple agents which interact through short and highly unreliable messages. We focus on the broadcast problem and the majority-consensus problem. Both are fundamental information dissemination problems in distributed computing, in which the goal of agents is to converge to some prescribed desired opinion. We initiate the study of these problems in the presence of communication noise. Our model for communication is extremely weak and follows the push gossip communication paradigm: In each round each agent that wishes to send information delivers a message to a random anonymous agent. This communication is further restricted to contain only one bit (essentially representing an opinion). Lastly, the system is assumed to be so noisy that the bit in each message sent is flipped independently with probability $$1/2-\epsilon $$ , for some small $$\epsilon >0$$ . Even in this severely restricted, stochastic and noisy setting we give natural protocols that solve the noisy broadcast and majority-consensus problems efficiently. Our protocols run in $$O(\log n/\epsilon ^2)$$ rounds and use $$O(n \log n / \epsilon ^2)$$ messages/bits in total, where n is the number of agents. These bounds are asymptotically optimal and, in fact, are as fast and message efficient as if each agent would have been simultaneously informed directly by an agent that knows the prescribed desired opinion. Our efficient, robust, and simple algorithms suggest balancing between silence and transmission, synchronization, and majority-based decisions as important ingredients towards understanding collective communication schemes in anonymous and noisy populations.

Let $$G=(V,E)$$ be an unweighted undirected graph with n vertices and m edges, and let $$k>2$$ be an integer. We present a routing scheme with a poly-logarithmic header size, that given a source s and a destination t at distance $$\varDelta $$ from s, routes a message from s to t on a path whose length is $$O(k\varDelta +m^{1/k})$$ . The total space used by our routing scheme is $$mn^{O(1/\sqrt{\log n})}$$ , which is almost linear in the number of edges of the graph. We present also a routing scheme with $$n^{O(1/\sqrt{\log n})}$$ header size, and the same stretch (up to constant factors). In this routing scheme, the routing table of every $$v\in V$$ is at most $$kn^{O(1/\sqrt{\log n})}deg(v)$$ , where deg(v) is the degree of v in G. Our results are obtained by combining a general technique of Bernstein (2009), that was presented in the context of dynamic graph algorithms, with several new ideas and observations.

This paper presents Ω(m logn) and Ω(mn) messages lower bounds on the problem of computing a gobal sensitive function in biderectional networks with link failures (i.e., dynamically changing topology), wheren andm are the total number of nodes and links in the network. The Ω(m logn) lower bound is under the assumption thatn is a-priori known to the nodes, while the second bound is for the case in which such knowledge is not available. A global sensitive function ofn variables is a function that may not be computed without the knowledge of the values of all then variables (e.g. maximum, sum, etc). Thus, computing such a function at one node of a distributed network requires this node to communicate with every other node in the network. Though lower bounds higher than Ω(m) messages are known for this problem in the context of link failures, none holds for dense bidirectional networks. Moreover, we are not aware of any other nontrivial lower bound higher than Ω(m) for dense bidirectional networks.

In a shared-memory distributed system, n independent asynchronous processes communicate by reading and writing to shared variables. An algorithm is adaptive (to total contention) if its step complexity depends only on the actual number, k, of active processes in the execution; this number is unknown in advance and may change in different executions of the algorithm. Adaptive algorithms are inherently wait-free, providing fault-tolerance in the presence of an arbitrary number of crash failures and different processes' speed. A wait-free adaptive collect algorithm with O(k) step complexity is presented, together with its applications in wait-free adaptive alg orithms for atomic snapshots, immediate snapshots and renaming.

We consider deterministic distributed broadcasting on multiple access channels in the framework of adversarial queuing. Packets are injected dynamically by an adversary that is constrained by the injection rate and the number of packets that may be injected simultaneously; the latter we call burstiness. A protocol is stable when the number of packets in queues at the stations stays bounded. The maximum injection rate that a protocol can handle in a stable manner is called the throughput of the protocol. We consider adversaries of injection rate 1, that is, of one packet per round, to address the question if the maximum throughput 1 can be achieved, and if so then with what quality of service. We develop a protocol that achieves throughput 1 for any number of stations against leaky-bucket adversaries. The protocol has $${\mathcal{O}(n^2+\text{burstiness})}$$ packets queued simultaneously at any time, where n is the number of stations; this upper bound is proved to be best possible. A protocol is called fair when each packet is eventually broadcast. We show that no protocol can be both stable and fair for a system of at least two stations against leaky-bucket adversaries. We study in detail small systems of exactly two and three stations against window adversaries to exhibit differences in quality of broadcast among classes of protocols. A protocol is said to have fair latency if the waiting time of packets is $${\mathcal{O}(\text{burstiness})}$$ . For two stations, we show that fair latency can be achieved by a full sensing protocol, while there is no stable acknowledgment based protocol. For three stations, we show that fair latency can be achieved by a general protocol, while no full sensing protocol can be stable. Finally, we show that protocols that either are fair or do not have the queue sizes affect the order of transmissions cannot be stable in systems of at least four stations against window adversaries.

This article presents a simple local medium access control protocol, called Jade, for multi-hop wireless networks with a single channel that is provably robust against adaptive adversarial jamming. The wireless network is modeled as a unit disk graph on a set of nodes distributed arbitrarily in the plane. In addition to these nodes, there are adversarial jammers that know the protocol and its entire history and that are allowed to jam the wireless channel at any node for an arbitrary $$(1-\epsilon )$$ -fraction of the time steps, where $$0<\epsilon <1$$ is an arbitrary constant. We assume that nodes can perform collision detection (unless they are transmitting themselves), but that they cannot distinguish between jammed transmissions and collisions of regular messages. Nevertheless, we show that Jade achieves an asymptotically optimal throughput by efficiently exploiting the unpredictable time periods in which the medium is available.