Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Computing
Erschienen in: Computing 1/2019

09.05.2018

Time-efficient read/write register in crash-prone asynchronous message-passing systems

verfasst von: Achour Mostéfaoui, Michel Raynal, Matthieu Roy

Erschienen in: Computing | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The atomic register is one of the most basic and useful object of computing science, and its simple read–write semantics is appealing when programming distributed systems. Hence, its implementation on top of crash-prone asynchronous message-passing systems has received a lot of attention. It was shown that having a strict minority of processes that may crash is a necessary and sufficient requirement to build an atomic register on top of a crash-prone asynchronous message-passing system. This paper visits the notion of a fast implementation of an atomic register, and presents a new time-efficient asynchronous algorithm that reduces latency in many cases: a write operation always costs a round-trip delay, while a read operation costs a round-trip delay in favorable circumstances (intuitively, when it is not concurrent with a write). When designing this algorithm, the design spirit was to be as close as possible to the original algorithm proposed by Attiya, Bar-Noy, and Dolev.
Vorheriger Artikel Special Issue on NETYS’2016
Nächster Artikel The out-of-core KNN awakens: the light side of computation force on large datasets

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
Considering the three-component model where each reader is also a server (i.e., \(R=S\)), we obtain a two-component model with one writer and reader-server processes. In this model, the necessary and sufficient condition \((|R|< \frac{|S|}{t}-2)\) can never be satisfied, which means that, it is impossible to design a fast implementation of a SWMR atomic register in such a two-component model.
 
2
Another example of a non-functional property is quiescence. This property is on algorithms implementing reliable communication on top of unreliable networks [1]. It states that the number of underlying implementation messages generated by an application message must be finite. Hence, if there is a time after which no application process sends messages, there is a time after which the system is quiescent.
 
3
Let us observe that, due to asynchrony, it is possible that \(wsn_i>wsn\) when \(p_i\) receives a message write(wsn, v) for the first time.
 
4
Messages state(rsn, x) are sent by the processes that received read(rsn) before \(\tau _w\), while the messages state\((rsn,x+1)\) are sent by the processes that received read(rsn) between \(\tau _w\) and \(\tau _r+\varDelta = \tau _w+\epsilon \).
 
Literatur
1.
2.
Attiya H, Bar-Noy A, Dolev D (1995) Sharing memory robustly in message passing systems. J ACM 42(1):121–132CrossRefMATH
3.
Attiya H, Welch J (2004) Distributed computing: fundamentals, simulations and advanced topics, 2nd edn. Wiley, HobokenCrossRefMATH
4.
Dutta P, Guerraoui R, Levy R, Chakraborty A (2004) How fast can a distributed atomic read be? In: Proceedings of 23rd ACM symposium on principles of distributed computing (PODC’04 ), ACM Press, pp 236–245
5.
6.
Herlihy MP, Wing JM (1990) Linearizability: a correctness condition for concurrent objects. ACM Trans Program Lang Syst 12(3):463–492CrossRef
7.
Hadjistasi T, Nicolaou N, Schwarzmann AA (2017) Oh-RAM! One and a half round atomic memory. In: Proceedings of 5th international conference on networked systems (NETYS’17), Springer LNCS 10299, pp 117–132
8.
Kramer SN (1956) History begins at sumer: thirty-nine firsts in man’s recorded history. University of Pennsylvania Press, Philadelphia. ISBN 978-0-8122-1276-1
9.
10.
Lynch NA (1996) Distributed algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA. ISBN 978-1-55860-384-4MATH
11.
Mostéfaoui A, Raynal M (2026) Two-bit messages are sufficient to implement atomic read/write registers in crash-prone systems. In: Proceedings of 35th ACM symposium on principles of distributed computing (PODC’16), ACM Press, pp 381–390
12.
Raynal M (2013) Distributed algorithms for message-passing systems. Springer, Heilderberg. ISBN 978-3-642-38122-5CrossRefMATH
13.
Raynal M (2013) Concurrent programming: algorithms, principles and foundations. Springer, Heilderberg. ISBN 978-3-642-32026-2CrossRefMATH
14.
Raynal M (2018) Fault-tolerant message-passing distributed systems: an algorithmic approach. Springer, Berlin, p 550CrossRef
15.
Turing AM (1936) On computable numbers with an application to the Entscheidungsproblem. Proc Lond Math Soc 42:230–265MathSciNetMATH
16.
Vukolic M (2012) Quorum systems, with applications to storage and consensus. Morgan & Claypool Publishers, San Rafael. ISBN 978-1-60845-683-3
Metadaten
Titel
Time-efficient read/write register in crash-prone asynchronous message-passing systems
verfasst von
Achour Mostéfaoui
Michel Raynal
Matthieu Roy
Publikationsdatum
09.05.2018
Verlag
Springer Vienna
Erschienen in
Computing / Ausgabe 1/2019
Print ISSN: 0010-485X
Elektronische ISSN: 1436-5057
DOI
https://doi.org/10.1007/s00607-018-0615-8

Weitere Artikel der Ausgabe 1/2019

Computing 1/2019 Zur Ausgabe

OriginalPaper

The out-of-core KNN awakens: the light side of computation force on large datasets

Editorial

Special Issue on NETYS’2016

OriginalPaper

A mechanized refinement proof of the Chase–Lev deque using a proof system

OriginalPaper

Waiting in concurrent algorithms