@inproceedings{156ec27dedf1429cb4952ed1134d6b34,

title = "Solving the At-Most-Once Problem with Nearly Optimal Effectiveness",

abstract = "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 − logm ·o(n). We also present an iterated version of our algorithm that for any m=O(n/logn−−−−−−√3+ϵ) 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 m=O(n/logn−−−−−−√3+ϵ).",

author = "Sotirios Kentros and Aggelos Kiayias",

year = "2012",

doi = "10.1007/978-3-642-25959-3_9",

language = "English",

isbn = " 978-3-642-25958-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "122--137",

editor = "Luciano Bononi and Datta, {Ajoy K.} and St{\'e}phane Devismes and Archan Misra",

booktitle = "Distributed Computing and Networking",

}