Feasibility and complexity of broadcasting with random transmission failures

ABSTRACT

We consider fault-tolerant broadcasting in the message passing and radio models under a probabilistic failure model. At each step, the transmitter of each node may fail independently with fixed probability p<1. We study both omission and Byzantine transmission failures. Our goal is to establish conditions on feasibility and to estimate the complexity of almost-safe broadcasting (i.e., broadcasting which is correct with probability at least 1-1/n on n-node graphs for sufficiently large n) under these scenarios. If only omission failures are assumed, almost-safe broadcasting is feasible for any p<1, in both communication models. For Byzantine faults, almost-safe broadcasting is feasible in the message passing model iff p<1/2 and in the radio model iff p<(1-p)^Δ+1, where Δ is the maximum degree of the network. For the time complexity of almost-safe broadcasting, we give the following upper and lower bounds. Consider an n-node graph G with a given source s, and denote by D the radius of G w.r.t. s (namely, the largest distance from s to any node in G). Then for the message passing model we show that assuming omission faults, the optimal almost-safe broadcasting time is Θ (D + log n). Assuming Byzantine faults, almost-safe broadcasting is possible in time O(D+log ^α n), for any constant α > 1. For the radio model we show that almost-safe broadcasting in time O (opt + log n) (where opt is the optimal fault-free broadcasting time) is impossible for some graphs, even with omission failures, and we give an almost-safe broadcasting algorithm of time O(opt • log n) for any graph, for both types of failures.

REFERENCES

• 1: Yehuda Afek , Hagit Attiya , Alan Fekete , Michael Fischer , Nancy Lynch , Yishay Mansour , Dai-Wei Wang , Lenore Zuck, Reliable communication over unreliable channels, Journal of the ACM (JACM), v.41 n.6, p.1267-1297, Nov. 1994 [doi>10.1145/195613.195651]
• 2: Yehuda Afek , Eli Gafni , Adi Rosén, The slide mechanism with applications in dynamic networks, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, p.35-46, August 10-12, 1992, Vancouver, British Columbia, Canada [doi>10.1145/135419.135430]
• 3: Noga Alon , Amotz Bar-Noy , Nathan Linial , David Peleg, A lower bound for radio broadcast, Journal of Computer and System Sciences, v.43 n.2, p.290-298, Oct. 1991 [doi>10.1016/0022-0000(91)90015-W]
• 4: Baruch Awerbuch , Shimon Even, Efficient and reliable broadcast is achievable in an eventually connected network(Extended Abstract), Proceedings of the third annual ACM symposium on Principles of distributed computing, p.278-281, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806754]
• 5: B. Awerbuch, Y. Mansour and N. Shavit, Polynomial end-to-end communication, Proc 33rd IEEE FOCS, 1992, 358--363.
• 6: A. Bagchi , S. L. Hakimi, Information Dissemination in Distributed Systems with Faulty Units, IEEE Transactions on Computers, v.43 n.6, p.698-710, June 1994 [doi>10.1109/12.286303]
• 7: Feng Bao , Yoshihide Igarashi , Keiko Katano, Broadcasting in Hypercubes with Randomly Distributed Byzantine Faults, Proceedings of the 9th International Workshop on Distributed Algorithms, p.215-229, September 13-15, 1995
• 8: Reuven Bar-Yehuda , Oded Goldreich , Alon Itai, On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization, Journal of Computer and System Sciences, v.45 n.1, p.104-126, Aug. 1992 [doi>10.1016/0022-0000(92)90042-H]
• 9: Piotr Berman , Krzysztof Diks , Andrzej Pelc, Reliable broadcasting in logarithmic time with Byzantine link failures, Journal of Algorithms, v.22 n.2, p.199-211, Feb. 1997 [doi>10.1006/jagm.1996.0810]
• 10: D. Blough and A. Pelc, Optimal communication in networks with randomly distributed Byzantine faults, Networks 23, (1993), 691--701.
• 11: Artur Czumaj , Wojciech Rytter, Broadcasting Algorithms in Radio Networks with Unknown Topology, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.492, October 11-14, 2003
• 12: Krzysztof Diks , Andrzej Pelc, Almost safe gossiping in bounded degree networks, SIAM Journal on Discrete Mathematics, v.5 n.3, p.338-344, Aug. 1992 [doi>10.1137/0405025]
• 13: D. Dolev, The Byzantine generals strike again, J. of Algorithms 3, (1982), 14--30.
• 14: Alan Fekete , Nancy Lynch , Yishay Mansour , John Spinelli, The impossibility of implementing reliable communication in the face of crashes, Journal of the ACM (JACM), v.40 n.5, p.1087-1107, Nov. 1993 [doi>10.1145/174147.169676]
• 15: Eli Gafni , Yehuda Afek, End-to-end communication in unreliable networks, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.131-148, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62570]
• 16: A. Herzberg , S. Kutten, Fast isolation of arbitrary forwarding faults, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.339-353, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.73006]
• 17: Chiu-Yuen Koo, Broadcast in radio networks tolerating byzantine adversarial behavior, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011807]
• 18: Dariusz R. Kowalski , Andrzej Pelc, Time of Deterministic Broadcasting in Radio Networks with Local Knowledge, SIAM Journal on Computing, v.33 n.4, p.870-891, 2004 [doi>10.1137/S0097539702419339]
• 19: Evangelos Kranakis , Danny Krizanc , Andrzej Pelc, Fault-tolerant broadcasting in radio networks, Journal of Algorithms, v.39 n.1, p.47-67, April 2001 [doi>10.1006/jagm.2000.1147]
• 20: L. Kučera, Broadcasting through a noisy one-dimensional network, Tech. Report MPI-I-93-106, Max-Planck-Institut, Saarbruecken, Germany, 1993.
• 21: Nancy A. Lynch , Yishay Mansour , Alan Fekete, Data link layer: two impossibility results, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.149-170, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62572]
• 22: O. Goldreich , A. Herzberg , Y. Mansour, Source to destination communication in the presence of faults, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.85-101, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72987]
• 23: A. Pelc, Fault-tolerant broadcasting and gossiping in communication networks, Networks 28, (1996), 143--156.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.1 Reliability, Testing, and Fault-Tolerance

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Reliability, Theory

Keywords:
Byzantine faults, broadcasting, omission faults, radio networks, random failures