Correctness of the Read/Conditional-Write and Query/Update Protocols
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 2005
- Accession Number
- ADA490223
Entities
People
- Garth R. Goodson
- Gregory R. Ganger
- Jay J. Wylie
- Michael Abd-el-malek
- Michael Reiter
Organizations
- Carnegie Mellon University