Eventual Election of Multiple Leaders for Solving Consensus in Anonymous Systems
- Authors
- Jim?nez Merino, Jos? Ernesto
- Format
- Article
- Status
- publishedVersion
- Description
In classical distributed systems, each process has a unique identity. Today, new distributed systems have emerged where a unique identity is not always possible to be assigned to each process. For example, in many sensor networks a unique identity is not possible to be included in each device due to its small storage capacity, reduced computational power, or the huge number of devices to be identified. In these cases, we have to work with anonymous distributed systems where processes cannot be identified. Consensus cannot be solved in classical and anonymous asynchronous distributed systems where processes can crash. To bypass this impossibility result, failure detectors are added to these systems. It is known that ? is the weakest failure detector class for solving consensus in classical asynchronous systems when a majority of processes never crashes. Although A? was introduced as an anonymous version of ?, to find the weakest failure detector in anonymous systems to solve consensus when a majority of processes never crashes is nowadays an open question. Furthermore, A? has the important drawback that it is not implementable. Very recently, A?? has been introduced as a counterpart of ? for anonymous systems. In this paper, we show that the A?? failure detector class is strictly weaker than A? (i.e., A?? provides less information about process crashes than A?). We also present in this paper the first implementation of A?? (hence, we also show that A?? is implementable), and, finally, we include the first implementation of consensus in anonymous asynchronous systems augmented with A?? and where a majority of processes does not crash.
http://link.springer.com/article/10.1007%2Fs11227-015-1460-6
- Publication Year
- 2015
- Language
- eng
- Topic
- FAILURE
DETECTORS
CONSENSUS
ANONYMITY
- Repository
- Repositorio SENESCYT
- Rights
- openAccess
- License
- closedAccess