Byzantine Agreement with Homonyms

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 \(\ell \) different identifiers, where \(1 \le \ell \le 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 \(\frac{n+3t}{2}\) in the partially synchronous case. This demonstrates two differences from the classical model (which has \(\ell =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.