In this paper, we address the problem of broadcasting in a wireless network under a novel communication model: the swamping communication model. In this model, nodes communicate only with those nodes at geometric distance greater than @math and at most @math from them. Communication between nearby nodes under this model can be very time consuming, as the length of the path between two nodes within distance @math is only bounded above by the diameter @math , in many cases. For the @math -node lattice networks, we present algorithms of optimal time complexity, respectively @math for the lattice line and @math for the two-dimensional lattice. We also consider networks of unknown topology of diameter @math and of a parameter @math ( granularity ). More specifically, we consider networks with @math the minimum distance between any two nodes and @math . We present broadcast algorithms for networks of nodes placed on the line and on the plane with respective time complexities @math and @math , where @math .
The fundamental questions of network reliability have received much attention in the context of wired networks, under the assumption that components fail randomly and independently (cf., e.g. @cite_14 @cite_23 @cite_18 @cite_12 and the survey @cite_6 ). On the other hand, empirical work has shown that positive correlation of faults is a more reasonable assumption for networks @cite_22 @cite_3 @cite_11 . In particular, in @cite_11 , the authors provide empirical evidence that data packets losses are spatially correlated in networks. Moreover, in @cite_22 , the authors state that the environment provides many phenomena that may lead to spatially correlated faults. More recently, in @cite_1 , a gap was demonstrated between the fault-tolerance of networks when faults occur independently as opposed to when they occur with positive correlation. To the best of our knowledge, this was the first paper to provide analytic results concerning network fault-tolerant communication in the presence of positively correlated faults for arbitrary networks.
@cite_18 @cite_14 @cite_22 @cite_1 @cite_6 @cite_3 @cite_23 @cite_12 @cite_11
2031578616 2045940022 2107905431 1522267679 2063105299 2071898078 2105269208
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 . Abstract We consider the problem of broadcasting in an n -vertex graph a message that originates from a given vertex, in the presence of random edge faults. If the number of edge faults is at most proportional to the total number of edges, there are networks for which the broadcast can be done in time O(log n ), with high probability. Previously proposed sensor network data dissemination schemes require periodic low-rate flooding of data in order to allow recovery from failure. We consider constructing two kinds of multipaths to enable energy efficient recovery from failure of the shortest path between source and sink. Disjoint multipath has been studied in the literature. We propose a novel braided multipath scheme, which results in several partially disjoint multipath schemes. We find that braided multipaths are a viable alternative for energy-efficient recovery from isolated and patterned failures. The aim of this paper is to study communication in networks where nodes fail in a random dependent way. In order to capture fault dependencies, we introduce the neighborhood fault model, where damaging events, called spots, occur randomly and independently with probability p at nodes of a network, and cause faults in the given node and all of its neighbors. Faults at distance at most 2 become dependent in this model and are positively correlated. We investigate the impact of spot probability on feasibility and time of communication in the fault-free part of the network. We show a network which supports fast communication with high probability, if p = 1 c log n. We also show that communication is not feasible with high probability in most classes of networks, for constant spot probabilities. For smaller spot probabilities, high probability communication is supported even by bounded degree networks. It is shown that the torus supports communication with high probability when p decreases faster than 1 n1 2, and does not when p ? 1 O(n1 2). Furthermore, a network built of tori is designed, with the same faulttolerance properties and additionally supporting fast communication. We show, however, that networks of degree bounded by a constant d do not support communication with high probability, if p ? 1 O(n1 d). While communication in networks with independent faults was widely studied, this is the first analytic paper which investigates network communication for random dependent faults. Broadcasting and gossiping are fundamental tasks in network communication. In broadcasting, or one-to-all communication, information originally held in one node of the network (called the source) must be transmitted to all other nodes. In gossiping, or all-to-all communication, every node holds a message which has to be transmitted to all other nodes. As communication networks grow in size, they become increasingly vulnerable to component failures. Thus, capabilities for fault-tolerant broadcasting and gossiping gain importance. The present paper is a survey of the fast-growing area of research investigating these capabilities. We focus on two most important efficiency measures of broadcasting and gossiping algorithms: running time and number of elementary transmissions required by the communication process. We emphasize the unifying thread in most results from the research in fault-tolerant communication: the trade-offs between efficiency of communication schemes and their fault-tolerance. © 1996 John Wiley & Sons, Inc. We construct and analyze a fast broadcasting algorithm working in the presence of Byzantine component faults. Such faults are particularly difficult to deal with, as faulty components may behave arbitrarily (even maliciously) as transmitters, by either blocking, rerouting, or altering transmitted messages in a way most detrimental to the broadcasting process. We assume that links and nodes of a communication network are subject to Byzantine failures, and that faults are distributed randomly and independently, with link failure probability p and node failure probability q, these parameters being constant and satisfying the inequality (1 - p)2(1 - q) > 1 2. A broadcasting algorithm, working in an n-node network, is called almost safe if the probability of its correctness is at least 1 - 1 n, for sufficiently large n. Thus the robustness of the algorithm grows with the size of the network. Our main result is the design and analysis of an almost safe broadcasting algorithm working in time O(log2 n) and using O(n log n) messages in n-node networks. Under a stronger assumption on failure probability parameters, namely (1 - p)2(1 - q)2 > 1 2, our algorithm can be modified to work in time O(log2 n log log n), also using O(n log n) messages. The novelty of our algorithm is that it can cope with the most difficult type of faults, potentially affecting all components of the network (both its links and nodes), and that it is simultaneously robust and efficient. The success of multicast applications such as Internet teleconferencing illustrates the tremendous potential of applications built upon wide-area multicast communication services. A critical issue for such multicast applications and the higher layer protocols required to support them is the manner in which packet losses occur within the multicast network. We present and analyze packet loss data collected on multicast-capable hosts at 17 geographically distinct locations in Europe and the US and connected via the MBone. We experimentally and quantitatively examine the spatial and temporal correlation in packet loss among participants in a multicast session. Our results show that there is some spatial correlation in loss among the multicast sites. However, the shared loss in the backbone of the MBone is, for the most part, low. We find a fairly significant amount of of burst loss (consecutive losses) at most sites. In every dataset, at least one receiver experienced a long loss burst greater than 8 seconds (100 consecutive packets). A predominance of solitary loss was observed in all cases, but periodic losses of length approximately 0.6 seconds and at 30 second intervals were seen by some receivers.