**Abstract:** A randomized construction of unbounded snapshots objects

from atomic registers is given. The cost of each snapshot operation is

O(log^3 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 [7, 8] and on the linear lower bound

for deterministic constructions [9], and does not require limiting the number

of updates as in previous sublinear constructions [4]. 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 without

running into covering lower bounds.

Guest: Keren Censor-Hillel

Host: Stefan Schmid

Podcast: Play in new window | Download