Symmetry breaking in distributive networks
- 1 October 1981
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 150-158
- https://doi.org/10.1109/sfcs.1981.41
Abstract
Given a ring (cycle) of n processes it is required to design the processes so that they will be able to choose a leader (a uniquely designated process) by sending messages along the ring. If the processes are indistiguishable there is no deterministic algorithm, and therefore probabilistic algorithms are proposed. These algorithms need not terminate, but their expected complexity (time or number of bits of communication) is bounded by a function of n. If the processes work asynchronously then on the average O(n log2n) bits are transmitted. In the above cases the size n of the ring was assumed to be known. If n is not known it is suggested first to determine the value of n and then use the above algorithm. However, n may only be determined probabilistically and any algorithm may yield an incorrect value. In addition, it is shown that the size of the ring cannot be calculated by any probabilistic algorithm in which the processes can sense termination.Keywords
This publication has 8 references indexed in Scilit:
- Distributed algorithms for synchronizing interprocess communication within real timePublished by Association for Computing Machinery (ACM) ,1981
- On the andvantages of free choicePublished by Association for Computing Machinery (ACM) ,1981
- Decentralized extrema-finding in circular configurations of processorsCommunications of the ACM, 1980
- A distributed abstract data type implemented by a probabilistic communication schemePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- Fast allocation of nearby resources in a distributed systemPublished by Association for Computing Machinery (ACM) ,1980
- An improved algorithm for decentralized extrema-finding in circular configurations of processesCommunications of the ACM, 1979
- Concurrent Processes and Their SyntaxJournal of the ACM, 1979
- Hierarchical ordering of sequential processesActa Informatica, 1971