Solving the At-Most-Once Problem with Nearly Optimal Effectiveness

Sotirios Kentros, Aggelos Kiayias

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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+ϵ).
Original languageEnglish
Title of host publicationDistributed Computing and Networking
Subtitle of host publication13th International Conference, ICDCN 2012, Hong Kong, China, January 3-6, 2012. Proceedings
EditorsLuciano Bononi, Ajoy K. Datta, Stéphane Devismes, Archan Misra
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages16
ISBN (Electronic)978-3-642-25959-3
ISBN (Print) 978-3-642-25958-6
Publication statusPublished - 2012

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'Solving the At-Most-Once Problem with Nearly Optimal Effectiveness'. Together they form a unique fingerprint.

Cite this