The Strong At-Most-Once Problem

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.