Practically stabilizing SWMR atomic memory in message-passing systems

Noga Alon; Hagit Attiya; Shlomi Dolev; Swan Dubois; Maria Potop-Butucaru; Sébastien Tixeuil

doi:10.1016/j.jcss.2014.11.014

Practically stabilizing SWMR atomic memory in message-passing systems

Noga Alon, Hagit Attiya, Shlomi Dolev, Swan Dubois, Maria Potop-Butucaru, Sébastien Tixeuil

Research output: Contribution to journal › Article › peer-review

18 Scopus citations

Abstract

A fault-tolerant and practically stabilizing simulation of an atomic register is presented. The simulation works in asynchronous message-passing systems, and allows a minority of processes to crash. The simulation stabilizes in a practically stabilizing manner, by reaching a long execution in which it runs correctly. A key element in the simulation is a new combinatorial construction of a bounded labeling scheme accommodating arbitrary labels, including those not generated by the scheme itself.

Original language	English (US)
Pages (from-to)	692-701
Number of pages	10
Journal	Journal of Computer and System Sciences
Volume	81
Issue number	4
DOIs	https://doi.org/10.1016/j.jcss.2014.11.014
State	Published - Jun 1 2015
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Keywords

Message passing
Self-stabilization
Shared memory
Single writer multiple reader register

Access to Document

10.1016/j.jcss.2014.11.014

Cite this

@article{1dcf3651a44142a78f04d62a3a6817b0,

title = "Practically stabilizing SWMR atomic memory in message-passing systems",

abstract = "A fault-tolerant and practically stabilizing simulation of an atomic register is presented. The simulation works in asynchronous message-passing systems, and allows a minority of processes to crash. The simulation stabilizes in a practically stabilizing manner, by reaching a long execution in which it runs correctly. A key element in the simulation is a new combinatorial construction of a bounded labeling scheme accommodating arbitrary labels, including those not generated by the scheme itself.",

keywords = "Message passing, Self-stabilization, Shared memory, Single writer multiple reader register",

author = "Noga Alon and Hagit Attiya and Shlomi Dolev and Swan Dubois and Maria Potop-Butucaru and S{\'e}bastien Tixeuil",

note = "Publisher Copyright: {\textcopyright} 2014 Elsevier Inc.",

year = "2015",

month = jun,

day = "1",

doi = "10.1016/j.jcss.2014.11.014",

language = "English (US)",

volume = "81",

pages = "692--701",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "4",

}

TY - JOUR

T1 - Practically stabilizing SWMR atomic memory in message-passing systems

AU - Alon, Noga

AU - Attiya, Hagit

AU - Dolev, Shlomi

AU - Dubois, Swan

AU - Potop-Butucaru, Maria

AU - Tixeuil, Sébastien

PY - 2015/6/1

Y1 - 2015/6/1

N2 - A fault-tolerant and practically stabilizing simulation of an atomic register is presented. The simulation works in asynchronous message-passing systems, and allows a minority of processes to crash. The simulation stabilizes in a practically stabilizing manner, by reaching a long execution in which it runs correctly. A key element in the simulation is a new combinatorial construction of a bounded labeling scheme accommodating arbitrary labels, including those not generated by the scheme itself.

AB - A fault-tolerant and practically stabilizing simulation of an atomic register is presented. The simulation works in asynchronous message-passing systems, and allows a minority of processes to crash. The simulation stabilizes in a practically stabilizing manner, by reaching a long execution in which it runs correctly. A key element in the simulation is a new combinatorial construction of a bounded labeling scheme accommodating arbitrary labels, including those not generated by the scheme itself.

KW - Message passing

KW - Self-stabilization

KW - Shared memory

KW - Single writer multiple reader register

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

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

U2 - 10.1016/j.jcss.2014.11.014

DO - 10.1016/j.jcss.2014.11.014

M3 - Article

AN - SCOPUS:84925060111

SN - 0022-0000

VL - 81

SP - 692

EP - 701

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 4

ER -

Practically stabilizing SWMR atomic memory in message-passing systems

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this