Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Computing
Published in: Computing 9/2019

22-09-2018

Anomalies and similarities among consensus numbers of variously-relaxed queues

Authors: Edward Talmage, Jennifer L. Welch

Published in: Computing | Issue 9/2019

Log in

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

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.
previous article On understanding price-QoS war for competitive market and confused consumers
next article Competitive clustering of stochastic communication patterns on a ring

Dont have a licence yet? Then find out more about our products and how to get one 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

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+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
Footnotes
1
This is a standard assumption and is used to clarify definitions and discussions of double-Dequeues and similar errors. It can be assumed WLOG because we have not restricted the type of the queues we consider. We can thus, when implementing a queue to hold a desired type T, instead implement one holding the pair (T,tag), putting a unique tag (such as a process id and local sequence counter) as the second element of each pair.
 
Literature
1.
Afek Y, Korland G, Yanovsky E (2010) Quasi-linearizability: Relaxed consistency for improved concurrency. In: Lu C, Masuzawa T, Mosbah M (eds) Principles of Distributed Systems– 14th International Conference, OPODIS 2010, Tozeur, Tunisia, December 14–17, 2010. Proceedings, volume 6490 of Lecture Notes in Computer Science, pp 395–410. Springer
2.
Anderson JH, Gouda MG (1990) The virtue of patience: concurrent programming with and without waiting. Technical report
3.
Attiya H, Welch JL (1994) Sequential consistency versus linearizability. ACM Trans Comput Syst 12(2):91–122CrossRef
4.
5.
Chor B, Israeli A, Li M (1987) On processor coordination using asynchronous hardware. In: Schneider Fred B, (ed) Proceedings of the sixth annual ACM symposium on principles of distributed computing, Vancouver, British Columbia, Canada, August 10–12, 1987, pp 86–97. ACM
6.
7.
Henzinger TA, Kirsch CM, Payer H, Sezgin A, Sokolova A (2013) 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 ’13, Rome, Italy, January 23–25, 2013, pp 317–328. ACM
8.
Herlihy M (1991) Wait-free synchronization. ACM Trans Program Lang Syst 13(1):124–149CrossRef
9.
10.
Lipton RJ, Sandberg JS (1988) PRAM: A scalable shared memory. Technical Report CS-TR-180-88, Princeton University, Department of Computer Science
11.
Lo W-K, Hadzilacos V (2000) All of us are smarter than any of us: nondeterministic wait-free hierarchies are not robust. SIAM J Comput 30(3):689–728MathSciNetCrossRefMATH
12.
Loui MC, Abu-Amara HH (1987) Memory requirements for agreement among unreliable asynchronous processes. Adv Comput Res 4(163–183):31
13.
Lynch Nancy A (1996) Morgan Kaufmann, Distributed Algorithms
14.
Shavit N, Taubenfeld G (2015) The computability of relaxed data structures: queues and stacks as examples. In: Scheideler C (ed) Structural information and communication complexity—22nd international colloquium, SIROCCO 2015, Montserrat, Spain, July 14-16, 2015, Post-Proceedings, volume 9439 of Lecture Notes in Computer Science, pages 414–428. Springer
15.
Shavit N, Taubenfeld G (2016) The computability of relaxed data structures: queues and stacks as examples. Distrib Comput 29(5):395–407MathSciNetCrossRefMATH
16.
Talmage E, Welch JL (2014) Improving average performance by relaxing distributed data structures. In: Kuhn F (ed) Distributed computing—28th international symposium, DISC 2014, Austin, TX, USA, October 12–15, 2014. Proceedings, volume 8784 of Lecture notes in computer science, pp 421–438. Springer
17.
Talmage E, Welch JL (2015) Generic proofs of consensus numbers for abstract data types. In: Anceaume E, Cachin C, Potop-Butucaru MG (eds) 19th international conference on principles of distributed systems, OPODIS 2015, December 14–17, 2015, Rennes, France, vol–46 of LIPIcs, pp 32:1–32:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
18.
Talmage E, Welch JL (2017) Anomalies and similarities among consensus numbers of relaxed queues. In: Abbadi Amr El, Garbinato B (eds), 5th Edn of the international conference on networked systems, NETYS 2017, May 17–19, 2017, Marrakech, Morocco, vol 10299 of Lecture notes in computer science. Springer
19.
Wang J, Talmage E, Lee H, Welch JL (2014) Improved time bounds for linearizable implementations of abstract data types. In: 2014 IEEE 28th international parallel and distributed processing symposium, Phoenix, AZ, USA, May 19-23, 2014, pp 691–701. IEEE Computer Society
Metadata
Title
Anomalies and similarities among consensus numbers of variously-relaxed queues
Authors
Edward Talmage
Jennifer L. Welch
Publication date
22-09-2018
Publisher
Springer Vienna
Published in
Computing / Issue 9/2019
Print ISSN: 0010-485X
Electronic ISSN: 1436-5057
DOI
https://doi.org/10.1007/s00607-018-0661-2

Other articles of this Issue 9/2019

Computing 9/2019 Go to the issue

OriginalPaper

Optimal torus exploration by oblivious robots

OriginalPaper

On understanding price-QoS war for competitive market and confused consumers

OriginalPaper

On the complexity of linearizability

Editorial

Editorial, special issue of NETYS 2015

OriginalPaper

Policy expressions and the bottom-up design of computing policies

OriginalPaper

A fully distributed learning algorithm for power allocation in heterogeneous networks

Premium Partner

    Image Credits