Top

Published in:

2017 | OriginalPaper | Chapter

Anomalies and Similarities Among Consensus Numbers of Variously-Relaxed Queues

Authors : Edward Talmage, Jennifer L. Welch

Published in: Networked Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Agreement Functions for Distributed Computing Models

next chapter Early Decision and Stopping in Synchronous Consensus: A Predicate-Based Guided Tour

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}^+\).

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

Attiya, H., Welch, J.L.: Sequential consistency versus linearizability. ACM Trans. Comput. Syst. 12(2), 91–122 (1994)CrossRef

Chen, W., Guangda, H., Zhang, J.: On the power of breakable objects. Theor. Comput. Sci. 503, 89–108 (2013)MathSciNetCrossRefMATH

Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)MathSciNetCrossRefMATH

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)

Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991)CrossRef

Kosa, M.J.: Time bounds for strong and hybrid consistency for arbitrary abstract data types. Chicago J. Theor. Comput. Sci. (1999)

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

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)

Title: Anomalies and Similarities Among Consensus Numbers of Variously-Relaxed Queues
Authors: Edward Talmage
Jennifer L. Welch
Publisher: Springer International Publishing
Book: Networked Systems
Print ISBN: 978-3-319-59646-4

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

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-59647-1_15

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner