000208944 001__ 208944
000208944 005__ 20190812205834.0
000208944 0247_ $$2doi$$a10.1145/1993806.1993810
000208944 037__ $$aCONF
000208944 245__ $$aByzantine agreement with homonyms
000208944 269__ $$a2011
000208944 260__ $$bACM Press$$c2011$$aNew York, New York, USA
000208944 336__ $$aConference Papers
000208944 520__ $$aSo 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.
000208944 700__ $$aDelporte-Gallet, Carole
000208944 700__ $$aFauconnier, Hugues
000208944 700__ $$0240335$$g105326$$aGuerraoui, Rachid
000208944 700__ $$aKermarrec, Anne-Marie
000208944 700__ $$aRuppert, Eric
000208944 700__ $$aTran-The, Hung
000208944 7112_ $$d06-08 06 2011$$cSan Jose, California, USA$$athe 30th annual ACM SIGACT-SIGOPS symposium
000208944 773__ $$tProceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing - PODC '11$$q21
000208944 8564_ $$zPreprint$$yPreprint$$uhttps://infoscience.epfl.ch/record/208944/files/byz_agr_with_homo_p21-delporte-gallet.pdf$$s459778
000208944 909C0 $$xU10407$$pDCL$$0252114
000208944 909CO $$ooai:infoscience.tind.io:208944$$qGLOBAL_SET$$pconf$$pIC
000208944 917Z8 $$x166927
000208944 937__ $$aEPFL-CONF-208944
000208944 973__ $$rNON-REVIEWED$$sPUBLISHED$$aEPFL
000208944 980__ $$aCONF