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 aim at bridging 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 rumor-spreading problem and the majority-consensus problem, two fundamental tasks in distributed computing, and initiate their study under communication noise. Our model for communication is extremely weak and follows the push gossip communication paradigm: In each synchronous 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-e, for some small Ae >0. Even in this severely restricted, stochastic and noisy setting we give natural protocols that solve the noisy rumor-spreading and the noisy majority-consensus problems efficiently. Our protocols run in O(log n e2) rounds and use O(n log n e2) 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 the source. 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.
Disseminating information to all the nodes of a network is one of the most fundamental communication primitives. In particular, the broadcast problem, where a single piece of information initially residing at some source node is to be disseminated, and variants of it have received a lot of attention in the literature, see, e.g., @cite_7 @cite_47 @cite_39 @cite_46 @cite_33 @cite_57 @cite_56 @cite_58 @cite_49 @cite_9 @cite_15 . Much of this research was devoted to bounding measures such as the number of rounds, and the total number of messages. Fault tolerant broadcast algorithms have also been studied extensively, especially in complete networks and in synchronous environments, where the focus has been on weak types of failures such as (probabilistic) message failures and initial node crashes. Essentially, it has been shown that there exist broadcast protocols that can overcome such faults with a relatively little penalty @cite_39 @cite_19 @cite_29 @cite_51 @cite_56 @cite_54 @cite_9 @cite_58 .
@cite_47 @cite_33 @cite_7 @cite_15 @cite_9 @cite_29 @cite_54 @cite_39 @cite_57 @cite_56 @cite_19 @cite_49 @cite_46 @cite_58 @cite_51
2161281242 2060660772 2031578616 2047677968
In much of the theoretical literature on wireless algorithms, 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 harder communication problems. In this paper, we present results of a current project aimed at simplifying such algorithms and analysis by decomposing the treatment into two levels, using abstract "MAC layer" specifications to encapsulate the contention management. We use two different abstract MAC layers: the basic one of [14, 15] and a new probabilistic layer. We first present a typical randomized contention-manageent algorithm for a standard graph-based radio network model We show that it implements both abstract MAC layers. We combine this algorithm with greedy algorithms for single-message and multi-message global broadcast and analyze the combination, using both abstract MAC layers as intermediate layers. Using the basic MAC layer, we prove a bound of O(D log(n ∈) 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 O((D + log(n ∈)) 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Δ) log(n ∈) log Δ) using the basic layer and O((D + kΔ log(n ∈)) log Δ) using the probabilistic layer, for the time to deliver a message everywhere in the presence of at most k concurrent messages. Flooding based querying and broadcasting schemes have low hop-delays of Theta(1 R(n)) to reach any node that is a unit distance away, where R(n) is the transmission range of any sensor node. However, in sensor networks with large radio ranges, flooding based broadcasting schemes cause many redundant transmissions leading to a broadcast storm problem. In this paper, we study the role of geographic information and state information (i.e., memory of previous messages or transmissions) in reducing the redundant transmissions in the network. We consider three broadcasting schemes with varying levels of local information where nodes have: (i) no geographic or state information, (ii) coarse geographic information about the origin of the broadcast, and (Hi) no geographic information, but remember previously received messages. For each of these network models, we demonstrate localized forwarding algorithms for broadcast (based on geography or state information) that achieve significant reductions in the transmission overheads while maintaining hop-delays comparable to flooding based schemes. We also consider the related problem of broadcasting to a set of "spatially uniform" points in the network (lattice points) in the regime where all nodes have only a local sense of direction and demonstrate an efficient "sparse broadcast" scheme based on a branching random walk that has a low number of packet transmissions. Thus, our results show that even with very little local information, it is possible to make broadcast schemes significantly more efficient. We consider the problem of broadcasting in an n –node hypercube whose links and nodes fail independently with given probabilities p source , has to reach all other fault-free nodes. Messages may be directly transmitted to adjacent nodes only, and every node may communicate with at most one neighbour in a unit of time. A message can be transmitted only if both communicating neighbours and the link joining them are fault-free. For parameters p and q satisfying (1 – p )(1 – q ) ≽ 0.99 (e.g. p = q = 0.5 ), we give an algorithm working in time O (log n ) and broadcasting source information to all fault-free nodes with probability exceeding 1 – cn -e for some positive constant e, c depending on p and q but not depending on n . We consider the problem of distributed deterministic broadcasting in radio networks whose nodes are located on a line. Nodes send messages in synchronous time-slots. Each node υ has a given transmission range. All nodes located within this range can receive messages from υ. However, a node situated in the range of two or more nodes that send messages simultaneously, cannot receive these messages and hears only noise. Each node knows only its own position and range, as well as the maximum of all ranges. Broadcasting is adaptive: nodes can decide on the action to take on the basis of previously received messages, silence or noise. We prove lower bounds on broadcasting time in this model and construct broadcasting protocols whose performance nearly matches these bounds for the simplest case when nodes are situated on a line. We also show that if nodes do not even know their own range, every broadcasting protocol must be hopelessly slow. While distributed randomized broadcasting algorithms, and, on the other hand, deterministic off-line broadcasting algorithms assuming full knowledge of the radio network, have been extensively studied in the literature, ours are the first results concerning broadcasting algorithms that are distributed and deterministic at the same time. We show that in this case, information available to nodes influences the efficiency of broadcasting in a significant way.