H. Raymond Strong

I&C Journal 1992 Journal Article

Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement

• Amotz Bar-Noy
• Danny Dolev
• Cynthia Dwork
• H. Raymond Strong

We describe several new algorithms for Byzantine agreement. The first of these is a simplification of the original exponential-time Byzantine agreement algorithm due to Pease, Shostak, and Lamport, and is of comparable complexity to their algorithm. However, its proof is very intuitively appealing. A technique of shifting between algorithms for solving the Byzantine agreement problem is then studied. We present two families of algorithms obtained by applying a shift operator to our first algorithm. These families obtain the same rounds to message length trade-off as do Coan's families but do not require the exponential local computation time (and space) of his algorithms. We also describe a modification of an O( n )-resilient algorithm for Byzantine agreement of Dolev, Reischuk, and Strong. Finally, we obtain a hybrid algorithm that dominates all our others, by beginning execution of an algorithm in one family, first shifting into an algorithm of the second family, and finally shifting into an execution of the adaptation of the Dolev, Reischuk, and Strong algorithm.

STOC Conference 1984 Conference Paper

A New Look at Fault Tolerant Network Routing

• Danny Dolev
• Joseph Y. Halpern
• Barbara Simons
• H. Raymond Strong

STOC Conference 1984 Conference Paper

On the Possibility and Impossibility of Achieving Clock Synchronization

• Danny Dolev
• Joseph Y. Halpern
• H. Raymond Strong

FOCS Conference 1982 Conference Paper

'Eventual' Is Earlier than 'Immediate'

• Danny Dolev
• Rüdiger Reischuk
• H. Raymond Strong

Two different notions of Byzantine Agreement - immediate and eventually - are defined depending on whether the agreement involves an action to be performed synchronously or not. The lower bounds for time complexity depend on what kind of agreement has to be achieved. All previous algorithms to reach Byzantine Agreement ensure immediate agreement. We present two algorithms that in many cases reach the second type of agreement faster than previously known algorithms showing that there actually is a difference between the two notions: Eventual Byzantine Agreement can be reached earlier than Immediate.

STOC Conference 1982 Conference Paper

Polynomial Algorithms for Multiple Processor Agreement

• Danny Dolev
• H. Raymond Strong

Reaching agreement in a distributed system while handling malfunctioning behavior is a central issue for reliable computer systems. All previous algorithms for reaching the agreement required an exponential number of messages to be sent, with or without authentication. We give polynomial algorithms for reaching (Byzantine) agreement, both with and without the use of authentication protocols. We also prove that no matter what kind of information is exchanged, there is no way to reach agreement with fewer than t+1 rounds of exchange, where t is the upper bound on the number of faults.

STOC Conference 1980 Conference Paper

Vector Execution of Flow Graphs (Extended Abstract)

• H. Raymond Strong

STOC Conference 1972 Conference Paper

Characterization of Flowchartable Recursions (Short Version)

• S. A. Walker
• H. Raymond Strong