t-Resilient Immediate Snapshot Is Impossible

详细信息    查看全文

• 关键词：Asynchronous system ; Atomic read/write register ; Consensus ; Distributed computability ; Immediate snapshot ; Impossibility ; Iterated model ; k ; Set Agreement ; Linearizability ; Process crash failure ; Snapshot object ; t ; Resilience ; Wait ; freedom
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9988
• 期：1
• 页码：177-191
• 全文大小：271 KB
• 参考文献：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)CrossRef MATH
  2.Anderson, J.: Multi-writer composite registers. Distrib. Comput. 7(4), 175–195 (1994)CrossRef
  3.Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., Reischuk, R.: Renaming in an asynchronous environment. J. ACM 37(3), 524–548 (1990)MathSciNet CrossRef MATH
  4.Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics, 2nd edn. Wiley-Interscience, New York (2004). 414 pagesCrossRef MATH
  5.Borowsky E., Gafni E.: Immediate atomic snapshots and fast renaming. In: Proceedings of the 12th ACM Symposium on Principles of Distributed Computing (PODC 1993), pp. 41–50 (1993)
  6.Borowsky E. and Gafni E., Generalized FLP impossibility results for \(t\) -resilient asynchronous computations. In: Proceedings of the 25th ACM Symposium on Theory of Computation (STOC 1993), California, USA, pp. 91–100 (1993)
  7.Borowsky E., Gafni E.: A simple algorithmically reasoned characterization of wait-free computations. In: Proceedings of the 16th ACM Symposium on Principles of Distributed Computing (PODC 1997), pp. 189–198. ACM Press (1997)
  8.Borowsky, E., Gafni, E., Lynch, N., Rajsbaum, S.: The BG distributed simulation algorithm. Distrib. Comput. 14, 127–146 (2001)CrossRef
  9.Castañeda, A., Rajsbaum, S., Raynal, M.: Specifying concurrent problems: beyond linearizability and up to tasks. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 420–435. Springer, Heidelberg (2015). doi:10.​1007/​978-3-662-48653-5_​28 CrossRef
  10.Chandra, T., Hadzilacos, V., Toueg, S.: The weakest failure detector for solving consensus. J. ACM 43(4), 685–722 (1996)MathSciNet CrossRef MATH
  11.Chaudhuri, S.: More choices allow more faults: set consensus problems in totally asynchronous systems. Inf. Comput. 105(1), 132–158 (1993)MathSciNet CrossRef MATH
  12.Delporte, C., Fauconnier, H., Rajsbaum, S., Raynal, M.: \(t\) -resilient immediate snapshot is impossible. Technical report 2036, IRISA, Université de Rennes (F): http://​hal.​inria.​fr/​hal-01313556
  13.Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)MathSciNet CrossRef MATH
  14.Gafni E., Kuznetsov P., and Manolescu C., A generalized asynchronous computability theorem. In: Proceedings of the 33th ACM Symposium on Principles of Distributed Computing (PODC 1994), pp. 222–231. ACM Press (2014)
  15.Gafni, E., Rajsbaum, S.: Recursion in distributed computing. In: Dolev, S., Cobb, J., Fischer, M., Yung, M. (eds.) SSS 2010. LNCS, vol. 6366, pp. 362–376. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-16023-3_​30 CrossRef
  16.Herlihy, M.P.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124–149 (1991)CrossRef
  17.Herlihy, M.P., Kozlov, D., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann/Elsevier, New York (2014). 336 pages. ISBN 9780124045781MATH
  18.Herlihy, M.P., Luchangco, V., Moir, M.: Obstruction-free synchronization: double-ended queues as an example. In: Proceedings of the 23th International IEEE Conference on Distributed Computing Systems (ICDCS 2003), pp. 522–529. IEEE Press (2003)
  19.Herlihy, M., Rajsbaum, S., Raynal, M.: Power and limits of distributed computing shared memory models. Theor. Comput. Sci. 509, 3–24 (2013)MathSciNet CrossRef MATH
  20.Herlihy, M.P., Shavit, N.: A simple constructive computability theorem for wait-free computation. In: Proceedings of the 26th ACM Symposium on Theory of Computing (STOC 1994), pp. 243–252. ACM Press (1994)
  21.Herlihy, M.P., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858–923 (1999)MathSciNet CrossRef MATH
  22.Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Programm. Lang. Syst. 12(3), 463–492 (1990)CrossRef
  23.Lamport, L.: On interprocess communication, Part I: basic formalism. Distrib. Comput. 1(2), 77–85 (1986)CrossRef MATH
  24.Lo, W.-K., Hadzilacos, V.: Using failure detectors to solve consensus in asynchronous shared-memory systems. In: Tel, G., Vitányi, P. (eds.) WDAG 1994. LNCS, vol. 857, pp. 280–295. Springer, Heidelberg (1994). doi:10.​1007/​BFb0020440 CrossRef
  25.Loui, M., Abu-Amara, H.: Memory requirements for agreement among unreliable asynchronous processes. Adv. Comput. Res. 4, 163–183 (1987)MathSciNet
  26.Neiger G., Set-linearizability. In: Brief Announcement in Proceedings of the 13th ACM Symposium on Principles of Distributed Computing (PODC 1994), p. 396. ACM Press (1994)
  27.Rajsbaum, S.: Iterated shared memory models. In: López-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 407–416. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-12200-2_​36 CrossRef
  28.Rajsbaum, S., Raynal, M.: An introductory tutorial to concurrency-related distributed recursion. Bull. Eur. Assoc. TCS 111, 57–75 (2013)MathSciNet
  29.Rajsbaum, S., Raynal, M., Travers, C.: The iterated restricted immediate snapshot model. In: Hu, X., Wang, J. (eds.) COCOON 2008. LNCS, vol. 5092, pp. 487–497. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-69733-6_​48 CrossRef
  30.Rajsbaum, S., Raynal, M., Travers, C.: An impossibility about failure detectors in the iterated immediate snapshot model. Inf. Process. Lett. 108(3), 160–164 (2008)MathSciNet CrossRef MATH
  31.Raynal, M.: Concurrent Programming: Algorithms, Principles and Foundations. Springer, Heidelberg (2013). 515 pages. ISBN 978-3-642-32026-2CrossRef MATH
  32.Raynal, M., Stainer, J.: Increasing the power of the iterated immediate snapshot model with failure detectors. In: Even, G., Halldórsson, M.M. (eds.) SIROCCO 2012. LNCS, vol. 7355, pp. 231–242. Springer, Heidelberg (2012). doi:10.​1007/​978-3-642-31104-8_​20 CrossRef
  33.Saks, M., Zaharoglou, F.: Wait-free \(k\) -set agreement is impossible: the topology of public knowledge. SIAM J. Comput. 29(5), 1449–1483 (2000)MathSciNet CrossRef MATH
  34.Taubenfeld, G.: Synchronization Algorithms and Concurrent Programming. Pearson Prentice-Hall, Upper Saddle River (2006). 423 pages. ISBN 0-131-97259-6
  
• 作者单位：Carole Delporte (14)
  Hugues Fauconnier (14)
  Sergio Rajsbaum (15)
  Michel Raynal (16)
  
  14. IRIF/GANG, Université Paris Diderot, Paris, France
  15. Instituto de Matemáticas, UNAM, 04510, México D.F., Mexico
  16. IUF, IRISA (Université de Rennes), Rennes, France
  
• 丛书名：Structural Information and Communication Complexity
• ISBN：978-3-319-48314-6
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9988

文摘

An immediate snapshot object is a high level communication object, built on top of a read/write distributed system in which all except one processes may crash. It allows each process to write a value and obtains a set of pairs (process id, value) such that, despite process crashes and asynchrony, the sets obtained by the processes satisfy noteworthy inclusion properties.