nach oben

Distributed Computing

Erschienen in:

01.06.2013

The topology of distributed adversaries

verfasst von: Maurice Herlihy, Sergio Rajsbaum

Erschienen in: Distributed Computing | Ausgabe 3/2013

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Roughly speaking, a simplicial complex is shellable if it can be constructed by gluing a sequence of n-simplexes to one another along \((n-1)\)-faces only. Shellable complexes have been widely studied because they have nice combinatorial properties. It turns out that several standard models of concurrent computation can be constructed from shellable complexes. We consider adversarial schedulers in the synchronous, asynchronous, and semi-synchronous message-passing models, as well as asynchronous shared memory. We show how to exploit their common shellability structure to derive new and remarkably succinct tight (or nearly so) lower bounds on connectivity of protocol complexes and hence on solutions to the \(k\)-set agreement task in these models. Earlier versions of material in this article appeared in the 2010 ACM Symposium on Principles of Distributed Computing (Herlihy and Rajsbaum 2010), and the International Conference on Distributed Computing (Herlihy and Rajsbaum 2010, doi:10.1145/1835698.1835724).

Vorheriger Artikel Competitive throughput in multi-hop wireless networks despite adaptive jamming

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

Choosing \(n+1\) processes rather than \(n\) simplifies the topological notation but slightly complicates the computing notation. Choosing \(n\) processes makes the opposite trade-off. We choose \(n+1\) for compatibility with prior work.

Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. ACM 40(4), 873–890 (1993)MATHCrossRef

Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., Reischuk, R.: Renaming in an asynchronous environment. J. ACM 37(3), 524–548 (1990)

Attiya, H., Borran, F., Hutle, M., Milosevic, Z., Schiper, A.: Structured Derivation of Semi-Synchronous Algorithms. In: Peleg, D. (ed.) Distributed Computing, Lecture Notes in Computer Science, vol. 6950, pp. 374–388. Springer, Berlin (2011). doi:10.1007/978-3-642-24100-0_37

Attiya, H., Dwork, C., Lynch, N., Stockmeyer, L.: Bounds on the time to reach agreement in the presence of timing uncertainty. J. ACM 41(1), 122–152 (1994). doi:10.1145/174644.174649 MathSciNetMATHCrossRef

Attiya, H., Welch, J.: Distributed Computing Fundamentals, Simulations, and Advanced Topics, 2nd Edn. Wiley, New York (2004). URL: http://www.cs.technion.ac.il/~hagit/DC/

Biran, O., Moran, S., Zaks, S.: A combinatorial characterization of the distributed 1-solvable tasks. J. Algorithms 11(3), 420–440 (1990)MathSciNetMATHCrossRef

Björner, A.: Shellable and Cohen-Macaulay partially ordered sets. Trans. Am. Math. Soc. 260(1), 159–183 (1980)MATHCrossRef

Borowsky, E., Gafni, E.: Immediate atomic snapshots and fast renaming. In: Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, PODC ’93, pp. 41–51. ACM, New York, NY, USA (1993). doi:10.1145/164051.164056

Borowsky, E., Gafni, E.: A simple algorithmically reasoned characterization of wait-free computations (extended abstract). In: PODC ’97: Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 189–198. ACM, New York, NY, USA (1997)

10.

Castañeda, A., Herlihy, M., Rajsbaum, S.: An equivariance theorem with applications to renaming. In: Proceedings of the 10th Latin American International Conference on Theoretical Informatics, LATIN’12, pp. 133–144. Springer, Berlin (2012). doi:10.1007/978-3-642-29344-3_12

11.

Chaudhuri, S.: More choices allow more faults: set consensus problems in totally asynchronous systems. Inform. Comput. 105(1), 132–158 (1993)MATHCrossRef

12.

Chaudhuri, S., Herlihy, M., Lynch, N.A., Tuttle, M.R.: Tight bounds for k-set agreement. J. ACM 47(5), 912–943 (2000). doi:10.1145/355483.355489 MathSciNetCrossRef

13.

Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Tielmann, A.: The disagreement power of an adversary. Distrib. Comput. 24(3), 137–147 (2011). doi:10.1007/s00446-010-0122-4 MATHCrossRef

14.

Dolev, D., Strong, H.R.: Authenticated algorithms for byzantine agreement. SIAM J. Comput. 12(4), 656–666 (1983)MathSciNetMATHCrossRef

15.

Fischer, M., Lynch, N.A., Paterson, M.S.: Impossibility of distributed commit with one faulty process. J. ACM 32(2), 374–382 (1985)

16.

Fischer, M.J., Lynch, N.A.: A lower bound for the time to assure interactive consistency. Inf. Process. Lett. 14(4), 183–186 (1982)

17.

Gafni, E.: Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony. In: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’98, pp. 143–152. ACM, New York, NY, USA (1998). doi:10.1145/277697.277724

18.

Gafni, E., Koutsoupias, E.: Three-processor tasks are undecidable. SIAM J. Comput. 28(3), 970–983 (1999)MathSciNetMATHCrossRef

19.

Gafni, E., Kuznetsov, P.: Relating \({\cal L}\)”-resilience and wait-freedom via hitting sets. In: Aguilera, M., Yu, H., Vaidya, N., Srinivasan, V., Choudhury, R. (eds.) Distributed Computing and Networking, Lecture Notes in Computer Science, vol. 6522, pp. 191–202. Springer, Berlin (2011)

20.

Gafni, E., Rajsbaum, S.: Distributed programming with tasks. In: Proceedings of the 14th International Conference on Principles of Distributed Systems, OPODIS’10, pp. 205–218. Springer, Berlin (2010). URL:http://portal.acm.org/citation.cfm?id=1940258

21.

