208944
20190317000213.0
10.1145/1993806.1993810
doi
CONF
Byzantine agreement with homonyms
New York, New York, USA
2011
ACM Press
2011
Conference Papers
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, t+1 identifiers are sufficient for agreement, even in the partially synchronous model.
Delporte-Gallet, Carole
Fauconnier, Hugues
Guerraoui, Rachid
105326
240335
Kermarrec, Anne-Marie
Ruppert, Eric
Tran-The, Hung
the 30th annual ACM SIGACT-SIGOPS symposium
San Jose, California, USA
06-08 06 2011
21
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing - PODC '11
Preprint
459778
Preprint
http://infoscience.epfl.ch/record/208944/files/byz_agr_with_homo_p21-delporte-gallet.pdf
DCL
252114
U10407
oai:infoscience.tind.io:208944
IC
conf
GLOBAL_SET
166927
EPFL-CONF-208944
EPFL
PUBLISHED
NON-REVIEWED
CONF