Carnegie Mellon University Parallel Data Lab Technical Report CMU-PDL-05-107. September 2005.
Michael Abd-El-Malek, Gregory R. Ganger, Garth R. Goodson, Michael K. Reiter, Jay J. Wylie
Parallel Data Laboratory
Electrical and Computer Engineering
Carnegie Mellon University
Pittsburgh, PA 15213
The Read/Conditional-Write (R/CW) protocol provides linearizable reads and conditional-writes of individual objects. A client's conditional-write of an object succeeds only if the object has not been conditionally-written since it was last read by the client. In this sense, R/CW semantics are similar to those of a compare-and-swap register. If a conditional-write does not succeed, it aborts. The R/CW protocol supports multi-object reads and conditional-writes; such operations are strictly serializable. A variant of the R/CW protocol, the Query/Update (Q/U) protocol, provides an operations-based interface to clients: clients invoke query and update methods on objects rather than reading and writing objects in their entirety. The R/CW and Q/U protocols are correct in the asynchronous timing model and tolerate Byzantine failures of clients and servers.
KEYWORDS: Byzantine fault tolerance, asynchronous, read/conditional-write, query/update.
FULL TECHNICAL REPORT: pdf