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

Anomalies and Similarities Among Consensus Numbers of Variously-Relaxed Queues

verfasst von : Edward Talmage, Jennifer L. Welch

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

Shared data structures are a basic building block in distributed computing, but can be expensive to implement. One way to circumvent the high implementation cost of linearizability is to relax the sequential specification of the data type. This gives up some guarantees, for instance on the ordering of data elements, as a tradeoff against performance. We want to explore the effects of this tradeoff on the computational power of the shared data structures.
In this paper, we characterize the effects of three different types of relaxation, chosen from the literature, on the computational power of FIFO queues. By parametrically relaxing each of the three operations on a queue (Enqueue, Dequeue, Peek), we obtain an infinite 3-dimensional space for each type of relaxation. We find the consensus number, a standard measure of the computational power of shared data types, of each point in these spaces, completely describing the effect of these three types of relaxation on the computational power of queues.

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 Agreement Functions for Distributed Computing Models
Nächstes Kapitel Early Decision and Stopping in Synchronous Consensus: A Predicate-Based Guided Tour
Fußnoten
1
We use \(*\), not \(\infty \), to maintain consistency with the literature, e.g. [11]. We also use \(\emptyset \) where [11] used 0. This maintains visual consistency, while avoiding the problem that \(0<x, \forall x\in \mathbb {Z}^+\), while we want \(\emptyset >x,\forall x\in \mathbb {Z}^+\).
 
Literatur
1.
Afek, Y., Korland, G., Yanovsky, E.: Quasi-linearizability: relaxed consistency for improved concurrency. In: Lu, C., Masuzawa, T., Mosbah, M. (eds.) OPODIS 2010. LNCS, vol. 6490, pp. 395–410. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-17653-1_​29 CrossRef
2.
Attiya, H., Welch, J.L.: Sequential consistency versus linearizability. ACM Trans. Comput. Syst. 12(2), 91–122 (1994)CrossRef
3.
4.
Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)MathSciNetCrossRefMATH
5.
Henzinger, T.A., Kirsch, C.M., Payer, H., Sezgin, A., Sokolova, A.: Quantitative relaxation of concurrent data structures. In: Giacobazzi, R., Cousot, R. (eds.) The 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2013, Rome, Italy, 23–25 January 2013, pp. 317–328. ACM (2013)
6.
Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991)CrossRef
7.
Kosa, M.J.: Time bounds for strong and hybrid consistency for arbitrary abstract data types. Chicago J. Theor. Comput. Sci. (1999)
8.
Lipton, R.J., Sandberg, J.S.: PRAM: a scalable shared memory. Technical report CS-TR-180-88, Princeton University, Department of Computer Science, September 1988
9.
Lo, W.-K., Hadzilacos, V.: All of us are smarter than any of us: nondeterministic wait-free hierarchies are not robust. SIAM J. Comput. 30(3), 689–728 (2000)MathSciNetCrossRefMATH
10.
Shavit, N., Taubenfeld, G.: The computability of relaxed data structures: queues and stacks as examples. In: Scheideler, C. (ed.) Structural Information and Communication Complexity. LNCS, vol. 9439, pp. 414–428. Springer, Cham (2015). doi:10.​1007/​978-3-319-25258-2_​29 CrossRef
11.
Shavit, N., Taubenfeld, G.: The computability of relaxed data structures: queues and stacks as examples. Distrib. Comput. 29(5), 395–407 (2016)MathSciNetCrossRefMATH
12.
Talmage, E., Welch, J.L.: Improving average performance by relaxing distributed data structures. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 421–438. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-45174-8_​29
13.
Talmage, E., Welch, J.L.: Generic proofs of consensus numbers for abstract data types. In: Anceaume, E., Cachin, C., Potop-Butucaru, M.G. (eds.) 19th International Conference on Principles of Distributed Systems, OPODIS 2015, 14–17 December 2015, Rennes, France. LIPIcs, vol. 46, pp. 32:1–32:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015)
14.
Wang, J., Talmage, E., Lee, H., Welch, J.L.: Improved time bounds for linearizable implementations of abstract data types. In: 2014 IEEE 28th International Parallel and Distributed Processing Symposium, Phoenix, AZ, USA, 19–23 May 2014, pp. 691–701. IEEE Computer Society (2014)
Metadaten
Titel
Anomalies and Similarities Among Consensus Numbers of Variously-Relaxed Queues
verfasst von
Edward Talmage
Jennifer L. Welch
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_15