Technical Report CS759

TR#:CS759
Title: EFFICIENT ATOMIC SNAPSHOTS USING LATTICE AGREEMENT (Preliminary Version).
Authors: H. Attiya, M. Herlihy and O. Rachman
PDFNot Available
Abstract:

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:

  • A deterministic algorithm that uses O(\log^2 n) operations on (dynamic) 2-processor Test{\cal \&}Set registers, plus O(n) operations on (dynamic) atomic single-writer multi-reader registers.
  • A deterministic algorithm that uses O(n \log^2 n) operations on (static) 2-processor Test{\cal \&}Set registers, plus O(n \log^2 n) operations on (static) atomic single-writer multi-reader registers.
  • A randomized algorithm that uses an expected number of O(n) operations on (dynamic) atomic single-writer multi-reader registers.
  • A randomized algorithm that uses and expected number of O(n \log^2 n) operations on (static) atomic single-writer multi-reader registers.
These algorithms imply implementations of atomic snapshots with the same behavior. The randomized algorithms are constructed from the deterministic ones by using randomized implementations of 2-processors Test{\cal \&}Set registers from atomic registers.

CopyrightThe 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