Gafni, E., Rajsbaum, S., Herlihy, M.: Subconsensus tasks: Renaming is weaker than set agreement. In: Distributed Computing, 20th International Symposium, Stockholm, Sweden, September 18–20, 2006, Proceedings(DISC), Lecture Notes in Computer Science, vol. 4167, pp. 329–338. Springer, Berlin (2006)

22.

Halpern, J.Y., Moses, Y.: Knowledge and common knowledge in a distributed environment. J. ACM 37(3), 549–587 (1990). doi:10.1145/79147.79161 MathSciNetMATHCrossRef

23.

Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991). doi:10.1145/114005.102808 CrossRef

24.

Herlihy, M., Rajsbaum, S.: Set consensus using arbitrary objects (preliminary version). In: PODC ’94: Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 324–333. ACM, New York, NY, USA (1994)

25.

Herlihy, M., Rajsbaum, S.: The decidability of distributed decision tasks (extended abstract). In: STOC ’97: Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, pp. 589–598. ACM, New York, NY, USA (1997). doi:10.1145/258533.258652

26.

Herlihy, M., Rajsbaum, S.: Algebraic spans. Math. Struct. Comput. Sci. 10(4), 549–573 (2000). http://journals.cambridge.org/action/displayAbstract?aid=54601

27.

Herlihy, M., Rajsbaum, S.: Concurrent computing and shellable complexes. In: Proceedings of the 24th International Conference on Distributed Computing, DISC’10, pp. 109–123. Springer, Berlin (2010). URL:http://dl.acm.org/citation.cfm?id=1888781.1888795

28.

Herlihy, M., Rajsbaum, S.: The topology of shared-memory adversaries. In: Proceeding of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC ’10, pp. 105–113. ACM, New York, NY, USA (2010). doi:10.1145/1835698.1835724

29.

Herlihy, M., Rajsbaum, S.: Simulations and reductions for colorless tasks. In: Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, PODC ’12, pp. 253–260. ACM, New York, NY, USA (2012). doi:10.1145/2332432.2332483

30.

Herlihy, M., Rajsbaum, S., Tuttle, M.: An axiomatic approach to computing the connectivity of synchronous and asynchronous systems. Electron. Notes Theor. Comput. Sci. 230, 79–102 (2009). doi:10.1016/j.entcs.2009.02.018

31.

Herlihy, M., Rajsbaum, S., Tuttle, M.R.: Unifying synchronous and asynchronous message-passing models. In: PODC ’98: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, pp. 133–142. ACM, New York, NY, USA (1998). doi:10.1145/277697.277722

32.

Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858–923 (1999). doi:10.1145/331524.331529 MathSciNetMATHCrossRef

33.

Junqueira, F., Marzullo, K.: A framework for the design of dependent-failure algorithms: research articles. Concurr. Comput.: Pract. Exper. 19(17), 2255–2269 (2007)CrossRef

34.

Kozlov, D.: Combinatorial Algebraic Topology, Algorithms and Computation in Mathematics, vol. 21, 1st edn. Springer, Berlin (2007). doi:10.1007/978-3-540-71962-5

35.

Kuznetsov, P.: Understanding non-uniform failure models. In: Bulletin of the EATCS, 106, p. 53.77. European Association for, Theoretical Computer Science (2012)

36.

Lamport, L.: On interprocess communication (part I): basic formalism. Distrib. Comput. 1, 77–101 (1986). URL:http://citeseer.nj.nec.com/227917.html

37.

Lamport, L.: On interprocess communication (part II): algorithms. Distrib. Comput. 1(1), 203–213 (1986)MathSciNet

38.

Loui, M.C., Abu-Amara, H.H.: Memory requirements for agreement among unreliable asynchronous processes, vol. 4. JAI press, Greenwick (1987)

39.

Michailidis, D.: Fast set agreement in the presence of timing uncertainty. In: Proceedings of the Eighteenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’99, pp. 249–256. ACM, New York, NY, USA (1999). doi:10.1145/301308.301365

40.

Moses, Y., Rajsbaum, S.: A layered analysis of consensus. SIAM J. Comput. 31(4), 989–1021 (2002)MathSciNetMATHCrossRef

41.

Munkres, J.: Elements of Algebraic Topology, 2nd edn. Prentice Hall, New York (1984). URL:http://www.worldcat.org/isbn/0131816292

42.

Saks, M., Zaharoglou, F.: Wait-free k-set agreement is impossible: the topology of public knowledge. SIAM J. Comput. 29(5), 1449–1483 (2000). URL:http://epubs.siam.org/doi/abs/10.1137/S0097539796307698?journalCode=smjcat

43.

Saks, M., Zaharoglou, F.: Wait-free k-set agreement is impossible: the topology of public knowledge. SIAM J. Comput. 29(5), 1449–1483 (2000). doi:10.1145/167088.167122 MathSciNetMATHCrossRef

44.

Spanier, E.H.: Algebraic Topology. Springer, New York (1981). URL:http://www.ams.org/mathscinet-getitem?mr=666554

45.

Wang, J., Song, M.: A new algorithm to solve synchronous consensus for dependent failures. In: Proceedings of the Sixth International Conference on Parallel and Distributed Computing Applications and Technologies, PDCAT ’05, pp. 371–375. IEEE Computer Society, Washington, DC, USA (2005). doi:10.1109/PDCAT.2005.23

Titel: The topology of distributed adversaries
verfasst von: Maurice Herlihy
Sergio Rajsbaum
Publikationsdatum: 01.06.2013
Verlag: Springer-Verlag
Erschienen in: Distributed Computing / Ausgabe 3/2013
Print ISSN: 0178-2770
Elektronische ISSN: 1432-0452
DOI: https://doi.org/10.1007/s00446-013-0189-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner