×

Analysis of fully distributed splitting and naming probabilistic procedures and applications. (English) Zbl 1315.68273

Summary: This paper proposes and analyses two fully distributed probabilistic splitting and naming procedures which assign a label to each vertex of a given anonymous graph \(G\) without any initial knowledge. We prove, in particular, that with probability \(1 - o(n^{- 1})\) (resp. with probability \(1 - o(n^{- c})\) for any \(c \geq 1\)) there is a unique vertex with the maximal label in the graph \(G\) having \(n\) vertices. In the first case, the size of labels is \(O(\log n)\) with probability \(1 - o(n^{- 1})\) and the expected value of the size of labels is also \(O(\log n)\). In the second case, the size of labels is \(O((\log n)(\log^\ast n)^2)\) with probability \(1 - o(n^{- c})\) for any \(c \geq 1\); their expected size is \(O((\log n)(\log^\ast n))\).
We analyse a basic simple maximum broadcasting algorithm and prove that if vertices of a graph \(G\) use the same probabilistic distribution to choose a label then, for broadcasting the maximal label over the labelled graph, each vertex sends \(O(\log n)\) messages with probability \(1 - o(n^{- 1})\).
From these probabilistic procedures we deduce Monte Carlo algorithms for electing or computing a spanning tree in anonymous graphs without any initial knowledge and for counting vertices of an anonymous ring; these algorithms are correct with probability \(1 - o(n^{- 1})\) or with probability \(1 - o(n^{- c})\) for any \(c \geq 1\). The size of messages has the same value as the size of labels. The number of messages is \(O(m \log n)\) for electing and computing a spanning tree; it is \(O(n \log n)\) for counting the vertices of a ring. These algorithms can be easily extended to also ensure for each vertex \(v\) an error probability bounded by \(\epsilon_v\); the error probability \(\epsilon_v\) is decided by \(v\) in a totally decentralised way.
We illustrate the power of the splitting procedure by giving a probabilistic election algorithm for rings having \(n\) vertices with identities which is correct and always terminates; its message complexity is equal to \(O(n \log n)\) with probability \(1 - o(n^{- 1})\).

MSC:

68W15 Distributed algorithms
65C05 Monte Carlo methods
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Angluin, D.; Aspnes, J.; Eisenstat, D.; Ruppert, E., The computational power of population protocols, Distrib. Comput., 20, 4, 279-304 (2007) · Zbl 1266.68043
[2] Afek, Y.; Matias, Y., Elections in anonymous networks, Inform. and Comput., 113, 2, 312-330 (1994) · Zbl 0942.68791
[3] Angluin, D., Local and global properties in networks of processors, (Proceedings of the 12th Symposium on Theory of Computing (1980)), 82-93
[4] Attiya, H.; Snir, M.; Warmuth, M. K., Computing on an anonymous ring, J. ACM, 35, 4, 845-875 (1988) · Zbl 0662.68035
[5] Attiya, H.; Welch, J., Distributed Computing: Fundamentals, Simulations, and Advanced Topics (2004), John Wiley & Sons
[6] Fill, J. A.; Mahmoud, H. M.; Szpankowski, W., On the distribution for the duration of a randomized leader election algorithm, Ann. Appl. Probab., 6, 1260-1283 (1996) · Zbl 0870.60018
[7] Guerraoui, R.; Ruppert, E., What can be implemented anonymously?, (DISC (2005)), 244-259 · Zbl 1171.68374
[8] Itai, A.; Rodeh, M., Symmetry breaking in distributed networks, Inform. and Comput., 88, 1, 60-87 (1990) · Zbl 0705.68020
[9] Jurdzinski, T.; Stachowiak, G., Probabilistic algorithms for the wakeup problem in single-hop radio networks, (Proceedings of the 13th International Symposium on Algorithms and Computation. Proceedings of the 13th International Symposium on Algorithms and Computation, ISAAC 2002, Vancouver, BC, Canada, November 21-23, 2002 (2002)), 535-549 · Zbl 1019.68813
[10] Kalpathy, R.; Mahmoud, H. M.; Ward, M. D., Asymptotic properties of a leader election algorithm, J. Appl. Probab., 48, 2, 569-575 (2011) · Zbl 1219.60008
[11] Lavault, C., Evaluation des algorithmes distribués (1995), Hermès: Hermès Paris · Zbl 0865.68050
[12] Moscibroda, T.; Wattenhofer, R., Maximal independent set in radio networks, (Proceedings of the 25 Annual ACM Symposium on Principles of Distributed Computing. Proceedings of the 25 Annual ACM Symposium on Principles of Distributed Computing, PODC (2005), ACM Press), 148-157 · Zbl 1314.68163
[13] Prodinger, H., How to select a loser, Discrete Math., 120, 1-3, 149-159 (1993) · Zbl 0795.90103
[14] Ramanathan, M. K.; Ferreira, R. A.; Jagannathan, S.; Grama, A.; Szpankowski, W., Randomized leader election, Distrib. Comput., 19, 5-6, 403-418 (2007) · Zbl 1266.68222
[15] Schieber, B.; Snir, M., Calling names on nameless networks, Inform. and Comput., 113, 1, 80-101 (1994) · Zbl 0942.68790
[16] Tel, G., Introduction to Distributed Algorithms (2000), Cambridge University Press · Zbl 0961.68157
[17] Williams, D., Probability with Martingales (1993), Cambridge University Press
[18] Yamashita, M.; Kameda, T., Computing on an anonymous network, (PODC (1988)), 117-130
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.