Simple Optimal Wait-free Multireader Registers
| dc.creator | Vitanyi, Paul | |
| dc.date | 2002-02-04 | |
| dc.date | 2005-12-15 | |
| dc.date.accessioned | 2026-07-07T06:34:54Z | |
| dc.date.available | 2026-07-07T06:34:54Z | |
| dc.description | Multireader shared registers are basic objects used as communication medium in asynchronous concurrent computation. We propose a surprisingly simple and natural scheme to obtain several wait-free constructions of bounded 1-writer multireader registers from atomic 1-writer 1-reader registers, that is easier to prove correct than any previous construction. Our main construction is the first symmetric pure timestamp one that is optimal with respect to the worst-case local use of control bits; the other one is optimal with respect to global use of control bits; both are optimal in time. | |
| dc.description | 11 pages LaTeX, 1 table, 2 pseudo-programs; previous version published in Proc 16th International Symposium on DIStributed Computing (DISC 2002), Lecture Notes in Computer Science, Vol 2508, Springer-Verlag, Berlin, 118-132. New version eliminates error in the protocol (merges a split scan operation that proved problematic) and defers the formal proof to a planned future I/O automaton version | |
| dc.identifier | https://arxiv.org/abs/cs/0202003 | |
| dc.identifier | http://arxiv.org/abs/cs/0202003 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/99665 | |
| dc.subject | Distributed, Parallel, and Cluster Computing | |
| dc.subject | F.1.2; C.2.4; B.3.2; B.4.3; D.1.3; D.4.1; D.4.4 | |
| dc.title | Simple Optimal Wait-free Multireader Registers | |
| dc.type | text |