At-most-once semantics in asynchronous shared memory

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

At-most-once semantics in asynchronous shared memory

Full text

Pdf (376 KB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures table of contents

Calgary, AB, Canada

SESSION: Brief Announcements I table of contents

Pages 43-44

Year of Publication: 2009

ISBN:978-1-60558-606-9

Authors

Sotirios Kentros	University of Connecticut, Storrs, CT, USA
Aggelos Kiayias	University of Connecticut, Storrs, CT, USA
Nicolas Nicolaou	University of Connecticut, Storrs, CT, USA
Alexander A. Shvartsman	University of Connecticut, Storrs, CT, USA

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 27, Downloads (12 Months): 55, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1583991.1584003 What is a DOI?

ABSTRACT

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Andrew D. Birrell , Bruce Jay Nelson, Implementing remote procedure calls, ACM Transactions on Computer Systems (TOCS), v.2 n.1, p.39-59, February 1984 [doi>10.1145/2080.357392]
	2	G. Di Crescenzo and A. Kiayias. Asynchronous perfectly secure communication over one--time pads. 3580:216--217, 2005.
	3	Jan Friso Groote , Wim H. Hesselink , Sjouke Mauw , Rogier Vermeulen, An algorithm for the asynchronous Write-All problem based on process collision, Distributed Computing, v.14 n.2, p.75-81, April 2001 [doi>10.1007/PL00008930]
	4	Barbara Liskov , Liuba Shrira , John Wroclawski, Efficient at-most-once messages based on synchronized clocks, ACM Transactions on Computer Systems (TOCS), v.9 n.2, p.125-142, May 1991 [doi>10.1145/103720.103722]
	5	Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996