Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2011-07-15
Computer Science
Distributed, Parallel, and Cluster Computing
A Brief Announcement of this paper has been published in PODC 2011. An Extended Abstract of this work has been submitted to IC
Scientific paper
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 o(n). We also present an iterated version of our algorithm that for any m = O((n/log n)^(1/(3+\epsilon))) is both effectiveness-optimal and work-optimal, for any constant \epsilon > 0. We then employ this algorithm to provide a new explicit algorithmic solution for the Write-All problem which is work optimal for any m=O((n/log n)^(1/(3+\epsilon))) improving the previously best known result of m = O((n/log n)^(1/4)).
Kentros Sotirios
Kiayias Aggelos
No associations
LandOfFree
Solving the At-Most-Once Problem with Nearly Optimal Effectiveness does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Solving the At-Most-Once Problem with Nearly Optimal Effectiveness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving the At-Most-Once Problem with Nearly Optimal Effectiveness will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-225940