Atomic snapshots in expected O(log³ n) steps using randomized helping

James Aspnes and Keren Censor-Hillel. Atomic snapshots in expected O(log³ n) steps using randomized helping. Submitted to Distributed Computing, January 2014. Last revised February 2017. An earlier version appeared in Distributed Computing: 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14--18, 2013. Proceedings, Lecture Notes in Computer Science 8205, Springer-Verlag, October 2013, pp. 254–268. There is an important erratum for the proceeding version of this paper.

Abstract

A randomized construction of single-writer snapshot objects from atomic registers is given. The cost of each snapshot operation is O(log³n) atomic register steps with high probability, where n is the number of processes, even against an adaptive adversary. This is an exponential improvement on the linear cost of the previous best known unrestricted snapshot construction and on the linear lower bound for deterministic constructions, and does not require limiting the number of updates as in previous sublinear constructions. One of the main ingredients in the construction is a novel randomized helping technique that allows out-of-date processes to obtain up-to-date information.

Our construction can be adapted to implement snapshots in a message-passing system. While a direct adaptation using the Attiya-Bar-Noy-Dolev construction gives a cost of O(log³ n) time and O(n log³ n) messages per operation with high probability, we show that exploiting the inherent parallelism of a message-passing system can eliminate the need for randomized helping and reduce the complexity to O(log² n) time and O(n log² n) messages per operation in the worst case. This implementation includes an O(1)-time, O(n)-message construction of an unbounded max register that may be of independent interest.

BibTeX

Download
@incollection{AspnesC2013,
year={2013},
isbn={978-3-642-41526-5},
booktitle={Distributed Computing: 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14--18, 2013. Proceedings},
volume={8205},
series={Lecture Notes in Computer Science},
editor={Afek, Yehuda},
doi={10.1007/978-3-642-41527-2_18},
title={Atomic Snapshots in ${O}(\log^3 n)$ Steps Using Randomized Helping},
url={http://dx.doi.org/10.1007/978-3-642-41527-2_18},
publisher={Springer Berlin Heidelberg},
author={Aspnes, James and Censor-Hillel, Keren},
pages={254--268}
}

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page