Abstract:

We present Zyzzyva, a protocol that uses speculation to reduce the cost 
and simplify the design of Byzantine fault tolerant state machine 
replication. In Zyzzyva, replicas respond to a client's request without 
first running an expensive three-phase commit protocol to reach agreement 
on the order in which the request must be processed. Instead, they 
optimistically adopt the order proposed by the primary and respond 
immediately to the client. Replicas can thus become temporarily 
inconsistent with one another, but clients detect inconsistencies, help 
correct replicas converge on a single total ordering of requests, and only 
rely on responses that are consistent with this total order. This approach 
allows Zyzzyva to reduce replication overheads to approach their 
theoretical minima.

Lorenzo Alvisi is a Professor in the Department of Computer Sciences at 
the University of Texasat Austin. Lorenzo holds a Ph.D. (1996) and M.S. 
(1994) in Computer Science from Cornell University, and a Laureasumma cum 
laude in Physics from the University of Bologna, Italy. He is the 
recipient of an Alfred P.Sloan Fellowship and of an NSF CAREER Award. 
Lorenzo is interested in distributed systems, fault-tolerance, security, 
and red Italian motorcycles.