Métivier, Y.; Robson, J. M.; Zemmari, A. Analysis of fully distributed splitting and naming probabilistic procedures and applications. (English) Zbl 1315.68273 Theor. Comput. Sci. 584, 115-130 (2015). 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})\). Cited in 5 Documents 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 Keywords:Monte Carlo algorithm; spanning tree computation; counting; election algorithm; probabilistic analysis; splitting and naming PDFBibTeX XMLCite \textit{Y. Métivier} et al., Theor. Comput. Sci. 584, 115--130 (2015; Zbl 1315.68273) 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.