TY - GEN

T1 - Reading many variables in one atomic operation solutions with linear or sublinear complexity

AU - Kirousis, Lefteris M.

AU - Spirakis, Paul

AU - Tsigas, Philippas

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.

PY - 1992

Y1 - 1992

N2 - We address the problem of reading more than one variables (components) X1,…, Xc, all in one atomic operation, by a process called the reader, while each of these variables are being written by a set of writers. All operations (i.e. both reads and writes) are assumed to be totally asynchronous and wait-free. The previous algorithms for this problem require at best quadratic time and space complexity (the time complexity of a construction is the number of sub-operations of a high-level operation and its space complexity is the number of atomic shared variables it needs). We provide a (deterministic) solution which has linear (in the number of processes) space complexity, linear time complexity for a read operation and constant time complexity for a write. Our solution does not make use of time-stamps. Rather, it is the memory location where a write writes that differentiates it from the other writes. Now, introducing randomness in the location where a reader gets the value it returns, we get a conceptually very simple probabilistic algorithm. This is the first probabilistic algorithm for the problem. Its space complexity as well as the time complexity of a read operation are both sublinear. The time complexity of a write is still constant. On the other hand, under the Archimedean assumption, we get a protocol whose both time and space complexity do not depend on the number of writers but are linear in the number of components only (the time complexity of a write operation is still constant).

AB - We address the problem of reading more than one variables (components) X1,…, Xc, all in one atomic operation, by a process called the reader, while each of these variables are being written by a set of writers. All operations (i.e. both reads and writes) are assumed to be totally asynchronous and wait-free. The previous algorithms for this problem require at best quadratic time and space complexity (the time complexity of a construction is the number of sub-operations of a high-level operation and its space complexity is the number of atomic shared variables it needs). We provide a (deterministic) solution which has linear (in the number of processes) space complexity, linear time complexity for a read operation and constant time complexity for a write. Our solution does not make use of time-stamps. Rather, it is the memory location where a write writes that differentiates it from the other writes. Now, introducing randomness in the location where a reader gets the value it returns, we get a conceptually very simple probabilistic algorithm. This is the first probabilistic algorithm for the problem. Its space complexity as well as the time complexity of a read operation are both sublinear. The time complexity of a write is still constant. On the other hand, under the Archimedean assumption, we get a protocol whose both time and space complexity do not depend on the number of writers but are linear in the number of components only (the time complexity of a write operation is still constant).

UR - http://www.scopus.com/inward/record.url?scp=85029787723&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85029787723&partnerID=8YFLogxK

U2 - 10.1007/BFb0022450

DO - 10.1007/BFb0022450

M3 - Conference contribution

AN - SCOPUS:85029787723

SN - 9783540552369

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 229

EP - 241

BT - Distributed Algorithms - 5th International Workshop, WDAG 1991, Proceedings

A2 - Spirakis, Paul G.

A2 - Kirousis, Lefteris

A2 - Toueg, Sam

PB - Springer Verlag

T2 - 5th International Workshop on Distributed Algorithms, WDAG 1991

Y2 - 7 October 1991 through 9 October 1991

ER -