Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
433885 | Theoretical Computer Science | 2015 | 16 Pages |
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)1−o(n−1) (resp. with probability 1−o(n−c)1−o(n−c) for any c≥1c≥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(logn)O(logn) with probability 1−o(n−1)1−o(n−1) and the expected value of the size of labels is also O(logn)O(logn). In the second case, the size of labels is O((logn)(log⁎n)2)O((logn)(log⁎n)2) with probability 1−o(n−c)1−o(n−c) for any c≥1c≥1; their expected size is O((logn)(log⁎n))O((logn)(log⁎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(logn)O(logn) messages with probability 1−o(n−1)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)1−o(n−1) or with probability 1−o(n−c)1−o(n−c) for any c≥1c≥1. The size of messages has the same value as the size of labels. The number of messages is O(mlogn)O(mlogn) for electing and computing a spanning tree; it is O(nlogn)O(nlogn) 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 ϵvϵv; the error probability ϵvϵ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(nlogn)O(nlogn) with probability 1−o(n−1)1−o(n−1).