[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1993806.1993837acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
abstract

Fork-consistent constructions from registers

Published: 06 June 2011 Publication History

Abstract

So far, all implementations providing fork-consistent semantics are based on objects with read-modify-write capabilities (also termed servers). We propose constructions of fork-consistent shared objects from single-writer multiple-reader(SWMR) read/write base registers, that are strictly weaker than servers. Our shared object constructions provide linearizability if all base registers behave correctly, and gracefully degrade to either fork-linearizability or weak fork-linearizability if any number of registers fails Byzantine. We make the following contributions: (a) A fork-linearizable construction of a universal type where operations are allowed to abort under concurrency, and (b) a weak fork-linearizable implementation of a shared memory that ensures wait-freedom when the registers are correct.

References

[1]
M. K. Aguilera, S. Frolund, V. Hadzilacos, S. L. Horn, and S. Toueg. Abortable and Query-Abortable Objects and Their Efficient Implementation. In PODC, New York, NY, USA, 2007. ACM.
[2]
C. Cachin, A. Shelat, and A. Shraer. Efficient Fork-Linearizable Access to Untrusted Shared Memory. In PODC, New York, NY, USA, 2007. ACM.
[3]
F. E. Fich. How Hard Is It to Take a Snapshot? In SOFSEM, Berlin, Heidelberg, 2005. Springer-Verlag.
[4]
M. Herlihy. Wait-Free Synchronization. ACM Trans. Program. Lang. Syst., 13(1), 1991.
[5]
M. P. Herlihy and J. M. Wing. Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Program. Lang. Syst., 12(3), 1990.
[6]
M. Majuntke, D. Dobre, M. Serafini, and N. Suri. Abortable Fork-Linearizable Storage. In OPODIS, Berlin, Heidelberg, 2009. Springer-Verlag.
[7]
D. Mazières and D. Shasha. Building Secure File Systems out of Byzantine Storage. In PODC, New York, NY, USA, 2002. ACM.

Cited By

View all
  • (2011)Fork-Consistent constructions from registersProceedings of the 15th international conference on Principles of Distributed Systems10.1007/978-3-642-25873-2_20(283-298)Online publication date: 13-Dec-2011

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
PODC '11: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing
June 2011
406 pages
ISBN:9781450307192
DOI:10.1145/1993806

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2011

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. atomic storage
  2. byzantine
  3. fork-consistency

Qualifiers

  • Abstract

Conference

PODC '11
Sponsor:

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)1
Reflects downloads up to 18 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2011)Fork-Consistent constructions from registersProceedings of the 15th international conference on Principles of Distributed Systems10.1007/978-3-642-25873-2_20(283-298)Online publication date: 13-Dec-2011

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media