×

Gossiping in chordal rings under the line model. (English) Zbl 0972.68010

Summary: This paper is devoted to the gossip (or all-to-all) problem in the chordal ring under the one-port line model. The line model assumes long distance calls between non-neighboring processors. In this sense, the line model is strongly related to circuit-switched networks, wormhole routing, optical networks supporting wavelength division multiplexing, ATM switching, and networks supporting connected mode routing protocols. Since the chordal rings are competitors of networks as meshes or tori because of their short diameter and bounded degree, it is of interest to ask whether they can support intensive communications (typically all-to-all) as efficiently as these networks. We propose polynomial algorithms to derive optimal or near-optimal gossip protocols in the chordal ring.

MSC:

68M12 Network protocols
68M14 Distributed systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arden, B. W.; Lee, H., Analysis of chordal ring network, IEEE Trans. Comput., C-30, 4, 291-295 (1981)
[2] L. Barrière, J. Fàbrega, E. Simó, Zaragozá, Fault-tolerant routings in chordal ring networks, Networks to appear.; L. Barrière, J. Fàbrega, E. Simó, Zaragozá, Fault-tolerant routings in chordal ring networks, Networks to appear.
[3] Bermond, J.-C.; Comellas, F.; Hsu, D. F., Distributed loop computer networksa survey, J. Parallel Distributed Comput., 24, 2-10 (1995)
[4] F. Comellas, P. Hell, Broadcasting in chordal rings, IWIN’97, Praga, 1997.; F. Comellas, P. Hell, Broadcasting in chordal rings, IWIN’97, Praga, 1997. · Zbl 1031.68012
[5] Coxeter, H. S.M., Self dual configurations and regular graphs, Bull. Amer. Math. Soc., 56, 413-455 (1950) · Zbl 0040.22803
[6] DeMara, R. F.; Moldovan, D. I., Performance indices for parallel marker-propagation, (Wu, C. I., Proc. Internat. Conf. on Parallel Processing (1991), CRC Press: CRC Press Boca Raton, FL), 658-659
[7] Dongarra, J. J.; Walker, D. W., Software libraries for linear algebra computation on high performances computers, SIAM Rev., 37, 151-180 (1995) · Zbl 0874.65014
[8] Farley, A. M., Minimum time line broadcast networks, Networks, 10, 59-70 (1980) · Zbl 0432.90030
[9] Fraigniaud, P.; Lazard, E., Methods and problems of communication in usual networks, Discrete Appl. Math., 53, 1, 79-133 (1994) · Zbl 0818.94029
[10] Hromkovič, J.; Klasing, R.; Stöhr, E. A., Dissemination of information in vertex-disjoint paths mode, Comput. Artificial Intelligence, 15, 4, 295-318 (1996)
[11] Hromkovič, J.; Klasing, R.; Stöhr, E. A.; Wagener, H., Gossiping in vertex-disjoint paths mode in \(d\)-dimensional grids and planar graphs, Inform. Comput., 123, 1, 17-28 (1995) · Zbl 1096.68514
[12] Hromkovič, J.; Klasing, R.; Unger, W.; Wagener, H., (Optimal algorithms for broadcast and gossip in the edge-disjoint path modes, 4th Scandinavian Workshop on Algorithm Theory (SWAT’94), Lecture Notes in Computer Science, Vol. 824 (1994), Springer: Springer Berlin), 219-230 · Zbl 1502.68232
[13] D. Krizanc, F. Luccio, Boolean routing on chordal rings, Proc. Coll. on Structural Information and Communication Complexity, 1995.; D. Krizanc, F. Luccio, Boolean routing on chordal rings, Proc. Coll. on Structural Information and Communication Complexity, 1995.
[14] Laforest, C., Gossip in trees under line-communication mode, (Bourge, L.; Fraigniaud, P.; Mignotte, A.; Robert, Y., Euro-Par’96 Parallel Processing, Lecture Notes in Computer Science, Vol. 1123 (1996), Springer: Springer Berlin), 333-340
[15] Pacheco, P., Parallel Programming with MPI (1995), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA
[16] de Rumeur, J., Communications dans les réseaux de processeurs (1994), Masson: Masson Paris
[17] Xu, H.; McKinley, P.; Ni, L., Efficient implementation of barrier synchronization in wormhole-routed hypercube multicomputers, J. Parallel Distributed Comput., 16, 172-184 (1992)
[18] Yebra, J. L.A.; Fiol, M. A.; Morillo, P.; Alegre, I., The diameter of undirected graphs associated to plane tessellations, Ars Combin., 20B, 159-171 (1985) · Zbl 0619.05031
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.