Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2016.32
URN: urn:nbn:de:0030-drops-71010
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7101/
Chen, Tian Ze ; Wei, Yuanhao
Step Optimal Implementations of Large Single-Writer Registers
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{chen_et_al:LIPIcs:2017:7101,
author = {Tian Ze Chen and Yuanhao Wei},
title = {{Step Optimal Implementations of Large Single-Writer Registers}},
booktitle = {20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
pages = {32:1--32:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-031-6},
ISSN = {1868-8969},
year = {2017},
volume = {70},
editor = {Panagiota Fatourou and Ernesto Jim{\'e}nez and Fernando Pedone},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7101},
URN = {urn:nbn:de:0030-drops-71010},
doi = {10.4230/LIPIcs.OPODIS.2016.32},
annote = {Keywords: atomic register, regular register, wait-free implementation, single writer, optimal}
}
| Keywords: | atomic register, regular register, wait-free implementation, single writer, optimal | |
| Seminar: | 20th International Conference on Principles of Distributed Systems (OPODIS 2016) | |
| Issue date: | 2017 | |
| Date of publication: | 06.04.2017 |
