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, processes use different identifiers, where . In this paper, we ask how many identifiers are actually needed to reach agreement in a distributed system with Byzantine processes. We show that having identifiers is necessary and sufficient for agreement in the synchronous case but, more surprisingly, the number of identifiers must be greater than in the partially synchronous case. This demonstrates two differences from the classical model (which has ): 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, assuming processes can count the number of messages with the same identifier they receive in a round.