×

Broadcast in the rendezvous model. (English) Zbl 1101.68487

Summary: Distributed or mobile networks, broadcast algorithms are used to update information stored at the nodes. In this paper, we propose a new model of communication based on rendezvous and analyze a multi-hop distributed algorithm to broadcast a message in a synchronous setting. In the rendezvous model, two neighbors \(u\) and \(v\) can communicate if and only if \(u\) calls \(v\) and \(v\) calls \(u\) simultaneously. Thus nodes \(u\) and \(v\) obtain a rendezvous at a meeting point. If \(m\) is the number of meeting points, the network can be modeled by a graph of \(n\) vertices and \(m\) edges. At each round, every vertex chooses a random neighbor and there is a rendezvous if an edge has been chosen by its two extremities. Rendezvous enable an exchange of information between the two entities. We get sharp lower and upper bounds on the time complexity in terms of number of rounds to broadcast: we show that, for any graph, the expected number of rounds is between ln \(n\) and \(O (n^{2})\). For these two bounds, we prove that there exist some graphs for which the expected number of rounds is either \(O (\ln (n))\) or \(\Omega (n^{2})\). For specific topologies, additional bounds are given.

MSC:

68P05 Data structures
68W05 Nonnumerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Albers, S.; Henzinger, M., Exploring unknown environments, SIAM Journal on Computing, 29, 4, 1164-1188 (2000) · Zbl 0947.68165
[2] D. Angluin, Local and global properties in networks of processors, in: Proceedings of the 12th Symposium on theory of computing, 1980, pp. 82-93.; D. Angluin, Local and global properties in networks of processors, in: Proceedings of the 12th Symposium on theory of computing, 1980, pp. 82-93.
[3] L. Barriere, P. Flocchini, P. Fraigniaud, N. Santoro, Capture of an intruder by mobile agents, in: 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2002, pp. 200-209.; L. Barriere, P. Flocchini, P. Fraigniaud, N. Santoro, Capture of an intruder by mobile agents, in: 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA), 2002, pp. 200-209.
[4] Bender, M. A.; Slonim, D. K., The power of team exploration: two robots can learn unlabeled directed graphs, (saddf, S., Proceedings of the 35rd Annual Symposium on Foundations of Computer Science (1994), IEEE Computer Society Press: IEEE Computer Society Press Los Alamitos, CA), 75-85
[5] B. Chlebus, Handbook on Randomized Computing, in: P.M. Pardalos, S. Rajasekaran, J.H. Reif, J.D.P. Rolim, (eds.), Randomized communication in radio networks, Kluwer Academic (2001).; B. Chlebus, Handbook on Randomized Computing, in: P.M. Pardalos, S. Rajasekaran, J.H. Reif, J.D.P. Rolim, (eds.), Randomized communication in radio networks, Kluwer Academic (2001). · Zbl 1059.68522
[6] Comellas, F.; Ozón, J.; Peters, J. G., Deterministic small-world communication networks, Information Processing Letters, 76, 1-2, 83-90 (2000) · Zbl 1338.68012
[7] Deng, X.; Kameda, T.; Papadimitriou, C. H., How to learn an unknown environment i: the rectilinear case, Journal of the ACM, 45, 2, 215-245 (1998) · Zbl 0904.68115
[8] Feige, U.; Peleg, D.; Raghavan, P.; Upfal, E., Randomized broadcast in networks, Random Structures and Algorithms, 1 (1990) · Zbl 0712.68011
[9] 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
[10] M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed, Probabilistic Methods for Algorithmic Discrete Mathematics, Springer, Berlin, 1998.; M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed, Probabilistic Methods for Algorithmic Discrete Mathematics, Springer, Berlin, 1998. · Zbl 0898.00019
[11] Karp, R. M.; Schindelhauer, C.; Shenker, S.; Vocking, B., Randomized rumor spreading, IEEE Symposium on Foundations of Computer Science, 565-574 (2000)
[12] Lynch, N., A hundred impossibility proofs for distributed computing, (Proceedings of the 8th ACM Symposium on Principles of Distributed Computing PODC (1989), ACM Press: ACM Press New York, NY), 1-28
[13] C. McDiarmid, Concentration, pp. 195-248. In Habib et al. [10], 1998.; C. McDiarmid, Concentration, pp. 195-248. In Habib et al. [10], 1998. · Zbl 0927.60027
[14] Motwani, R.; Raghavan, P., Randomized Algorithms (1995), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0849.68039
[15] Metivier, Y.; Saheb, N.; Zemmari, A., Randomized rendezvous, Trends in Mathematics, 183-194 (2000) · Zbl 0965.68140
[16] Metivier, Y.; Saheb, N.; Zemmari, A., Randomized local elections, Information Processing Letters, 82, 313-320 (2002) · Zbl 1043.68115
[17] N. Rao, S. Kareti, W. Shi, S. Iyenagar, Robot Navigation in Unknown Terrains: Introductory Survey of Non-Heuristic Algorithms. 1993.; N. Rao, S. Kareti, W. Shi, S. Iyenagar, Robot Navigation in Unknown Terrains: Introductory Survey of Non-Heuristic Algorithms. 1993.
[18] Tel, G., Introduction to Distributed Algorithms (2000), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0961.68157
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.