At-Most-Once Semantics in Asynchronous Shared Memory

Sotirios Kentros, Aggelos Kiayias, Nicolas Nicolaou, Alexander A. Shvartsman

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

Abstract

At-most-once semantics is one of the standard models for object access in decentralized systems. Accessing an object, such as altering the state of the object by means of direct access, method invocation, or remote procedure call, with at-most-once semantics guarantees that the access is not repeated more-than-once, enabling one to reason about the safety properties of the object. This paper investigates implementations of at-most-once access semantics in a model where a set of such actions is to be performed by a set of failure-prone, asynchronous shared-memory processes. We introduce a definition of the at-most-once problem for performing a set of n jobs using m processors and we introduce a notion of efficiency for such protocols, called effectiveness, used to classify algorithms. Effectiveness measures the number of jobs safely completed by an implementation, as a function of the overall number of jobs n, the number of participating processes m, and the number of process crashes f in the presence of an adversary. We prove a lower bound of n − f on the effectiveness of any algorithm. We then prove that this lower bound can be matched in the two process setting by presenting two algorithms that offer a tradeoff between time and space complexity. Finally, we generalize our two-process solution in the multi-process setting with a hierarchical algorithm that achieves effectiveness of n − logm ·o(n), coming reasonably close, asymptotically, to the corresponding lower bound.
Original languageEnglish
Title of host publicationDistributed Computing
Subtitle of host publication23rd International Symposium, DISC 2009, Elche, Spain, September 23-25, 2009. Proceedings
EditorsIdit Keidar
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages258-273
Number of pages16
ISBN (Electronic)978-3-642-04355-0
ISBN (Print)978-3-642-04354-3
DOIs
Publication statusPublished - 2009

Publication series

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

Fingerprint

Dive into the research topics of 'At-Most-Once Semantics in Asynchronous Shared Memory'. Together they form a unique fingerprint.

Cite this