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
Distributed Computing
Published in: Distributed Computing 5/2016

01-10-2016

The computability of relaxed data structures: queues and stacks as examples

Authors: Nir Shavit, Gadi Taubenfeld

Published in: Distributed Computing | Issue 5/2016

Log in

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

search-config
loading …

Abstract

Most concurrent data structures being designed today are versions of known sequential data structures. However, in various cases it makes sense to relax the semantics of traditional concurrent data structures in order to get simpler and possibly more efficient and scalable implementations. For example, when solving the classical producer-consumer problem by implementing a concurrent queue, it might be enough to allow the dequeue operation (by a consumer) to return and remove one of the two oldest values in the queue, and not necessarily the oldest one. We define infinitely many possible relaxations of several traditional data structures and objects: queues, stacks, multisets and registers, and examine their relative computational power.
previous article Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring

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
Footnotes
1
The enqueue operation inserts a value to the queue and the dequeue operation returns and removes the oldest value in the queue. That is, the values are dequeued in the order in which they were enqueued. The peek operation reads the oldest value in the queue without removing it. If the queue is empty the dequeue and the peek operations return a special symbol.
 
2
A position of an item in a queue or in a stack is simply the number of items which precede it plus one.
 
3
To our surprise, we could not find any publication in which it is claimed that \(CN(stack[1,1,1]) = 2\). Nevertheless, we consider it as a known result.
 
4
This is false, if the queue initially contains one element. In such a case, two processes can solve consensus, by deciding on the input of the process that successfully dequeues the element.
 
5
Notice that we reach a contradiction, by assuming that p’s peek operation returns the first element in both passes. Since this implies that it cannot be the case that both events by p and q are peek events, there is no need to consider the sub-case where p’s peek operation returns the first element in one path and the second element is the other path.
 
6
The known constructions of a MWMR multi-valued 1-atomic register from SWMR 1-safe bits, are complicated and are not practically useful for transforming algorithms that use strong type of registers into algorithms that use weak type of registers.
 
Literature
1.
Adve, S.V., Gharachorloo, K.: Shared memory consistency models: a tutorial. IEEE Comput. 29(12), 66–76 (1996)CrossRef
2.
Afek, Y., Korland, G., Natanzon, M., Shavit, N.: Scalable producer-consumer pools based on elimination-diffraction trees. In: Proceedings of the 16th International Euro-Par Conference on Parallel Processing: Part II, Euro-Par’10, pp. 151–162, (2010)
3.
Afek, Y., Korland, G., Yanovsky, E.: Quasi-linearizability: relaxed consistency for improved concurrency. In: Proceedings of the 14th International Conference on Principles of Distributed Systems, OPODIS’10, pp. 395–410 (2010)
4.
Attiya, H., Guerraoui, R., Hendler, D., Kuznetsov, P.: The complexity of obstruction-free implementations. J. ACM 56(4), 1–33 (2009)MathSciNetCrossRefMATH
5.
Borowsky, E., Gafni, E.: Generalizecl FLP impossibility result for \(t\)-resilient asynchronous computations. In: Proceedings of 25th ACM Symposium on Theory of Computing, pp. 91–100 (1993)
6.
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.
Gidron, E., Keidar, I., Perelman, D., Perez, Yonathan Y.: Salsa: scalable and low synchronization numa-aware algorithm for producer-consumer pools. In: Proceeding of 24th Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’12, pp. 151–160 (2012)
9.
Henzinger, T., Kirsch, C., Payer, H., Sezgin, A., Sokolova, A.: Quantitative relaxation of concurrent data structures. SIGPLAN Not. 48(1), 317–328 (2013)MATH
10.
Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann Publishers, Burlington (2008)
11.
Herlihy, M.P.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991)CrossRef
12.
Herlihy, M.P., Luchangco, V., Moir, M.: Obstruction-free synchronization: double-ended queues as an example. In: Proceedings of the 23rd International Conference on Distributed Computing Systems, p. 522 (2003)
13.
14.
Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)CrossRef
15.
Jayanti, P., Toueg, S.: Some results on the impossibility, universality, and decidability of consensus. In: Proceedings of the 6th International Workshop on Distributed Algorithms: LNCS 674, pp. 69–84 (1992)
16.
Kirsch, C., Payer, H., Röck, H., Sokolova, A.: Performance, scalability, and semantics of concurrent fifo queues. In: Proceedings of the 12th International Conference on Algorithms and Architectures for Parallel Processing—Volume Part I, LNCS 7439, pp. 273–287 (2012)
17.
Lamport, L.: How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Trans. Comput. 28(9), 690–691 (1979)CrossRefMATH
18.
19.
20.
Lamport, L.: On interprocess communication, parts I and II. Distrib. Comput. 1(2), 77–101 (1986)CrossRefMATH
21.
Loui, M.C., Abu-Amara, H.: Memory requirements for agreement among unreliable asynchronous processes. Adv. Comput. Res. 4, 163–183 (1987)MathSciNet
22.
McKenney, P.E.: Memory ordering in modern microprocessors, part i. Linux J. 136, 2 (2005). (Revised April 2009.)
23.
McKenney, P.E.: Memory ordering in modern microprocessors, part ii. Linux J. 137, 2 (2005). (Revised April 2009.)
24.
Mckenney, P.E.: Memory barriers: a hardware view for software hackers (2009, unpublished)
25.
Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. J. ACM 27(2), 228–234 (1980)
26.
Saks, M., Zaharoglou, F.: Wait-free \(k\)-set agreement is impossible: the topology of public knowledge. SIAM J. Comput. 29, 1449–1483 (2000)MathSciNetCrossRefMATH
27.
Shavit, N.: Data structures in the multicore age. Commun. ACM 54(3), 76–84 (2011)CrossRef
28.
Shavit, N., Taubenfeld, G.: The computability of relaxed data structures: queues and stacks as examples. In: 22nd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2015) (July 2015)
29.
Sundell, H., Gidenstam, A., Papatriantafilou, M., Tsigas, P.: A lock-free algorithm for concurrent bags. In: Proceedings of the Twenty-third Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’11, pp. 335–344 (2011)
30.
Taubenfeld, G.: Synchronization Algorithms and Concurrent Programming. Pearson / Prentice-Hall, Upper Saddle River (2006). ISBN 0-131-97259-6
31.
Metadata
Title
The computability of relaxed data structures: queues and stacks as examples
Authors
Nir Shavit
Gadi Taubenfeld
Publication date
01-10-2016
Publisher
Springer Berlin Heidelberg
Published in
Distributed Computing / Issue 5/2016
Print ISSN: 0178-2770
Electronic ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-016-0272-0

Other articles of this Issue 5/2016

Distributed Computing 5/2016 Go to the issue

OriginalPaper

Randomized mutual exclusion on a multiple access channel

OriginalPaper

Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring

OriginalPaper

Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems

OriginalPaper

Distributed algorithms for barrier coverage using relocatable sensors

Premium Partner

    Image Credits