×
Bienstock, Daniel

Broadcasting with random faults. (English) Zbl 0658.05068

Discrete Appl. Math. 20, No. 1, 1-7 (1988).
A communication network can be modeled by a graph. The problem is to broadcast a message that originates from a given node to the remaining nodes as fast as possible, in the presence of random edge faults. It is shown that 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, where n is the number of nodes in the graph.
Reviewer: Wai-Kai Chen

Cited in 11 Documents

MSC:

05C99 Graph theory
94C15 Applications of graph theory to circuits and networks

Keywords:

communication network; message; random edge faults; total number of edges
PDF BibTeX XML Cite
\textit{D. Bienstock}, Discrete Appl. Math. 20, No. 1, 1--7 (1988; Zbl 0658.05068)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Ajtai, M.; Komlós, J.; Szemerédi, E., Sorting in c log n parallel steps, Combinatorica, 3, 1-19, (1983) · Zbl 0523.68048
[2] Alon, N.; Milman, V.D., Eigenvalues, expanders and superconcentrators, 25th symp. found. comp. sci., 320-322, (1984)
[3] Broder, A.; Dolev, D.; Fischer, M.; Simons, B., Efficient fault-tolerant routings in networks, 16th symp. on theory of computing, 536-541, (1984)
[4] Chernoff, H., A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. math. stat., 23, 493-509, (1952) · Zbl 0048.11804
[5] Dolev, D.; Halpern, J., A new look at fault-tolerant network routing, 16th symp. on theory of computing, 526-535, (1984)
[6] Farley, A.M.; Hedetniemi, S.T.; Mitchell, S.; Proskurowski, A., Minimum broadcast graphs, Discrete math., 25, 189-193, (1979) · Zbl 0404.05038
[7] Leighton, T., Tight bounds on the complexity of parallel sorting, 16th symp. on theory of computing, 71-80, (1984)
[8] Liestman, A.L., Fault-tolerant broadcast, graphs, Networks, 15, 159-171, (1985) · Zbl 0579.94030
[9] Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan conjecture and explicit construction of expanders, 18th symp. on theory of computing, 240-246, (1986)
[10] Mitchell, S.L.; Hedetniemi, S.T., A census of minimum broadcast graphs, J. combin. inform. sys. sci., 5, 119-129, (1980)
[11] Peleg, D.; Upfal, E., The token distribution problem, 27th symp. on found. of comp. sci., 418-427, (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.