×

Parallel algorithms for gossiping by mail. (English) Zbl 0696.68048

Summary: We consider the following communication problem: Each vertex of an undirected graph possesses a unique piece of information which must be sent to every other vertex in the graph. The mode of communication will be one-way, point-to-point communication (i.e., one-way mail) in which one vertex may tell another everything it knows in a single transmission. We describe nearly optimal parallel algorithms for disseminating the messages in certain prominent families of graphs (e.g., trees and hypercubes), and consider the complexity of the problem for general graphs.

MSC:

68Q25 Analysis of algorithms and problem complexity
68N25 Theory of operating systems
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Entringer, R. C.; Slater, P. J., Gossips and telegraphs, J. Franklin Inst., 307, 353-360 (1979) · Zbl 0408.05051
[2] Even, S.; Monien, B., On the number of rounds necessary to disseminate information, (Proc. 1st ACM Symposium on Parallel Algorithms and Architectures (1989)), Santa Fe, New Mexico
[3] Hedetniemi, S. M.; Hedetniemi, S. T.; Liestman, A. L., A survey of gossiping and broadcasting in communication networks, Networks, 18, 319-349 (1988) · Zbl 0649.90047
[4] Knödel, W., New gossips and telephones, Discrete Math., 13, 95 (1975) · Zbl 0305.05001
[5] Labahn, R., The telephone problem for trees, Electron. Inf. verarb Kybern., 22, 475-485 (1986) · Zbl 0606.05022
[6] Slater, P. J.; Cockayne, E. J.; Hedetniemi, S. T., Information dissemination in trees, SIAM J. Comput., 10, 692-701 (1981) · Zbl 0468.68064
[7] Vuillemin, J., A data structure for manipulating priority queues, Comm. ACM, 21, 309-315 (1978) · Zbl 0371.68011
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.