Knowledge in distributed byzantine environments
Ruben Michel · 1990
We examine the Simultaneous Byzantine Agreement problem (SBA), a variant of the Byzantine Agreement problem in which the correct processors commit to the agreement value at the same round. Our failure model is the crash Byzantine model where faulty processors follow the protocol up to some round at which they transmit arbitrary messages and thereafter they do not transmit at all. We consider a class of protocols for SBA in which the correct processors transmit sufficient information at each round such that if SBA can be attained at the end of that round, it will. We show that any such protocol requires in the worst case exponential communication. Therefore, any polynomial deterministic protocol sometimes misses SBA. While proving this result we design a protocol called NIP in which the processors remember and convey all interesting information. The protocol's time, space and bit complexities are all linear in the natural parameter of the problem, the number of actual lies. We show that under natural complexity measures, the bit complexity of NIP is lower (to within small factor) than the bit complexity of any other protocol in which processors remember and convey all interesting information. Consequently, NIP is an efficient tool for solving distributed problems. It releases the protocol designer from worrying about administering information so that the designer need only be concerned with the actions that processors should execute based on their knowledge. We introduce a categorical approach for comparing protocols based on their expressibility, thereby settling several questions raised in (DM) and (MT). This approach leads to an algebraic hierarchy of protocols with many intuitive properties, e.g., the further up a protocol is in the hierarchy the more knowledge and common knowledge the processors attain, the lower the protocol is in the hierarchy the less its bit complexity, etc. We show that any protocol that attains SBA as early as possible on corresponding runs requires exponential communication in the worst case. This result stands in contrast with the polynomial implementation of protocols that attain SBA as early as possible on corresponding runs in the omission model. Finally, we show that the two lower bounds on the complexity of SBA protocols extend also to the Byzantine model in which faulty processors transmit arbitrary messages.