Practically stabilizing SWMR atomic memory in message-passing systems

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

Research output: Contribution to journalArticle

9 Citations (Scopus)

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 languageEnglish (US)
Pages (from-to)692-701
Number of pages10
JournalJournal of Computer and System Sciences
Volume81
Issue number4
DOIs
StatePublished - Jun 1 2015

Fingerprint

Message passing
Message Passing
Labeling
Labels
Computer systems
Data storage equipment
Simulation
Labeling Scheme
Crash
Fault-tolerant
Arbitrary

All Science Journal Classification (ASJC) codes

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

Keywords

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

Cite this

Alon, Noga Mordechai ; Attiya, Hagit ; Dolev, Shlomi ; Dubois, Swan ; Potop-Butucaru, Maria ; Tixeuil, Sébastien. / Practically stabilizing SWMR atomic memory in message-passing systems. In: Journal of Computer and System Sciences. 2015 ; Vol. 81, No. 4. pp. 692-701.
@article{46d58f6c896846cab3dd723999dc5ee8,
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 = "Alon, {Noga Mordechai} and Hagit Attiya and Shlomi Dolev and Swan Dubois and Maria Potop-Butucaru and S{\'e}bastien Tixeuil",
year = "2015",
month = "6",
day = "1",
doi = "https://doi.org/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",

}

Alon, NM, Attiya, H, Dolev, S, Dubois, S, Potop-Butucaru, M & Tixeuil, S 2015, 'Practically stabilizing SWMR atomic memory in message-passing systems', Journal of Computer and System Sciences, vol. 81, no. 4, pp. 692-701. https://doi.org/10.1016/j.jcss.2014.11.014

Practically stabilizing SWMR atomic memory in message-passing systems. / Alon, Noga Mordechai; Attiya, Hagit; Dolev, Shlomi; Dubois, Swan; Potop-Butucaru, Maria; Tixeuil, Sébastien.

In: Journal of Computer and System Sciences, Vol. 81, No. 4, 01.06.2015, p. 692-701.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Alon, Noga Mordechai

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 - https://doi.org/10.1016/j.jcss.2014.11.014

DO - https://doi.org/10.1016/j.jcss.2014.11.014

M3 - Article

VL - 81

SP - 692

EP - 701

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 4

ER -