Byzantine Agreement with Homonyms (Accord Byzantin avec des Homonymes)

Carole Delporte-Gallet (1) , Hugues Fauconnier (1) , Rachid Guerraoui (2) , Anne-Marie Kermarrec (3) , Eric Ruppert (4) , Hung Tran-The (1)

1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications
2 EPFL - Ecole Polytechnique Fédérale de Lausanne
3 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
4 Department of Computer Science and Engineering [York]

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 l different authenticated identifiers, where 1 <= l <=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+3t)/2 in the partially synchronous case. This demonstrates two differences from the classical model (which has l=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, identifiers are sufficient for agreement, even in the partially synchronous model.

Domaines: Informatique

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert, et al.. Byzantine Agreement with Homonyms (Accord Byzantin avec des Homonymes). 2012. ⟨hal-00689119⟩