\input zb-basic
\input zb-ioport
\iteman{io-port 06060323}
\itemau{Kentros, Sotirios; Kiayias, Aggelos}
\itemti{Solving the at-most-once problem with nearly optimal effectiveness.}
\itemso{Bononi, Luciano (ed.) et al., Distributed computing and networking. 13th international conference, ICDCN 2012, Hong Kong, China, January 3--6, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-25958-6/pbk). Lecture Notes in Computer Science 7129, 122-137 (2012).}
\itemab
Summary: 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$ tasks at most once. Our algorithmic strategy provides for the first time nearly optimal effectiveness, which is a measure that expresses the total number of tasks 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 $n - \log m \cdot o(n)$. We also present an iterated version of our algorithm that for any $m = \mathrm{O}(\sqrt[3+\epsilon]{n/\log n})$ is both effectiveness-optimal and work-optimal, for any constant $\epsilon > 0$. We then employ this algorithm to provide a new algorithmic solution for the wite-all problem which is work optimal for any $m=\mathrm{O}(\sqrt[3+\epsilon]{n/\log n})$.r
\itemrv{~}
\itemcc{}
\itemut{At-most-once problem; write-all; I/O automata; asynchronous shared memory}
\itemli{doi:10.1007/978-3-642-25959-3\_9}
\end