The Strong At-Most-Once Problem

Sotirios Kentros, Chadi Kari, Aggelos Kiayias

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

Abstract

The at-most-once problem in shared memory asks for the completion of a number of tasks by a set of independent processors while adhering to “at most once” semantics. At-most-once algorithms are evaluated in terms of effectiveness, which is a measure that expresses the total number of tasks completed at-most-once in the worst case. Motivated by the lack of deterministic solutions with high effectiveness, we study the feasibility of (a close variant of) this problem. The strong at most once problem is solved by an at-most-one algorithm when all tasks are performed if no participating processes crash during the execution of the algorithm. We prove that the strong at-most-once problem has consensus number 2. This explains, via impossibility, the lack of wait-free deterministic solutions with high effectiveness for the at most once problem using only read/write atomic registers. We then present the first k-adaptive effectiveness optimal randomized solution for the strong at-most-once problem, that has optimal expected work for a non-trivial number of participating processes. Our solution also provides the first k-adaptive randomized solution for the Write-All problem, a dual problem to at-most-once.
Original languageEnglish
Title of host publicationDistributed Computing
Subtitle of host publication26th International Symposium, DISC 2012, Salvador, Brazil, October 16-18, 2012. Proceedings
EditorsMarcos K. Aguilera
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Pages386-400
Number of pages15
ISBN (Electronic)978-3-642-33651-5
ISBN (Print)978-3-642-33650-8
DOIs
Publication statusPublished - 2012

Publication series

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

Fingerprint

Dive into the research topics of 'The Strong At-Most-Once Problem'. Together they form a unique fingerprint.

Cite this