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:
An Innovative Combinatorial Approach for the Spanning Tree Entropy in Flower Network Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Agreement Functions for Distributed Computing Models

verfasst von : Petr Kuznetsov, Thibault Rieutord

Erschienen in: Networked Systems

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The paper proposes a surprisingly simple characterization of a large class of models of distributed computing, via an agreement function: for each set of processes, the function determines the best level of set consensus these processes can reach. We show that the task computability of a large class of fair adversaries that includes, in particular superset-closed and symmetric one, is precisely captured by agreement functions.

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 Aspect-Oriented State Machines for Resolving Conflicts in XACML Policies
Nächstes Kapitel Anomalies and Similarities Among Consensus Numbers of Variously-Relaxed Queues
Fußnoten
1
In the “universal” task of consensus, every process has a private input value, and is expected to produce an output value, so that (validity) every output is an input of some process, (agreement) no two processes produce different output values, and (termination) every process taking sufficiently many steps returns.
 
2
Note that the extended BG-simulation provides a mechanism which ensures that a simulation step is not blocked forever by a no longer active BG simulator.
 
3
\(\mathcal {A}|_P\) is the adversary consisting of all live sets of \(\mathcal {A}\) that are subsets of P.
 
Literatur
1.
Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. ACM 40(4), 873–890 (1993)CrossRefMATH
2.
Borowsky, E., Gafni, E.: Generalized FLP impossibility result for \(t\)-resilient asynchronous computations. In: STOC, pp. 91–100. ACM Press, May 1993
3.
Borowsky, E., Gafni, E.: Immediate atomic snapshots and fast renaming. In: PODC, pp. 41–51. ACM Press, New York (1993)
4.
Borowsky, E., Gafni, E., Lynch, N.A., Rajsbaum, S.: The BG distributed simulation algorithm. Distrib. Comput. 14(3), 127–146 (2001)CrossRef
5.
Delporte-Gallet, C., Fauconnier, H., Gafni, E., Kuznetsov, P.: Wait-freedom with advice. Distrib. Comput. 28(1), 3–19 (2015)MathSciNetCrossRefMATH
6.
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Tielmann, A.: The disagreement power of an adversary. Distrib. Comput. 24(3–4), 137–147 (2011)CrossRefMATH
7.
Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)MathSciNetCrossRefMATH
8.
Gafni, E.: The extended BG-simulation and the characterization of t-resiliency. In: STOC, pp. 85–92 (2009)
9.
10.
11.
12.
Gafni, E., Kuznetsov, P.: Turning adversaries into friends: simplified, made constructive, and extended. In: Lu, C., Masuzawa, T., Mosbah, M. (eds.) OPODIS 2010. LNCS, vol. 6490, pp. 380–394. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-17653-1_​28 CrossRef
13.
Gafni, E., Kuznetsov, P.: Relating L-resilience and wait-freedom via hitting sets. In: ICDCN, pp. 191–202 (2011)
14.
Herlihy, M.: Wait-free synchronization. ACM Trans. Prog. Lang. Syst. 13(1), 123–149 (1991)CrossRef
15.
Herlihy, M., Kozlov, D.N., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, Burlington (2014)MATH
16.
Herlihy, M., Rajsbaum, S.: The topology of shared-memory adversaries. In: PODC, pp. 105–113 (2010)
17.
Herlihy, M., Rajsbaum, S.: Simulations and reductions for colorless tasks. In: PODC, pp. 253–260 (2012)
18.
19.
20.
Kuznetsov, P., Rieutord, T.: Agreement functions for distributed computing models. CoRR, abs/1004.4701 (2017)
21.
Loui, M.C., Abu-Amara, H.H.: Memory requirements for agreement among unreliable asynchronous processes. Adv. Comput. Res. 4, 163–183 (1987)MathSciNet
22.
Saks, M., Zaharoglou, F.: Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput. 29, 1449–1483 (2000)MathSciNetCrossRefMATH
23.
Metadaten
Titel
Agreement Functions for Distributed Computing Models
verfasst von
Petr Kuznetsov
Thibault Rieutord
Copyright-Jahr
2017
Buch
Networked Systems

Print ISBN: 978-3-319-59646-4

Electronic ISBN: 978-3-319-59647-1

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-59647-1_14