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
Erschienen in:
Basic Definitions and Network Traversal Algorithms Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

12. Order Constraints on Message Delivery

verfasst von : Michel Raynal

Erschienen in: Distributed Algorithms for Message-Passing Systems

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

High-level communication abstractions offer communication operations which ensure order properties on message delivery. The simplest (and best known) order property is the first in first out (FIFO) property, which ensures that, on each channel, the messages are received in their sending order. Another order property on message delivery is captured by the total order broadcast abstraction, which was presented in Sect. 7.​1.​4. This communication abstraction ensures that all the messages are delivered in the same order at each process, and this order complies with their causal sending order.
This chapter focuses first on causal message delivery. It defines the corresponding message delivery property and presents several algorithms that implement it, both for point-to-point communication and broadcast communication. Then the chapter presents new algorithms that implement the total order broadcast abstraction. Finally, the chapter plays with a channel by considering four order properties which can be associated with each channel taken individually.
When discussing a communication abstraction, it is assumed that all the messages sent at the application level are sent with the communication operation provided by this communication abstraction. Hence, there is no hidden relation on messages that will be unknown by the algorithms implementing these abstractions.

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

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

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"

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
Vorheriges Kapitel Distributed Resource Allocation
Nächstes Kapitel Rendezvous (Synchronous) Communication
Literatur
1.
A. Acharya, B.R. Badrinath, Recording distributed snapshot based on causal order of message delivery. Inf. Process. Lett. 44, 317–321 (1992) MathSciNetMATHCrossRef
12.
13.
M. Ahuja, M. Raynal, An implementation of global flush primitives using counters. Parallel Process. Lett. 5(2), 171–178 (1995) CrossRef
14.
S. Alagar, S. Venkatesan, An optimal algorithm for distributed snapshots with message causal ordering. Inf. Process. Lett. 50, 310–316 (1994) CrossRef
15.
A. Alvarez, S. Arévalo, V. Cholvi, A. Fernández, E. Jiménez, On the interconnection of message passing systems. Inf. Process. Lett. 105(6), 249–254 (2008) MATHCrossRef
24.
H. Attiya, J.L. Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. (Wiley-Interscience, New York, 2004). 414 pages. ISBN 0-471-45324-2 CrossRef
38.
R. Baldoni, A. Mostéfaoui, M. Raynal, Causal delivery of messages with real-time data in unreliable networks. Real-Time Syst. 10(3), 245–262 (1996) CrossRef
39.
R. Baldoni, R. Prakash, M. Raynal, M. Singhal, Efficient delta-causal broadcasting. Comput. Syst. Sci. Eng. 13(5), 263–270 (1998) MATH
53.
K. Birman, T. Joseph, Reliable communication in the presence of failures. ACM Trans. Comput. Syst. 5(1), 47–76 (1987) CrossRef
55.
K.P. Birman, A. Schiper, P. Stephenson, Lightweight causal and atomic group multicast. ACM Trans. Comput. Syst. 9(3), 272–314 (1991) CrossRef
67.
C. Cachin, R. Guerraoui, L. Rodrigues, Introduction to Reliable and Secure Distributed Programming, 2nd edn. (Springer, Berlin, 2012), 367 pages. ISBN 978-3-642-15259-7
84.
J.-M. Chang, N.F. Maxemchuck, Reliable broadcast protocols. ACM Trans. Comput. Syst. 2(3), 251–273 (1984) CrossRef
88.
B. Charron-Bost, G. Tel, F. Mattern, Synchronous, asynchronous, and causally ordered communications. Distrib. Comput. 9(4), 173–191 (1996) MathSciNetCrossRef
90.
D.R. Cheriton, D. Skeen, Understanding the limitations of causally and totally ordered communication, in Proc. 14th ACM Symposium on Operating System Principles (SOSP’93) (ACM Press, New York, 1993), pp. 44–57
102.
F. Cristian, H. Aghili, R. Strong, D. Dolev, Atomic broadcast: from simple message diffusion to Byzantine agreement. Inf. Comput. 118(1), 158–179 (1995) MathSciNetCrossRef
135.
U. Fridzke, P. Ingels, A. Mostéfaoui, M. Raynal, Fault-tolerant consensus-based total order multicast. IEEE Trans. Parallel Distrib. Syst. 13(2), 147–157 (2001) CrossRef
217.
A.D. Kshemkalyani, M. Singhal, Necessary and sufficient conditions on information for causal message ordering and their optimal implementation. Distrib. Comput. 11(2), 91–111 (1998) CrossRef
226.
L. Lamport, Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978) MATHCrossRef
242.
N.A. Lynch, Distributed Algorithms (Morgan Kaufmann, San Francisco, 1996), 872 pages MATH
254.
F. Mattern, Distributed algorithms and causally consistent observations, in Proc. 16th Int’l Conference on Application and Theory of Petri Nets, (Invited Paper). LNCS, vol. 935 (Springer, Berlin, 1995), pp. 21–22
255.
F. Mattern, S. Fünfrocken, A non-blocking lightweight implementation of causal order message delivery, in Proc. Int’l Dagstuhl Workshop on Theory and Practice in Distributed Systems. LNCS, vol. 938 (Springer, Berlin, 1995), pp. 197–213 CrossRef
274.
V.V. Murty, V.K. Garg, Characterization of message ordering specifications and protocols, in Proc. 7th Int’l Conference on Distributed Computer Systems (ICDCS’97) (IEEE Press, New York, 1997), pp. 492–499 CrossRef
296.
L.L. Peterson, N.C. Bucholz, R.D. Schlichting, Preserving and using context information in interprocess communication. ACM Trans. Comput. Syst. 7(3), 217–246 (1989) CrossRef
298.
R. Prakash, M. Raynal, M. Singhal, An adaptive causal ordering algorithm suited to mobile computing environments. J. Parallel Distrib. Comput. 41(1), 190–204 (1997) CrossRef
316.
M. Raynal, Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems (Morgan & Claypool, San Francisco, 2010), 251 pages. ISBN 9781608452934
324.
M. Raynal, A. Schiper, S. Toueg, The causal ordering abstraction and a simple way to implement. Inf. Process. Lett. 39(6), 343–350 (1991) MathSciNetMATHCrossRef
336.
A. Schiper, J. Eggli, A. Sandoz, A new algorithm to implement causal ordering, in Proc. 3rd Int’l Workshop on Distributed Algorithms (WDAG’89). LNCS, vol. 392 (Springer, Berlin, 1989), pp. 219–232 CrossRef
339.
F.B. Schneider, Implementing fault-tolerant services using the state machine approach. ACM Comput. Surv. 22(4), 299–319 (1990) CrossRef
340.
R. Schwarz, F. Mattern, Detecting causal relationships in distributed computations: in search of the Holy Grail. Distrib. Comput. 7, 149–174 (1994) MATHCrossRef
353.
D. Skeen, A quorum-based commit protocol, in Proc. 6th Berkeley Workshop on Distributed Data Management and Computer Networks (1982), pp. 69–80
Metadaten
Titel
Order Constraints on Message Delivery
verfasst von
Michel Raynal
Copyright-Jahr
2013
Verlag
Springer Berlin Heidelberg
Buch
Distributed Algorithms for Message-Passing Systems

Print ISBN: 978-3-642-38122-5

Electronic ISBN: 978-3-642-38123-2

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-3-642-38123-2_12