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 September 2018. 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.

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.

- Journal version:
**PDF**. (This version fixes the error in the proceedings version described in the erratum below.) - DISC 2013 proceedings version: PDF. Erratum.
- Slides from Keren Censor-Hillel's talk at DISC 2013: PPTX.

@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