Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Tính đồng bộ từng phần dựa trên sự kịp thời của tập hợp
Tóm tắt
Chúng tôi giới thiệu một mô hình mới về tính đồng bộ từng phần cho các hệ thống bộ nhớ chia sẻ đọc-ghi. Mô hình này dựa trên khái niệm đơn giản về sự kịp thời của tập hợp—một tổng quát tự nhiên của khái niệm mang tính tiên phong về sự kịp thời trong mô hình đồng bộ từng phần của Dwork và cộng sự (J. ACM 35(2):288–323, 1988). Mặc dù tính đơn giản của nó, khái niệm sự kịp thời của tập hợp đủ mạnh để định nghĩa một họ các hệ thống đồng bộ từng phần có sự phù hợp gần gũi với từng trường hợp của vấn đề thỏa thuận k-t tập chạy n với độ t-resilient, được ký hiệu là thỏa thuận (t, k, n). Cụ thể, chúng tôi sử dụng nó để đưa ra một hệ thống đồng bộ từng phần đủ đồng bộ để giải quyết vấn đề thỏa thuận (t, k, n), nhưng không đủ để giải quyết hai vấn đề mạnh mẽ hơn một cách từng bước, cụ thể là thỏa thuận (t + 1, k, n)—có yêu cầu độ resiliance hơi mạnh hơn—và thỏa thuận (t, k − 1, n)—có yêu cầu thỏa thuận hơi mạnh hơn. Đây là hệ thống đồng bộ từng phần đầu tiên phân tách những vấn đề sub-consensus này. Các kết quả trên chỉ ra rằng sự kịp thời của tập hợp có thể được sử dụng để nghiên cứu và so sánh các yêu cầu đồng bộ từng phần của những vấn đề mà yếu hơn hẳn so với thỏa thuận.
Từ khóa
#tính đồng bộ từng phần #sự kịp thời của tập hợp #thỏa thuận #hệ thống bộ nhớ chia sẻ #độ t-resilient #quán hợp.Tài liệu tham khảo
Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: Communication-efficient leader election and consensus with limited link synchrony. In: ACM Symposium on Principles of Distributed Computing, pp. 328–337, July 2004
Aguilera M.K., Delporte-Gallet C., Fauconnier H., Toueg S.: On implementing Omega in systems with weak reliability and synchrony assumptions. Distrib. Comput. 21(4), 285–314 (2008)
Aguilera, M.K., Delporte-Gallet, C., Fauconnier, H., Toueg, S.: Partial synchrony based on set timeliness. In: ACM Symposium on Principles of Distributed Computing, pp. 102–110, August 2009
Aguilera M.K., Toueg S.: Adaptive progress: a gracefully-degrading liveness property. Distrib. Comput. 22(5–6), 303–334 (2010)
Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: ACM Symposium on Theory of Computing, pp. 91–100, May 1993
Borowsky, E., Gafni, E.: A simple algorithmically reasoned characterization of wait-free computation (extended abstract). In: ACM Symposium on Principles of Distributed Computing, pp. 189–198, August 1997
Borowsky E., Gafni E., Lynch N.A., Rajsbaum S.: The BG distributed simulation algorithm. Distrib. Comput. 14(3), 127–146 (2001)
Chandra T.D., Hadzilacos V., Toueg S.: The weakest failure detector for solving consensus. J. ACM 43(4), 685–722 (1996)
Chandra T.D., Toueg S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225–267 (1996)
Chaudhuri S.: More choices allow more faults: set consensus problems in totally asynchronous systems. Inf. Comput. 105(1), 132–158 (1993)
Cornejo, A., Rajsbaum, S., Raynal, M., Travers, C.: Brief announcement: failure detectors are schedulers. In: ACM Symposium on Principles of Distributed Computing, pp. 308–309, August 2007
Dwork C., Lynch N.A., Stockmeyer L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288–323 (1988)
Fernández A., Raynal M.: From an asynchronous intermittent rotating star to an eventual leader. IEEE Trans. Parallel Distrib. Syst. 21(9), 1290–1303 (2010)
Gafni E., Kuznetsov P.: On set consensus numbers. Distrib. Comput. 24(3–4), 149–163 (2011)
Herlihy M., Shavit N.: The topological structure of asynchronous computability. J. ACM 46(6), 858–923 (1999)
Hutle M., Malkhi D., Schmid U., Zhou L.: Chasing the weakest system model for implementing Ω and consensus. IEEE Trans. Dependable Secur. Comput. 6(4), 269–281 (2009)
Jiménez E., Arévalo S., Fernández A.: Implementing unreliable failure detectors with unknown membership. Inf. Process. Lett. 100(2), 60–63 (2006)
Malkhi, D., Oprea, F., Zhou, L.: Omega meets Paxos: leader election and stability without eventual timely links. In: International Conference on Distributed Computing. LNCS, vol. 3724, pp. 199–213. Springer, September 2005
Mostéfaoui, A., Raynal, M.: k-set agreement with limited accuracy failure detectors. In: ACM Symposium on Principles of Distributed Computing, pp. 143–152, July 2000
Mostefaoui A., Raynal M., Travers C.: Time-free and timer-based assumptions can be combined to obtain eventual leadership. IEEE Trans. Parallel Distrib. Syst. 17(7), 656–666 (2006)
Neiger, G.: Failure detectors and the wait-free hierarchy. In: ACM Symposium on Principles of Distributed Computing, pp. 100–109, August 1995
Pike, S.M., Sastry, S., Welch, J.L.: Failure detectors encapsulate fairness. In: International Conference on Principles of Distributed Systems. LNCS, vol. 6490, pp. 173–188. Springer, December 2010
Rajsbaum, S., Raynal, M., Travers, C.: Failure detectors as schedulers (an algorithmically-reasoned characterization). Technical Report 1838, IRISA, Université de Rennes, France, March 2007
Rajsbaum S., Raynal M., Travers C.: The iterated restricted immediate snapshot model. In: International Computing and Combinatorics Conference. LNCS, vol. 5092, pp. 487–497. Springer, June 2008
Saks M.E., Zaharoglou F.: Wait-free k-set agreement is impossible: the topology of public knowledge. SIAM J. Comput. 29(5), 1449–1483 (2000)
Zielinski P.: Anti-Ω: the weakest failure detector for set agreement. Distrib. Comput. 22(5–6), 335–348 (2010)