At-most-once semantics in asynchronous shared memory

Sotiris Kentros, Aggelos Kiayias, Nicolas C. Nicolaou, Alexander A. Shvartsman

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


This paper investigates the feasibility of implementing at-most-once access semantics in a model where a collection of actions is to be performed by failure-prone, asynchronous shared-memory processes. We introduce the At-Most-Once problem for performing a set of n jobs using m processors, and we define the notion of efficiency for such protocols, called effectiveness, that allows the classification of algorithms solving the problem. The effectiveness for an at-most-once implementation is the number of jobs safely completed by the implementation, expressed as a function of the number of jobs n, the number of processes m, and the number of process crashes f. We prove a lower bound of n--f on the effectiveness of any algorithm. We then present two process solutions that offer a trade off between work and space complexity. Finally, we generalize a two-process solution for the multi-process setting using a hierarchical algorithm that achieves effectiveness of n--log m†o(n), coming reasonably close, asymptotically, to the corresponding lower bound.
Original languageEnglish
Title of host publicationSPAA 2009: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, Calgary, Alberta, Canada, August 11-13, 2009
Number of pages2
ISBN (Print)978-1-60558-606-9
Publication statusPublished - 2009


Dive into the research topics of 'At-most-once semantics in asynchronous shared memory'. Together they form a unique fingerprint.

Cite this