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

The Strong At-Most-Once Problem

Sotirios Kentros, Chadi Kari, Aggelos Kiayias

Abstract: The at-most-once problem in shared memory asks for the completion of a number of tasks by a set of independent processors while adhering to “at most once” semantics. At-most-once algorithms are evaluated in terms of effectiveness, which is a measure that expresses the total number of tasks completed at-most-once in the worst case. Motivated by the lack of deterministic solutions with high effectiveness, we study the feasibility of (a close variant of) this problem. The strong at most once problem is solved by an at-most-one algorithm when all tasks are performed if no participating processes crash during the execution of the algorithm. We prove that the strong at-most-once problem has consensus number 2. This explains, via impossibility, the lack of wait-free deterministic solutions with high effectiveness for the at most once problem using only read/write atomic registers. We then present the first k-adaptive effectiveness optimal randomized solution for the strong at-most-once problem, that has optimal expected work for a non-trivial number of participating processes. Our solution also provides the first k-adaptive randomized solution for the Write-All problem, a dual problem to at-most-once.

Guest: Sotiris Kentros

Host: Yvonne-Anne Pignolet

Faster Randomized Consensus with an Oblivious Adversary

James Aspnes

Abstract: Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction of a conciliator, an object that guarantees termination and validity, but that only guarantees agreement with constant probability. The first conciliator assumes unit-cost snapshots and achieves agreement among n processes with probability 1-ε in O(log* n + log(1/ε)) steps for each process. The second uses ordinary multi-writer registers, and achieves agreement with probability 1-ε in O(log log n + log(1/ε)) steps. Combining these constructions with known results gives randomized consensus for arbitrarily many possible input values using unit-cost snapshots in O(log* n) expected steps and randomized consensus for up to O(log n log log n) possible input values using ordinary registers in O(log log n) expected steps.

Guest: James Aspnes
Host: Zvi Lotker