×

Token transfer in a faulty network. (English) Zbl 0838.68007

Summary: A token originally situated in a given fault-free node of the complete network, called the source, has to visit all other fault-free nodes. Linkes and/or nodes of the network fail independently with probabilities \(p< 1\) and \(q< 1\), respectively. In a unit of the time every node can be involved in at most one transmission; transmissions along a fault link or involving a faulty node do not succeed. We consider various communication models depending on the ability of nodes to modify their behavior according to the outcome of previous transmissions. For all models we present token transfer algorithms working fast and with probability of correctness exceeding \(1- n^{-\varepsilon}\), where \(n\) is the number of nodes and \(\varepsilon\) an arbitrary positive constant.

MSC:

68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] 1. K. A. BERMAN and M. HAWRYLYCZ, Telephone problems with failures, SIAM J. Alg. Disc. Meth., 1986, 7, pp. 13-17. Zbl0578.05059 MR819701 · Zbl 0578.05059 · doi:10.1137/0607002
[2] 2. D. BIENSTOCK, Broadcasting with random faults, Disc. Appl. Math., 1988, 20, pp. 1-7. Zbl0658.05068 MR936893 · Zbl 0658.05068 · doi:10.1016/0166-218X(88)90037-6
[3] 3. S. BITAN and S. ZAKS, Optimal linear broadcast, J. of Algorithms, 1993, 14, pp. 288-315. Zbl0774.68014 MR1201930 · Zbl 0774.68014 · doi:10.1006/jagm.1993.1015
[4] 4. B. S. CHLEBUS, K. DIKS and A. PELC, Sparse networks supporting efficient reliable broadcasting, Proc. of the 20th International Colloquium on Automata, Languages and Programming, ICALP-93, LNCS 700, pp. 388-397. · Zbl 0817.68019
[5] 5. B. S. CHLEBUS, K. DIKS and A. PELC, Optimal broadcasting in faulty hypercubes, Digest of Papers, FTCS-21, 1991, pp. 266-273.
[6] 6. B. S. CHLEBUS, K. DIKS and A. PELC, Fast gossiping with short unreliable messages, Disc. Appl. Math., to appear. Zbl0807.94029 MR1290999 · Zbl 0807.94029 · doi:10.1016/0166-218X(94)90176-7
[7] 7. B. S. CHLEBUS, K. DIKS and A. PELC, Waking up an anonymous faulty network from a single source, Proc. of the 27th Annual Hawaii International Conference on System Sciences, 1994, Vol. 2, pp. 187-193. MR1259015
[8] 8. C.-T. CHOU and I. S. GOPAL, Linear broadcast routing, J. of Algorithms, 1989, 10, pp. 490-517. Zbl0825.68415 MR1022108 · Zbl 0825.68415 · doi:10.1016/0196-6774(89)90002-3
[9] 9. K. DIKS and A. PELC, Almost safe gossiping in bounded degree networks, SIAM J. Disc. Math., 1992, 5, pp. 338-344. Zbl0768.05060 MR1172742 · Zbl 0768.05060 · doi:10.1137/0405025
[10] 10. K. DIKS and A. PELC, Linear time gossiping with random faults, Rapport de Recherche RR 93/02-3, Université du Québec à Hull, 1993. · Zbl 0803.68004
[11] 11. L. GARGANO, Tighter time bounds on fault-tolerant broadcasting and gossiping, Networks, 1992, 22, pp. 469-486. Zbl0758.90033 MR1170949 · Zbl 0758.90033 · doi:10.1002/net.3230220505
[12] 12. R. W. HADDAD, S. ROY and A. A. SCHAFFER, On gossiping with faulty telephone lines, SIAM J. Alg. Disc. Meth., 1987, 8, pp. 439-445. Zbl0626.05033 MR897741 · Zbl 0626.05033 · doi:10.1137/0608036
[13] 13. T. HAGERUP and C. RUB, A guided tour of Chernoff bounds, Inf. Proc. Letters, 1989/90, 33, pp. 305-308. Zbl0702.60021 MR1045520 · Zbl 0702.60021 · doi:10.1016/0020-0190(90)90214-I
[14] 14. S. M. HEDETNIEMI, S. T. HEDETNIEMI and A. L. LIESTMAN, A survey of gossiping and broadcasting in communication networks, Networks, 1988, 18, pp. 319-349. Zbl0649.90047 MR964236 · Zbl 0649.90047 · doi:10.1002/net.3230180406
[15] 15. E. R. SCHEINERMAN and J. C. WIERMAN, Optimal and near-optimal broadcast in random graphs, Disc. Appl. Math., 1989, 25, pp. 289-297 Zbl0709.05031 MR1026338 · Zbl 0709.05031 · doi:10.1016/0166-218X(89)90007-3
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.