Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Tự điều chỉnh thích ứng với ngẫu nhiên
Tóm tắt
Chúng tôi trình bày một sơ đồ để chuyển đổi các thuật toán tự ổn định sử dụng ngẫu nhiên trong và sau quá trình hội tụ sang các thuật toán tự ổn định chỉ sử dụng ngẫu nhiên trong quá trình hội tụ. Do đó, chúng tôi giảm số lượng bit ngẫu nhiên từ vô hạn xuống một số giới hạn kỳ vọng. Sơ đồ này áp dụng cho các trường hợp mà tồn tại một tiền đề cục bộ cho mỗi nút, sao cho tính nhất quán toàn cục được ngụ ý bởi sự hợp nhất của các tiền đề cục bộ. Chúng tôi minh họa sơ đồ của mình qua thuật toán tuần hoàn thẻ của Herman (Infor Process Lett 35:63–67, 1990) và thuật toán đồng bộ hóa đồng hồ tự ổn định Byzantine thời gian không đổi gần đây của Ben-Or, Dolev và Hoch (Kỷ yếu của hội thảo thường niên ACM SIGACT-SIGOPS lần thứ 27 về nguyên tắc tính toán phân tán (PODC), 2008). Việc ứng dụng sơ đồ của chúng tôi dẫn đến thuật toán đồng bộ hóa đồng hồ tự ổn định Byzantine thời gian không đổi đầu tiên mà cuối cùng không sử dụng các bit ngẫu nhiên.
Từ khóa
#tính tự ổn định #thuật toán ngẫu nhiên #đồng bộ hóa đồng hồ #tính nhất quán toàn cục #lý thuyết phân tánTài liệu tham khảo
Afek Y., Brown G.M.: Self-stabilization over unreliable communication media. Distrib. Comput. 7(1), 27–34 (1993)
Afek Y., Dolev S.: Local stabilizer. J. Parallel Distrib. Comput. 62(5), 745–765 (2002)
Anagnostou, E., El-Yaniv, R., Hadzilacos, V.: Memory adaptive self-stabilizing protocols (extended abstract). In: Proceedings of the 6th International Workshop on Distributed Algorithms (WDAG 1992), pp. 203–220 (1992)
Ben-Or, M., Dolev, D., Hoch, E.N.: Fast self-stabilizing byzantine tolerant digital clock synchronization. In: Proceedings of the 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, (PODC) (2008)
Chandy K.M., Misra J.: The drinking philosophers problem. ACM Trans. Programming Languages Syst. 6(4), 632–646 (1984)
Dolev S.: Self-Stabilization. MIT Press, Cambridge, MA (2000)
Dolev S., Israeli A., Moran S.: Resource bounds for self-stabilizing message-driven protocols. SIAM J. Comput. 26(1), 273–290 (1997)
Dolev S., Schiller E.: Communication adaptive self-stabilizing group membership service. IEEE Trans. Parallel Distrib. Syst. 14(7), 709–720 (2003)
Dolev, S., Welch, J.: Self-stabilizing clock synchronization in the presence of byzantine faults. In: Proceedings of the 2nd Workshop on Self-Stabilizing Systems, UNLV, May 1995. [Also in Journal of the ACM 51(5), 780–799 Sep (2004)]
Herman T.: Probabilistic self-stabilization. Infor. Process. Lett. 35, 63–67 (1990)
Katz S., Perry K.J.: Self-stabilizing extensions for message-passing systems. Distrib Comput 7(1), 17–26 (1993)
Michael, R.O., Lehmann, D.: The advantages of free choice: a symmetric and fully distributed solution for the dining philosophers problem. In: A Classical Mind: Essays in Honor of C. A. R. Hoare, Prentice-Hall International Series In Computer Science, pp. 333–352 (1994)
Rao J.R.: Eventual determinism: using probabilistic means to achieve deterministic ends. Int. J. Parallel, Emergent Distrib. Syst. 8(1), 3–19 (1996)