We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Byzantine agreement with homonyms.
- Authors
Delporte-Gallet, Carole; Fauconnier, Hugues; Guerraoui, Rachid; Kermarrec, Anne-Marie; Ruppert, Eric; Tran-The, Hung
- Abstract
So far, the distributed computing community has either assumed that all the processes of a distributed system have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. These are two extremes of the same general model: namely, $$n$$ processes use $$\ell $$ different identifiers, where $$1 \le \ell \le n$$ . In this paper, we ask how many identifiers are actually needed to reach agreement in a distributed system with $$t$$ Byzantine processes. We show that having $$3t+1$$ identifiers is necessary and sufficient for agreement in the synchronous case but, more surprisingly, the number of identifiers must be greater than $$\frac{n+3t}{2}$$ in the partially synchronous case. This demonstrates two differences from the classical model (which has $$\ell =n$$ ): there are situations where relaxing synchrony to partial synchrony renders agreement impossible; and, in the partially synchronous case, increasing the number of correct processes can actually make it harder to reach agreement. The impossibility proofs use the fact that a Byzantine process can send multiple messages to the same recipient in a round. We show that removing this ability makes agreement easier: then, $$t+1$$ identifiers are sufficient for agreement, even in the partially synchronous model, assuming processes can count the number of messages with the same identifier they receive in a round.
- Subjects
COMPUTER networks; DISTRIBUTED computing; BYZANTINE processional crosses; CONTRACTS; UNIFORM Resource Identifiers; ANONYMITY
- Publication
Distributed Computing, 2013, Vol 26, Issue 5/6, p321
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-013-0190-3