Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Xác thực, tính toán và phát hiện lỗi tự ổn định nhanh chóng và gọn nhẹ của cây khung tối thiểu (MST)
Tóm tắt
Bài báo này chứng minh tính hữu ích của việc xác thực chứng minh tại chỗ phân tán, như một công cụ cho việc thiết kế các thuật toán tự ổn định. Cụ thể, nó giới thiệu một khái niệm hơi tổng quát về chứng minh tại chỗ phân tán, và sử dụng nó để cải thiện đáng kể độ phức tạp về thời gian, trong khi vẫn duy trì tính tối ưu về không gian. Kết quả là, chúng tôi cho thấy việc tối ưu hóa kích thước bộ nhớ chỉ tốn một chi phí nhỏ về thời gian, trong bối cảnh cây khung tối thiểu (MST). Điều này có nghĩa là chúng tôi trình bày các thuật toán vừa hiệu quả về thời gian vừa không gian cho cả việc xây dựng một MST và việc xác thực nó. Điều này bao gồm một số phần có thể được coi là những đóng góp độc lập. Đầu tiên, chúng tôi tổng quát hóa khái niệm chứng minh tại chỗ, đánh đổi độ phức tạp về thời gian để cải thiện hiệu quả về bộ nhớ. Điều này thêm một chiều vào nghiên cứu các chứng minh tại chỗ phân tán, một lĩnh vực đang nhận được sự quan tâm gần đây. Cụ thể, chúng tôi thiết kế một cơ chế gán nhãn chứng minh (tự ổn định) mà là tối ưu về bộ nhớ (tức là, $$O(\log n)$$ bit mỗi nút), và độ phức tạp về thời gian là $$O(\log ^2 n)$$ trong các mạng đồng bộ, hoặc $$O(\varDelta \log ^3 n)$$ thời gian trong các mạng không đồng bộ, với $$\varDelta $$ là bậc tối đa của các nút. Điều này giải quyết một vấn đề mở mà Awerbuch et al. (1991) đã đặt ra. Chúng tôi cũng cho thấy rằng thời gian $$\varOmega (\log n)$$ là cần thiết, ngay cả trong các mạng đồng bộ. Một đặc điểm khác là nếu có $$f$$ lỗi xảy ra, thì trong thời gian phát hiện yêu cầu ở trên, chúng sẽ được phát hiện bởi một số nút trong khu vực $$O(f\log n)$$ của mỗi lỗi. Thứ hai, chúng tôi cho thấy cách cải thiện một bộ biến đổi đã biết giúp các thuật toán đầu vào/đầu ra tự ổn định. Nó hiện nay nhận vào một thuật toán xây dựng hiệu quả và một cơ chế gán nhãn chứng minh tự ổn định hiệu quả, và sản xuất một thuật toán tự ổn định hiệu quả. Khi được sử dụng cho MST, bộ biến đổi này tạo ra một thuật toán tự ổn định tối ưu về bộ nhớ, với độ phức tạp thời gian, tức là $$O(n)$$, tốt hơn đáng kể so với các thuật toán trước đó (độ phức tạp thời gian của các thuật toán MST trước đó mà sử dụng $$\varOmega (\log ^2 n)$$ bit bộ nhớ mỗi nút là $$O(n^2)$$, và thời gian cho các thuật toán tối ưu không gian là $$O(n|E|)$$). Kế thừa từ cơ chế gán nhãn chứng minh của chúng tôi, thuật toán xây dựng MST tự ổn định của chúng tôi cũng có hai thuộc tính sau: (1) nếu các lỗi xảy ra sau khi việc xây dựng kết thúc, thì chúng được phát hiện bởi một số nút trong $$O(\log ^2 n)$$ thời gian trong các mạng đồng bộ, hoặc trong $$O(\varDelta \log ^3 n)$$ thời gian trong các mạng không đồng bộ, và (2) nếu có $$f$$ lỗi xảy ra, thì trong thời gian phát hiện yêu cầu ở trên, chúng được phát hiện trong khu vực $$O(f\log n)$$ của mỗi lỗi. Chúng tôi cũng cho thấy cách cải thiện hai thuộc tính trên, với chi phí là một chút tăng trong bộ nhớ.
Từ khóa
#cây khung tối thiểu #thuật toán tự ổn định #chứng minh tại chỗ phân tánTài liệu tham khảo
Afek, Y., Bremler-Barr, A.: Self-stabilizing unidirectional network algorithms by power supply. Chic. J. Theor. Comput. Sci. (1998)
Afek, Y., Kutten, S., Yung, M.: Memory-efficient self stabilizing protocols for general networks. In: WDAG (renamed DISC), pp. 15–28 (1991)
Afek, Y., Kutten, S., Yung, M.: The local detection paradigm and its application to self-stabilization. Theor. Comput. Sci. 186(1–2), 199–229 (1997)
Aggarwal, S., Kutten, S.: Time optimal self-stabilizing spanning tree algorithms. In: FSTTCS, pp. 400–410 (1993)
Antonoiu, G., Srimani, P.: Distributed self-stabilizing algorithm for minimum spanning tree construction. Euro-Par 1300, 480–487 (1997)
Arora, A., Gouda, M.G.: Distributed reset. IEEE Trans. Comput. 43(9), 1026–1038 (1994)
Awerbuch, B.: A new distributed depth first search algorithm. Inf. Process. Lett. 20(3), 147–150 (1985)
Awerbuch, B.: Optimal distributed algorithms for minimum weight spanning tree, counting, leader election and related problems. In: STOC, pp. 230–240 (1987)
Awerbuch, B., Kutten, S., Mansour, Y., Patt-Shamir, B., Varghese, G.: Time optimal self-stabilizing synchronization. In: STOC, pp. 652–661 (1993)
Awerbuch, B., Kutten, S., Mansour, Y., Patt-Shamir, B., Varghese, G.: A time-optimal self-stabilizing synchronizer using a phase clock. IEEE Trans. Dependable Secure Comput. 4(3), 180–190 (2007)
Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by local checking and correction. In: FOCS, pp. 268–277 (1991)
Awerbuch, B., Patt-Shamir, B., Varghese, G., Dolev, S.: Self-stabilization by local checking and global reset. In: WDAG, pp. 326–339 (1994)
Awerbuch, B., Varghese, G.: Distributed program checking: a paradigm for building self-stabilizing distributed protocols. In: FOCS, pp. 258–267 (1991)
Azar, Y., Kutten, S., Patt-Shamir, B.: Distributed error confinement. ACM Trans. Algorithms 6(3), 48 (2010)
Blin, L., Dolev, S., Potop-Butucaru, M.G., Rovedakis, S.: Fast self-stabilizing minimum spanning tree construction. In: DISC, pp. 480–494 (2010)
Blin, L., Potop-Butucaru, M., Rovedakis, S., Tixeuil, S.: A new self-stabilizing minimum spanning tree construction with loop-free property. In: DISC, pp. 407–422 (2009)
Boulinier, C., Petit, F., Villain, V.: When graph theory helps self-stabilization. In: PODC, pp. 150–159 (2004)
Bui, A., Datta, A.K., Petit, F., Villain, V.: Snap-stabilization and PIF in tree networks. Distrib. Comput. 20(1), 3–19 (2007)
Chang, E.J.H.: Echo algorithms: depth parallel operations on general graphs. IEEE Trans. Softw. Eng. 8(4), 391–401 (1982)
Chlamtac, I., Kutten, S.: Tree-based broadcasting in multihop radio networks. IEEE Trans. Comput. 36(10), 1209–1223 (1987)
Collin, Z., Dolev, S.: Self-stabilizing depth-first search. Inf. Process. Lett. 49(6), 297–301 (1994)
Cournier, A., Petit, F., Villain, V., Datta, A.K.: Self-stabilizing PIF algorithm in arbitrary rooted networks. In: ICDCS, pp. 91–98 (2001)
Dalal, Y.K.: A distributed algorithm for constructing minimal spanning trees. IEEE Trans. Softw. Eng. 13(3), 398–405 (1987)
Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235–1265 (2012)
Datta, A.K., Larmore, L.L., Pinigantim, H.: Self-stabilizing leader election in dynamic networks. In: SSS, pp. 35–49 (2010)
Datta, A.K., Larmore, L.L., Vemula, P.: Self-stabilizing leader election in optimal space. In: SSS, pp. 109–123 (2008)
Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. CACM 17(11), 643–644 (1974)
Dixon, B., Rauch, M., Tarjan, R.E.: Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Comput. 21(6), 1184–1192 (1992)
Dixon, B., Tarjan, R.E.: Optimal parallel verification of minimum spanning trees in logarithmic time. Algorithmica 17(1), 11–18 (1997)
Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000)
Dolev, S., Gouda, M., Schneider, M.: Requirements for silent stabilization. Acta Inform. 36(6), 447–462 (1999)
Dolev, S., Israeli, A., Moran, S.: Self-stabilization of dynamic systems assuming only read/write atomicity. Distrib. Comput. 7(1), 3–16 (1994)
Even, S.: Graph Algorithms. Computer Science Press, Rockville (1979)
Fraigniaud, P., Gavoille, C.L.: Routing in trees. In: ICALP, pp. 757–772 (2001)
Fraigniaud, P., Korman, A., Peleg, D.: Local distributed decision. In: FOCS, pp. 708–717 (2011)
Fraigniaud, P., Korman, A., Parter, M., Peleg, D.: Randomized distributed decision. In: DISC, pp. 371–385 (2012)
Fraigniaud, P., Halldorsson, M.M., Korman, A.: On the impact of identifiers on local decision. In: OPODIS, pp. 224–238 (2012)
Gallager, R.G., Humblet, P.A., Spira, P.M.: A distributed algorithm for minimum-weight spanning trees. ACM Trans. Program. Lang. Syst. 5(1), 66–77 (1983)
Garay, J., Kutten, S., Peleg, D.: A sub-linear time distributed algorithm for minimum-weight spanning trees. In: FOCS, pp. 659–668 (1993)
Gavoille, C., Peleg, D., Pérennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53(1), 85–112 (2004)
Ghosh, S., Gupta, A., Herman, T., Pemmaraju, S.V.: Fault-containing self-stabilizing algorithms. In: PODC, pp. 45–54 (1996)
Goemans, M.X.: Minimum bounded degree spanning trees. In: FOCS, pp. 273–282 (2006)
Goldreich, O., Shrira, L.: Electing a leader in a ring with link failures. Acta Inform. 24(1), 79–91 (1987)
Göös, M., Suomela, J.: Locally checkable proofs. In: PODC, pp. 159–168 (2011)
Gupta, S.K.S., Srimani, P.K.: Self-stabilizing multicast protocols for ad hoc networks. J. Parallel Distrib. Comput. 63(1), 87–96 (2003)
Higham, L., Liang, Z.: Self-stabilizing minimum spanning tree construction on message passing networks. In: DISC, pp. 194–208 (2001)
Israeli, A., Jalfon, M.: Token management schemes and random walks yield self stabilizing mutual exclusion. In: PODC, pp. 119–132 (1990)
Jayaram, G.M., Varghese, G.: The fault span of crash failures. JACM 47(2), 244–293 (2000)
Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. Comput. 34, 23–40 (2004)
Katz, S., Perry, K.J.: Self-stabilizing extensions for message-passing systems. Distrib. Comput. 7(1), 17–26 (1993)
Kor, L., Korman, A., Peleg, D.: Tight bounds for distributed MST verification. In: STACS, pp. 69–80 (2011)
Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. Distrib. Comput. 20(4), 253–266 (2007)
Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib. Comput. 22(4), 215–233 (2010)
Korman, A., Peleg, D.: Compact separator decomposition for dynamic trees and applications. Distrib. Comput. 21(2), 141–161 (2008)
Kutten, S., Peleg, D.: Fast distributed construction of k-dominating sets and applications. In: PODC, pp. 238–249 (1995)
Lotker, Z., Patt-Shamir, B., Peleg, D.: Distributed MST for constant diameter graphs. Distrib. Comput. 18(6), 453–460 (2006)
McQuillan, J., Richer, I., Rosen, E.: The new routing algorithm for the ARPANET. IEEE Trans. Commun. 28(5), 711–719 (1980)
Naor, M., Stockmeyer, L.: What can be computed locally? In: STOC, pp. 184–193 (1993)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)
Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30(5), 1427–1442 (2000)
Segall, A.: Distributed network protocols. IEEE Trans. Inf. Theory 29(1), 23–34 (1983)
Stomp, F.A.: Structured design of self stabilizing programs. In: Proceedings IEEE 2nd Israeli Symposium on Theory of Computer Systems, pp. 167–176 (1993)
Tarjan, R.E.: Applications of path compression on balanced trees. JACM 26(4), 690–715 (1979)
Varghese, G.: Self-stabilization by local checking and correction. PhD dissertation, Laboratory for Computer Science, Massachusetts Institute of Technology (1992)