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

Lefteris M. Kirousis; Paul Spirakis; Philippas Tsigas

doi:10.1007/3-540-54029-6_207

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

Lefteris M. Kirousis, Paul Spirakis, Philippas Tsigas

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Let X₁,…, X_c 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.

Original language	English (US)
Title of host publication	Advances in Computing and Information – ICCI 1991 - International Conference on Computing and Information, Proceedings
Editors	Waldemar W. Koczkodaj, Frank Dehne, Frantisek Fiala
Publisher	Springer Verlag
Pages	582-587
Number of pages	6
ISBN (Print)	9783540540298
DOIs	https://doi.org/10.1007/3-540-54029-6_207
State	Published - 1991
Event	3rd International Conference on Computing and Information, ICCI 1991 - Ottawa, Canada Duration: May 27 1991 → May 29 1991

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	497 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd International Conference on Computing and Information, ICCI 1991
Country/Territory	Canada
City	Ottawa
Period	5/27/91 → 5/29/91

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-54029-6_207

Cite this

Kirousis, L. M., Spirakis, P., & Tsigas, P. (1991). Simple atomic snapshots a linear complexity solution with unbounded time-stamps. In W. W. Koczkodaj, F. Dehne, & F. Fiala (Eds.), Advances in Computing and Information – ICCI 1991 - International Conference on Computing and Information, Proceedings (pp. 582-587). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 497 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-54029-6_207

Simple atomic snapshots a linear complexity solution with unbounded time-stamps. / Kirousis, Lefteris M.; Spirakis, Paul; Tsigas, Philippas.
Advances in Computing and Information – ICCI 1991 - International Conference on Computing and Information, Proceedings. ed. / Waldemar W. Koczkodaj; Frank Dehne; Frantisek Fiala. Springer Verlag, 1991. p. 582-587 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 497 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Kirousis, LM, Spirakis, P & Tsigas, P 1991, Simple atomic snapshots a linear complexity solution with unbounded time-stamps. in WW Koczkodaj, F Dehne & F Fiala (eds), Advances in Computing and Information – ICCI 1991 - International Conference on Computing and Information, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 497 LNCS, Springer Verlag, pp. 582-587, 3rd International Conference on Computing and Information, ICCI 1991, Ottawa, Canada, 5/27/91. https://doi.org/10.1007/3-540-54029-6_207

Kirousis LM, Spirakis P, Tsigas P. Simple atomic snapshots a linear complexity solution with unbounded time-stamps. In Koczkodaj WW, Dehne F, Fiala F, editors, Advances in Computing and Information – ICCI 1991 - International Conference on Computing and Information, Proceedings. Springer Verlag. 1991. p. 582-587. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-54029-6_207

Kirousis, Lefteris M. ; Spirakis, Paul ; Tsigas, Philippas. / Simple atomic snapshots a linear complexity solution with unbounded time-stamps. Advances in Computing and Information – ICCI 1991 - International Conference on Computing and Information, Proceedings. editor / Waldemar W. Koczkodaj ; Frank Dehne ; Frantisek Fiala. Springer Verlag, 1991. pp. 582-587 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{108280b37ce84856bccc7ca7458ee3e6,

title = "Simple atomic snapshots a linear complexity solution with unbounded time-stamps",

abstract = "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.",

author = "Kirousis, {Lefteris M.} and Paul Spirakis and Philippas Tsigas",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1991.; 3rd International Conference on Computing and Information, ICCI 1991 ; Conference date: 27-05-1991 Through 29-05-1991",

year = "1991",

doi = "10.1007/3-540-54029-6_207",

language = "English (US)",

isbn = "9783540540298",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "582--587",

editor = "Koczkodaj, {Waldemar W.} and Frank Dehne and Frantisek Fiala",

booktitle = "Advances in Computing and Information – ICCI 1991 - International Conference on Computing and Information, Proceedings",

}

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 -

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

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this