Atomic snapshots in O(log^3 n) steps using randomized helping

James Aspnes and Keren Censor-Hillel

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

Leave a Reply

Your email address will not be published.

163,337 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>