Dịch tự ổn định trong giao tiếp nhóm trên mạng có hướng

Acta Informatica - Tập 40 - Trang 609-636 - 2004
Shlomi Dolev1, Elad Schiller2
1Department of Computer Science, Ben-Gurion University of the Negev, Beer Sheva, Israel
2Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel

Tóm tắt

Bài báo này trình bày dịch vụ thành viên nhóm tự ổn định đầu tiên, dịch vụ multicast và dịch vụ phân bổ tài nguyên cho các mạng có hướng. Thuật toán giao tiếp nhóm đầu tiên dựa trên việc luân chuyển token qua một vòng ảo. Thuật toán thứ hai dựa trên việc xây dựng các cây bao trùm phân tán. Bên cạnh đó, một kỹ thuật được trình bày có khả năng giả lập, theo cách tự ổn định, bất kỳ mạng giao tiếp không có hướng nào trên các mạng có hướng được kết nối mạnh mẽ. Một thuật toán phân bổ tài nguyên không đồng bộ cho các mạng có hướng được kết nối mạnh mẽ cũng được trình bày.

Từ khóa

#tự ổn định #giao tiếp nhóm #mạng có hướng #phân bổ tài nguyên #thuật toán giao tiếp nhóm #cây bao trùm phân tán

Tài liệu tham khảo

Afek, Y., Bremler, A. (1998) Self-stabilizing unidirectional network algorithms by power-supply. Chicago Journal of Theoretical Computer Science 1998(3): 1- 48 Alstein, D., Hoepman, J.H., Olivier, B.E., van der Put, P.I.A. (1994) Self-stabilizing mutual exclusion on directed graphs. In: Computing Science in the Netherlands (Utrecht, 1994), Stichting Mathematisch Centrum, Amsterdam, pp. 42-53 Awerbuch, B. (1985) Complexity of network synchronization. JACM 32(4): 804-823 Brukman, O., Dolev, S., Kolodner, H. (2003) Self-stabilizing autonomic recoverer for eventual byzantine software. IEEE International Conference on Software-Science, Technology & Engineering, (SwSTE03). Herzelia, pp. 20-29. Also in: Workshop on Adaptive Distributed Systems (WADiS03), Sorrento, Italy Bang-Jensen, J., Gutin, G. (2000) Digraphs: theory, algorithms and applications. Springer Monographs in Mathematics, Springer, London Beauquier, J., Gradinariu, M., Johnen, C., Durand-Lose, J. (2002) Token based self-stabilizing uniform algorithms. Journal of Parallel and Distributed Computing (JPDC) 62(5): 899-921 Beauquier, J., Kutten, S., Tixeuil, S. (1999) Self-stabilization in Eulerian networks with cut-through constraints. Technical Report 1200, Laboratoire de Recherche en Informatique, January Cobb, J.A., Gouda, M.G. (2001) Stabilization of routing in directed networks. Proc. 5th Workshop on Self-Stabilization Systems, LNCS 2194, pp. 51-66 Cristian, F., Schmuck, F. (1995) Agreeing on processor group membership in asynchronous distributed systems. Technical Report CSE95-428, Department of Computer Science, University of California San Diego Choy, M., Singh, A.K. (1995) Efficient fault tolerant algorithms for distributed resource allocation. ACM Transactions on Programming Languages and Systems 17(4): 535-559 Dijkstra, E.W. (1971) Hierarchical ordering of sequential processes. Acta Informatica 1: 115-138 Dijkstra, E.W. (1974) Self-stabilizing systems in spite of distributed control. Communication of the ACM 17: 643-644 Dolev, S. (1997) Self-stabilizing routing and related protocols. Journal of Parallel and Distributed Computing 42: 122-127 Dolev, S. (2000) Self-stabilization. MIT Press, Cambridge, MA Dolev, S., Herman, T. (1997) Superstabilizing protocols for dynamic distributed systems. Chicago Journal of Theoretical Computer Science 1997(4): 1-40 Dolev, S., Haviv, Y. (2003) Self-stabilizing soft error resilient microprocessor. Supplemental Volume of the 2003 International Conference on Dependable Systems and Networks, IEEE Computer Society, (DSN 2003), pp. B-18, B-19. Also presented at: IBM’s Compiler and Architecture Seminar, IBM Haifa Labs, November 2002 Dolev, S., Kat, R., (2002) Self-stabilizing distributed file systems. International Workshop on Self-Repairing and Self-Configurable Distributed Systems, (RCDS 2002), pp. 384-389. Also presented at: IBM’s Storage Systems Technology Workshop, IBM Haifa Labs, November 2002 S. Dolev, Israeli, A., Moran, S. (1997) Uniform dynamic self-stabilizing leader election. IEEE Transactions on Parallel and Distributed Systems, Vol. 8, No. 4, pp. 424-440 Dolev, S., Schiller, E. (2001) Communication adaptive self-stabilizing group membership service. 5th Workshop on Self-Stabilizing Systems, LNCS 2194, pp. 82-97, October. Also in: Technical Report #00-02 Department of Computer Science Ben-Gurion University, Beer-Sheva, Israel, 2000 Dolev, S., Schiller, E. (2003) Self-stabilizing group communication in directed networks. Technical Report #10-03 Department of Computer Science Ben-Gurion University, Beer-Sheva, Israel Dolev, S., Schiller, E., Welch, J.L. (2002) Random walk for self-stabilizing group communication in ad-hoc networks. 21st Symposium on Reliable Distributed Systems, IEEE Computer Society Press, pp. 70-79 Delaet, S., Tixeuil, S. (2002) Tolerating transient and intermittent failures. Journal of Parallel and Distributed Computing 62(5): 961-981 Dolev, S., Welch, J.L. (1997) Crash resilient communication in dynamic networks. IEEE Transactions on Computers, 46(1): 12-26 Dolev, S., Yagel, R. (2003) Toward self-stabilizing operating systems. IEEE International Conference on Software-Science, Technology & Engineering, Industrial Track, Doctoral Symposium, Posters, (SwSTE03), Herzelia, November Fox, A., Patterson, D. (2003) Self-repairing computers. Scientific American, May 12 IBM (2001) Autonomic computing. http://www.research.ibm.com/autonomic Kaiser, G., Parekh, J., Gross, P., Valetto, G. (2003) Kinesthetics eXtreme: An external infrastructure for monitoring distributed legacy systems. In: 5th Annual International Active Middleware Workshop, June, pp. 22-30 Lynch, N.A. (1980) Fast allocation of nearby resources in a distributed system. Proc. 12th ACM Symposium on Theory of Computing, pp. 70-81 Patterson, D., Brown, A., Broadwell, P., Candea, G., Chen, M., Cutler, J., Enriquez, P., Fox, A., Kiciman, E., Merzbacher, M., Oppenheimer, D., Sastry, N., Tetzlaff, W., Traupman, J., Treuhaft, N. (2002) Recovery Oriented Computing(ROC): Motivation, definition, techniques and case studies. UC Berkeley Computer Science Technical Report UCB/CSD-02-1175, Berkeley, CA, March Sussman, J., Marzullo, K. (1998) The bancomat problem: An example of resource allocation in a partitionable asynchronous system. Theoretical Computer Science 291(1): 103-131 Tanenbaum, A.S. (1996) Computer networks, 3rd edn. Prentice Hall Tchunte, M. (1981) Sur l’auto-stabilisation dans un reseau d’ordinateurs. RAIRO Informatique Theoretique 15: 47-66