Tighter time bounds on fault-tolerant broadcasting and gossiping. (English) Zbl 0758.90033
Summary: Consider a network in which \(n\) processors are connected by unreliable lines and are allowed to communicate with at most one other processor at a time. In this paper, the problems of broadcasting and gossiping are considered. Broadcast is the task of transmitting a message, originated at one node, to all other nodes in the network. Gossiping refers to the process of information dissemination when each processor knows a unique item of information and must transmit it to all the other processors in the network. In this paper, new bounds on fault-tolerant broadcasting and gossiping times are obtained. The given bounds improve on previously known results. In particular, if \(n\) is a power of two, the given broadcast and gossiping schemes require minimum time and are supported by a network having the minimum possible number of edges.
MSC:
| 90B18 | Communication networks in operations research |
| 90B25 | Reliability, availability, maintenance, inspection in operations research |
References:
| [1] | Berman, SIAM J. Alg. Discrete Methods 7 pp 13– (1986) |
| [2] | Bienstock, Discrete Appl. Math. 20 pp 1– (1988) |
| [3] | Bumby, SIAM. J. Alg. Discrete Methods 2 pp 13– (1981) |
| [4] | Chau, J. Comb. Info. Syst. Sci. 10 pp 110– (1985) |
| [5] | Chau, J. Comb. Info. Syst. Sci. 11 pp 1– (1986) |
| [6] | Farley, Networks 9 pp 313– (1979) |
| [7] | Farley, Discrete Math. 25 pp 189– (1979) |
| [8] | Farley, SIAM J. Alg. Discrete Methods 2 pp 189– (1979) · Zbl 0404.05038 · doi:10.1016/0012-365X(79)90022-0 |
| [9] | Gargano, Networks 19 pp 673– (1989) |
| [10] | Gargano, SIAM J. Discrete Math. |
| [11] | Grigni, SIAM J. Discrete Math. 4 pp 207– (1991) |
| [12] | Haddad, SIAM J. Alg. Discrete Methods 8 pp 439– (1987) |
| [13] | Hajnal, Can. Math. Bull. 15 pp 447– (1972) · Zbl 0251.05132 · doi:10.4153/CMB-1972-081-0 |
| [14] | Hedetniemi, Networks 18 pp 319– (1988) |
| [15] | Knödel, Discrete Math 13 pp 95– (1975) |
| [16] | and , Introduction to Finite Fields and Their Applications. Cambridge University Press (1986). · Zbl 0629.12016 |
| [17] | Liestman, Networks 15 pp 159– (1985) |
| [18] | Algorithms for the constructions of fault-tolerant networks (in Italian). Thesis, Università di Salerno. |
| [19] | Peleg, Networks 19 pp 803– (1989) |
| [20] | Seress, SIAM J. Discrete Math. 1 pp 109– (1988) |
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.
