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

01.10.2016

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

verfasst von: Nir Shavit, Gadi Taubenfeld

Erschienen in: Distributed Computing | Ausgabe 5/2016

Einloggen

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

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.
Vorheriger Artikel Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring

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
Fußnoten
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.
 
Literatur
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.
Ellen, F., Hendler, D., Shavit, N.: On the inherent sequentiality of concurrent objects. SIAM J. Comput. 41(3), 519–536 (2012)MathSciNetCrossRefMATH
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.
Metadaten
Titel
The computability of relaxed data structures: queues and stacks as examples
verfasst von
Nir Shavit
Gadi Taubenfeld
Publikationsdatum
01.10.2016
Verlag
Springer Berlin Heidelberg
Erschienen in
Distributed Computing / Ausgabe 5/2016
Print ISSN: 0178-2770
Elektronische ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-016-0272-0

Weitere Artikel der Ausgabe 5/2016

Distributed Computing 5/2016 Zur Ausgabe

OriginalPaper

Distributed algorithms for barrier coverage using relocatable sensors

OriginalPaper

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

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