|Title:||EFFICIENT ATOMIC SNAPSHOTS USING LATTICE AGREEMENT (Preliminary Version).
|Authors:||H. Attiya, M. Herlihy and O. Rachman
|PDF - Revised||CS0759.revised.pdf|
The snapshot object is an important tool for constructing wait-free asynchronous algorithms. We relate the snapshot object to the lattice agreement decision problem. It is shown that any algorithm for solving lattice agreement can be transformed into an implementation of a snapshot object. The overhead cost of this transformation is only a linear number of operations on atomic single-writer multi-reader registers. The transformation uses an unbounded amount of shared memory. Four lattice agreement algorithms are presented:
|Copyright||The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information|
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1992/CS/CS0759), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1992
To the main CS technical reports page
Computer science department, Technion