Skip to Main content Skip to Navigation
Journal articles

Byzantine agreement with homonyms

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 ℓ different identifiers, where 1≤ℓ≤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 n+3t2 in the partially synchronous case. This demonstrates two differences from the classical model (which has ℓ=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.
Document type :
Journal articles
Complete list of metadata
Contributor : Anne-Marie Kermarrec Connect in order to contact the contributor
Submitted on : Friday, June 28, 2013 - 4:51:06 PM
Last modification on : Friday, January 21, 2022 - 3:13:56 AM

Links full text



Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert, et al.. Byzantine agreement with homonyms. Distributed Computing, Springer Verlag, 2013, 26 (5-6), pp.321-340. ⟨10.1007/s00446-013-0190-3⟩. ⟨hal-00839625⟩



Les métriques sont temporairement indisponibles