On the round complexity of Byzantine agreement without initial set-up

摘要

It is well known that in order to (deterministically) achieve Byzantine agreement (consensus) among n processors in a fully connected network in which f processors may be faulty, where f satisfies f < n/3,exactly f+ 1 communication rounds are required. This result was proved under the assumption that the network topology is known a priori to each processor, i.e., the identifiers of the processors and of the links between processors are known. This paper deals with the Byzantine agreement problem when such initial setup is not available. It is shown that/+ 1 rounds are sufficient to reach agreement if the faulty processors are not able to identify themselves with names of the correct processors, and that this upper bound no longer holds when such identity theft is possible.