Byzantine Agreement with Homonyms

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert and Hung Tran-The

So far, the distributed computing community has either assumed that the processes of a distributed system all have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. In a sense, these are two extremes of the same general model: namely, n processes can use l authenticated identifiers, where 1 ≤ l ≤ n. This paper studies Byzantine agreement in this general model assuming several processes can share the same identifier.
We study Byzantine agreement in a message-passing system with homonyms. We assume up to t < n of the processes can be Byzantine. We prove the following results: (i) synchronous agreement is possible if and only if l > 3t; (ii) partially synchronous agreement is possible if and only if 3t < l ≤ n < 2l−3t; (iii) asynchronous eventual agreement is possible if and only if l > 3t.

Guset: Rachid Guerraoui
Host: Zvi Lotker

Leave a Reply

Your email address will not be published.

165,401 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>