Step Optimal Implementations of Large Single-Writer Registers

Authors Tian Ze Chen, Yuanhao Wei



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.32.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Tian Ze Chen
Yuanhao Wei

Cite AsGet BibTex

Tian Ze Chen and Yuanhao Wei. Step Optimal Implementations of Large Single-Writer Registers. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.OPODIS.2016.32

Abstract

We present two wait-free algorithms for simulating an l-bit single-writer register from k-bit single-writer registers, for any k >= 1. Our first algorithm has big-theta(l/k) step complexity for both Read and Write and uses big-theta (4^(l-k)) registers. An interesting feature of the algorithm is that Read operations do not write to shared variables. Our second algorithm has big-theta (l/k + (log n)/k) step complexity for both Read and Write, where n is the number of readers, but uses only big-theta (nl/k + n(log n)/k) registers. Combining both algorithms gives an implementation with big-theta (l/k) step complexity using big-theta (nl/k) space for any 1 <= k < l. We also prove that any implementation with big-O (l/k) step complexity for Read requires big-omega (l/k) step complexity for Write. Since reading l-bits requires at least ceiling(l/k) reads of k-bit registers, our lower bound shows that our implementation is step optimal.
Keywords
  • atomic register
  • regular register
  • wait-free implementation
  • single writer
  • optimal

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Zahra Aghazadeh, Wojciech Golab, and Philipp Woelfel. Making objects writable. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, pages 385-395. ACM, 2014. Google Scholar
  2. Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). John Wiley Interscience, March 2004. Google Scholar
  3. Soma Chaudhuri, Martha J. Kosa, and Jennifer L. Welch. One-write algorithms for multivalued regular and atomic registers. Acta Inf., 37(3):161-192, 2000. Google Scholar
  4. Soma Chaudhuri and Jennifer L. Welch. Bounds on the costs of multivalued register implementations. SIAM J. Comput., 23(2):335-354, 1994. Google Scholar
  5. M. Herlihy and J. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, 1990. Google Scholar
  6. A. Israeli and A. Shaham. Time and space optimal implementations of atomic multi-writer register. Information and Computation, 200(1):62-106, 2005. Google Scholar
  7. Leslie Lamport. On interprocess communication. Distributed Computing, 1(2):77-101, 1986. Google Scholar
  8. Andreas Larsson, Anders Gidenstam, Phuong Hoai Ha, Marina Papatriantafilou, and Philippas Tsigas. Multiword atomic read/write registers on multiprocessor systems. ACM Journal of Experimental Algorithmics, 13, 2008. Google Scholar
  9. G. L. Peterson. Concurrent reading while writing. ACM Trans. Program. Lang. Syst., 5(1):46-55, 1983. Google Scholar
  10. K Vidyasankar. A very simple construction of 1-writer multireader multivalued atomic variable. Information Processing Letters, 37(6):323-326, 1991. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail