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
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 2/2019

13.11.2017

Wait-free Solvability of Colorless Tasks in Anonymous Shared-memory Model

verfasst von: Nayuta Yanagisawa

Erschienen in: Theory of Computing Systems | Ausgabe 2/2019

Einloggen

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

search-config
loading …

Abstract

We investigate the fault-tolerant capability of distributed systems in anonymous and unreliable settings. In the anonymous model, processes have no identifiers and execute an identical code. The present paper assumes that processes are prone to crash failures and communicate via multi-writer/multi-reader shared registers. We study the wait-free solvability of colorless tasks in the anonymous model. Especially, we propose an anonymous full-information protocol for colorless tasks and give a topological characterization of colorless tasks that are wait-free solvable in the anonymous model. The characterization implies that the anonymity does not reduce the computational power of the asynchronous shared-memory model as long as colorless tasks are concerned. We also show that some of the existing topological arguments on the eponymous model apply to the anonymous one.
Vorheriger Artikel Synchronous Gathering without Multiplicity Detection: a Certified Algorithm
Nächster Artikel Packet Efficient Implementation of the Omega Failure Detector

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 "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

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
Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. ACM 40(4), 873–890 (1993)CrossRefMATH
2.
Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC), pp. 82–93 (1980)
3.
Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235–253 (2006)CrossRefMATH
4.
Aspnes, J.: Slightly smaller splitter networks. Tech. Rep. YALEU/DCS/TR-1438 Yale University Department of Computer Science (2010)
5.
Aspnes, J., Fich, F.E., Ruppert, E.: Relationships between broadcast and shared memory in reliable anonymous distributed systems. Distrib. Comput. 18(3), 209–219 (2006)CrossRefMATH
6.
Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., Reischuk, R.: Renaming in an asynchronous environment. J. ACM 37(3), 524–548 (1990)MathSciNetCrossRefMATH
7.
Attiya, H., Gorbach, A., Moran, S.: Computing in totally anonymous asynchronous shared memory systems. Inf. Comput. 173(2), 162–183 (2002)MathSciNetCrossRefMATH
8.
Baldoni, R., Bonomi, S., Raynal, M.: Value-based sequential consistency for set objects in dynamic distributed systems. In: Proceedings of the 16th International Euro-Par Conference (Euro-Par), pp. 523–534 (2010)
9.
Baldoni, R., Bonomi, S., Raynal, M.: Implementing set objects in dynamic distributed systems. J. Comput. Syst. Sci. 82(5), 654–689 (2016)MathSciNetCrossRefMATH
10.
Borowsky, E., Gafni, E.: Immediate atomic snapshots and fast renaming. In: Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 41–51 (1993)
11.
Capdevielle, C., Johnen, C., Kuznetsov, P., Milani, A.: On the Uncontended Complexity of Anonymous Consensus. In: Anceaume, E., Cachin, C., Potop-Butucaru, M. (eds.) 19th International Conference on Principles of Distributed Systems (OPODIS 2015), Leibniz International Proceedings in Informatics (LIPIcs), vol. 46, pp 1–16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl (2016)
12.
Chaudhuri, S.: More choices allow more faults: Set consensus problems in totally asynchronous systems. Inf. Comput. 105(1), 132–158 (1993)MathSciNetCrossRefMATH
13.
Chothia, T., Chatzikokolakis, K.: A survey of anonymous peer-to-peer file-sharing. In: Proceedings of Satellite Workshop of the International Conference on Embedded and Ubiquitous Systems (EUS), pp. 744–755 (2005)
14.
Delporte-Gallet, C., Fauconnier, H.: Two consensus algorithms with atomic registers and failure detector ω. In: Proceedings of the 10th International Conference on Distributed Computing and Networking (ICDCN), pp. 251–262 (2009)
15.
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Kermarrec, A.M., Ruppert, E., Tran-The, H.: Byzantine agreement with homonyms. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 21–30 (2011)
16.
Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approximate agreement in the presence of faults. J. ACM 33(3), 499–516 (1986)MathSciNetCrossRefMATH
17.
Fich, F., Ruppert, E.: Hundreds of impossibility results for distributed computing. Distrib. Comput. 16(2), 121–163 (2003)CrossRef
18.
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
19.
20.
Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computing. Distrib. Comput. 20(3), 165–177 (2007)CrossRefMATH
21.
Herlihy, M., Kozlov, D., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann (2013)
22.
Herlihy, M., Rajsbaum, S.: The decidability of distributed decision tasks (extended abstract). In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), pp. 589–598 (1997)
23.
24.
Herlihy, M., Rajsbaum, S.: The topology of shared-memory adversaries. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 105–113 (2010)
25.
Herlihy, M., Rajsbaum, S.: Simulations and reductions for colorless tasks. In: Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (PODC), pp. 253–260 (2012)
26.
Herlihy, M., Rajsbaum, S., Raynal, M.: Power and limits of distributed computing shared memory models. Theor. Comput. Sci. 509, 3–24 (2013)MathSciNetCrossRefMATH
27.
Herlihy, M., Rajsbaum, S., Raynal, M., Stainer, J.: Computing in the presence of concurrent solo executions. In: Proceedings of the 11th Latin American Theoretical Informatics Symposium (LATIN), pp. 214–225 (2014)
28.
29.
Herlihy, M.P., Wing, J.M.: Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463–492 (1990)CrossRef
30.
Jayanti, P., Toueg, S.: Wakeup under read/write atomicity. In: Proceedings of the 4th International Workshop on Distributed Algorithms, pp. 277–288 (1991)
31.
Junqueira, F.P., Marzullo, K.: Synchronous consensus for dependent process failures. In: Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS), pp. 274–283 (2003)
32.
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann (1996)
33.
Mendes, H., Tasson, C., Herlihy, M.: Distributed computability in byzantine asynchronous systems. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pp. 704–713 (2014)
34.
35.
Ruppert, E.: The anonymous consensus hierarchy and naming problems. In: Proceedings of the 11th International Conference on Principles of Distributed Systems (OPODIS), pp. 386–400 (2007)
36.
Spanier, E.: Algebraic Topology, vol. 55. McGraw-Hill. (1966). (reprinted by Springer-Verlag)
37.
Yanagisawa, N.: Wait-free solvability of colorless tasks in anonymous shared-memory model. In: Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 415–429 (2016)
Metadaten
Titel
Wait-free Solvability of Colorless Tasks in Anonymous Shared-memory Model
verfasst von
Nayuta Yanagisawa
Publikationsdatum
13.11.2017
Verlag
Springer US
Erschienen in
Theory of Computing Systems / Ausgabe 2/2019
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-017-9819-0

Weitere Artikel der Ausgabe 2/2019

Theory of Computing Systems 2/2019 Zur Ausgabe

OriginalPaper

Synchronous Gathering without Multiplicity Detection: a Certified Algorithm

OriginalPaper

Self-Stabilizing Byzantine Clock Synchronization with Optimal Precision

OriginalPaper

Packet Efficient Implementation of the Omega Failure Detector

OriginalPaper

Self-Stabilizing Metric Graphs

OriginalPaper

Making Local Algorithms Wait-Free: the Case of Ring Coloring

OriginalPaper

On-Line Path Computation and Function Placement in SDNs