Solving the at-most-once problem with nearly optimal effectiveness

We present and analyze a wait-free deterministic algorithm for solving the at-most-once problem: how m shared-memory fail-prone processes perform asynchronously n jobs at most once. Our algorithmic strategy provides for the first time nearly optimal effectiveness, which is a measure that expresses the total number of jobs completed in the worst case. The effectiveness of our algorithm equals n−2m+2. This is up to an additive factor of m close to the known effectiveness upper bound n−m+1 over all possible algorithms and improves on the previously best known deterministic solutions that have effectiveness only . We also present an iterative version of our algorithm that for any is both effectiveness-optimal and work-optimal, for any constant ϵ>0. We then employ this algorithm to provide a new algorithmic solution for the Write-All problem which is work optimal for any .