TY - GEN

T1 - Simple atomic snapshots a linear complexity solution with unbounded time-stamps

AU - Kirousis, Lefteris M.

AU - Spirakis, Paul

AU - Tsigas, Philippas

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

PY - 1991

Y1 - 1991

N2 - Let X1,…, Xc be variables shared by a number of processes which operate in a totally asynchronous and wait-free manner. An operation by a process is either a write on one of the variables or a read of the values of all variables. All operations are assumed to be atomic, i.e. an execution of any number of them (including reads) must be serializable in a way compatible with the values returned by the reads. We give a new protocol implementing such operations for the case of a single-reader and one writer per variable. Our construction uses time-stamps that may take values as large as the number of operations performed. The advantages of our construction over previous (bounded time-stamps) solutions are: (i) It has very simple semantics. (ii) The time complexity of an operation (i.e. the number of its sub-operations) and the space complexity of the construction (i.e. the number of subregisters used) are equal to the number of processes involved.

AB - Let X1,…, Xc be variables shared by a number of processes which operate in a totally asynchronous and wait-free manner. An operation by a process is either a write on one of the variables or a read of the values of all variables. All operations are assumed to be atomic, i.e. an execution of any number of them (including reads) must be serializable in a way compatible with the values returned by the reads. We give a new protocol implementing such operations for the case of a single-reader and one writer per variable. Our construction uses time-stamps that may take values as large as the number of operations performed. The advantages of our construction over previous (bounded time-stamps) solutions are: (i) It has very simple semantics. (ii) The time complexity of an operation (i.e. the number of its sub-operations) and the space complexity of the construction (i.e. the number of subregisters used) are equal to the number of processes involved.

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

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

U2 - 10.1007/3-540-54029-6_207

DO - 10.1007/3-540-54029-6_207

M3 - Conference contribution

AN - SCOPUS:85028815434

SN - 9783540540298

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

SP - 582

EP - 587

BT - Advances in Computing and Information – ICCI 1991 - International Conference on Computing and Information, Proceedings

A2 - Koczkodaj, Waldemar W.

A2 - Dehne, Frank

A2 - Fiala, Frantisek

PB - Springer Verlag

T2 - 3rd International Conference on Computing and Information, ICCI 1991

Y2 - 27 May 1991 through 29 May 1991

ER -