TY - GEN
T1 - At-most-once semantics in asynchronous shared memory
AU - Kentros, Sotirios
AU - Kiayias, Aggelos
AU - Nicolaou, Nicolas
AU - Shvartsman, Alexander A.
N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=76749121560&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=76749121560&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-04355-0_27
DO - 10.1007/978-3-642-04355-0_27
M3 - Conference contribution
AN - SCOPUS:76749121560
SN - 3642043542
SN - 9783642043543
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 258
EP - 273
BT - Distributed Computing - 23rd International Symposium, DISC 2009, Proceedings
T2 - 23rd International Symposium on Distributed Computing, DISC 2009
Y2 - 23 September 2009 through 25 September 2009
ER -