Brian A. Coan

I&C Journal 1992 Journal Article

Modular construction of a Byzantine agreement protocol with optimal message bit complexity

• Brian A. Coan
• Jennifer L. Welch

This paper presents a new Byzantine agreement protocol that tolerates t processor faults using 3t + 1 processors, t + o(t) rounds, O(t 2) total message bits, and O(t ɛ) maximum message size, for any ɛ > 0. The protocol is optimal or near optimal in all cost measures: the number of processors is optimal, the message bit complexity is optimal, the number of rounds exceeds the lower bound by o(t), and the maximum message size exceeds the lower bound by O(t ɛ). The round complexity is uniformly better than 2·(t + 1) and thus is reasonable even for small t. This is the first Byzantine agreement protocol to have optimal message bit complexity. The new protocol is constructed by recursively applying a simple, yet general, transformation that changes the number of rounds, total message bits, and maximum message size required by a Byzantine agreement protocol, but preserves correctness, number of processor faults tolerated, and total number of processors. Each application of this new transformation reduces the number of message bits sent—at the expense of adding rounds of communication. Surprisingly, the base case of the recursive construction is the agreement protocol of Lamport, Shostak, and Pease, which has a number of message bits exponential in t.

I&C Journal 1991 Journal Article

Simultaneity is harder than agreement

• Brian A. Coan
• Cynthia Dwork

We prove a strong lower bound on the number of rounds of message exchange required to achieve simultaneity (i. e. , action in the same round) in certain synchronous fault-tolerant distributed systems. Specifically, our bound holds for any randomized protocol which solves either the simultaneous agreement problem or the distributed firing squad problem. It is known that any protocol that solves either of these problems and that is resilient to t processor faults has at least one execution that lasts at least t + 1 rounds. We strengthen that bound by showing that all normal executions of such a protocol last at least t + 1 rounds. The restriction to normal executions is a technical one that excludes certain executions in which a fortuitous pattern of processor faults enables early termination. The lower bounds proved in this paper contrast with known protocols that achieve agreement on a value (without simultaneity) in fewer than t + 1 rounds in some normal executions. Our results are proved for randomized protocols, for a benign failure model (crash faults), and for a weak adversary. They apply a fortiori to deterministic protocols, more malicious failure models, and stronger adversaries.

STOC Conference 1985 Conference Paper

The Distributed Firing Squad Problem (Preliminary Version)

• Brian A. Coan
• Danny Dolev
• Cynthia Dwork
• Larry J. Stockmeyer