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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Leader Election in Rings with Bounded Multiplicity (Short Paper) Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Wait-Free Solvability of Colorless Tasks in Anonymous Shared-Memory Model

verfasst von : Nayuta Yanagisawa

Erschienen in: Stabilization, Safety, and Security of Distributed Systems

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We investigate the capability of distributed systems in the anonymous asynchronous shared-memory model, in which processes have no identifiers and communicate through multi-writer/multi-reader atomic registers. The present paper assumes that an arbitrary number of processes may fail by crashing.
We propose a 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, as long as colorless tasks are concerned, that the anonymity does not reduce the computational power of the asynchronous shared-memory model.

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
Vorheriges Kapitel Searching for an Evader in an Unknown Graph by an Optimal Number of Searchers
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 12th ACM Symposium on Theory of Computing, pp. 82–93. ACM, New York (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.
Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., Reischuk, R.: Renaming in an asynchronous environment. J. ACM 37(3), 524–548 (1990)MathSciNetCrossRefMATH
5.
Attiya, H., Gorbach, A., Moran, S.: Computing in totally anonymous asynchronous shared memory systems. Inf. Comput. 173(2), 162–183 (2002)MathSciNetCrossRefMATH
6.
Chaudhuri, S.: More choices allow more faults: set consensus problems in totally asynchronous systems. Inf. Comput. 105(1), 132–158 (1993)MathSciNetCrossRefMATH
7.
Chothia, T., Chatzikokolakis, K.: A survey of anonymous peer-to-peer file-sharing. In: Enokido, T., Yan, L., Xiao, B., Kim, D., Dai, Y., Yang, L.T. (eds.) EUC 2005. LNCS, vol. 3823, pp. 744–755. Springer, Heidelberg (2005). doi:10.​1007/​11596042_​77 CrossRef
8.
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Kermarrec, A.M., Ruppert, E., et al.: Byzantine agreement with homonyms. In: Proceedings of 30th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 21–30. ACM, New York (2011)
9.
Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Kermarrec, A.M., Ruppert, E., et al.: Byzantine agreement with homonyms. Distrib. Comput. 26(5–6), 321–340 (2013)CrossRefMATH
10.
Delporte-Gallet, C., Fauconnier, H., Tran-The, H.: Byzantine agreement with homonyms in synchronous systems. In: Bononi, L., Datta, A.K., Devismes, S., Misra, A. (eds.) ICDCN 2012. LNCS, vol. 7129, pp. 76–90. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-25959-3_​6 CrossRef
11.
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
12.
Ellen, F., Fatourou, P., Ruppert, E.: The space complexity of unbounded timestamps. Distrib. Comput. 21(2), 103–115 (2008)CrossRefMATH
13.
Fich, F., Ruppert, E.: Hundreds of impossibility results for distributed computing. Distrib. Comput. 16(2–3), 121–163 (2003)CrossRef
14.
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
15.
16.
Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computing. Distrib. Comput. 20(3), 165–177 (2007)CrossRefMATH
17.
Herlihy, M., Kozlov, D., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, San Francisco (2013)MATH
18.
Herlihy, M., Rajsbaum, S.: The decidability of distributed decision tasks. In: Proceedings of Symposium on Theory of Computing, pp. 589–598. ACM, New York (1997)
19.
20.
Herlihy, M., Rajsbaum, S.: The topology of shared-memory adversaries. In: Proceedings of 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 105–113. ACM, New York (2010)
21.
Herlihy, M., Rajsbaum, S.: Simulations and reductions for colorless tasks. In: Proceedings of 2012 ACM Symposium on Principles of Distributed Computing, pp. 253–260. ACM, New York (2012)
22.
Herlihy, M., Rajsbaum, S., Raynal, M.: Power and limits of distributed computing shared memory models. Theor. Comput. Sci. 509, 3–24 (2013)MathSciNetCrossRefMATH
23.
Herlihy, M., Rajsbaum, S., Raynal, M., Stainer, J.: Computing in the presence of concurrent solo executions. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 214–225. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-54423-1_​19 CrossRef
24.
25.
26.
Junqueira, F.P., Marzullo, K.: Synchronous consensus for dependent process failures. In: Proceedings of 23rd International Conference on Distributed Computing Systems, pp. 274–283. IEEE (2003)
27.
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1996)MATH
28.
Mendes, H., Tasson, C., Herlihy, M.: Distributed computability in Byzantine asynchronous systems. In: Proceedings of 46th ACM Symposium on Theory of Computing, pp. 704–713. ACM, New York (2014)
29.
30.
Spanier, E.: Algebraic Topology, vol. 55. McGraw-Hill, New York (1966). (reprinted by Springer-Verlag)MATH
Metadaten
Titel
Wait-Free Solvability of Colorless Tasks in Anonymous Shared-Memory Model
verfasst von
Nayuta Yanagisawa
Copyright-Jahr
2016
Buch
Stabilization, Safety, and Security of Distributed Systems

Print ISBN: 978-3-319-49258-2

Electronic ISBN: 978-3-319-49259-9

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-49259-9_32

Premium Partner

    Bildnachweise