Song song hóa thuật toán Lamport trong loại trừ tương hỗ phân tán
Abstract
Hệ phân tán là hệ thống cung cấp tài nguyên dùng chung với quy mô lớn. Hệ phân tán sử dụng cơ chế truyền thông điệp để hợp lực trong môi trường truyền thông. Trong hợp lực, nhiều tiến trình cùng tương tranh tài nguyên dùng chung dễ dẫn đến bế tắc trong cung cấp tài nguyên. Loại trừ tương hỗ phân tán cho phép chỉ có một tiến trình duy nhất được thực thi trong miền găng tại một thời điểm đối với một tài nguyên để giải quyết bế tắc. Để đạt được loại trừ tương hỗ phân tán, các tiến trình phải được gắn dấu đồng hồ lô-gic để xác lập trật tự và loại trừ các tiến trình gây ra bế tắc. Bài báo trình bày giải pháp song song hóa thuật toán Lamport trong loại trừ tương hỗ phân tán. Kết quả giải pháp là xác lập giá trị đồng hồ lô-gic dựa trên song song hóa thuật toán Lamport và xác định các tiến trình thực thi trong đảm bảo tính nhất quán và gắn bó trong hệ phân tán.
References
R. Buyya, “Market-oriented cloud computing: Vision, hype, and reality of delivering computing as the 5th utility,” in 2009 Fourth ChinaGrid Annual Conf., 2009, pp. xii–xv.
G. F. Coulouris and J. Dollimore, Distributed systems: Concepts and design, 4th ed. Addison-Wesley, 2005. [3] M. Raynal, Distributed Algorithms for Message-Passing Systems. Springer, 2013.
A. D. Kshemkalyani and M. Singhal, Distributed Computing: Principles, Algorithms, and Systems. Cambridge University Press, 2008.
M. Raynal, A. Schiper, and S. Toueg, “The causal ordering abstraction and a simple way to implement it,” Information Processing Letters, vol. 39, no. 6, pp. 343–350, 1991.
N. Sharma and A. Parikh, “Deadlock detection and removal in distributed systems,” International Jour. Engineering and Computer Science, vol. 2, no. 10, pp. 2900–2902, Oct. 2013.
H. H. C. Nguyen, H. V. Dang, N. M. N. Pham, V. S. Le, and T. T. Nguyen, “Deadlock detection for resource allocation in heterogeneous distributed platforms,” in Recent Advances in Information and Communication Technology 2015. Springer, 2015, pp. 285–295.
H. H. C. Nguyen, V. S. Le, and T. T. Nguyen, “Algorithmic approach to deadlock detection for resource allocation in heterogeneous platforms,” in International Conference on Smart Computing, 2014, pp. 97–103.
H. H. C. Nguyen, H. D. Tran, V. T. Doan, and V. T. P. Anh, “Deadlock avoidance for resource allocation model V VMout-of-N PM,” in Context-Aware Systems and Applications. Springer, 2017, pp. 172–182.
M. Singhal, “Deadlock detection in distributed systems,” Computer, vol. 22, no. 11, pp. 37–48, 1989.
K. Erciyes and V. Adve, Distributed Graph Algorithms for Computer Networks. Springer, 2013.
G. Ricart and A. K. Agrawala, “Author’s response to ‘On mutual exclusion in computer networks’ by Carvalho and Roucairol,” Commun. of the ACM, pp. 147–148, 1983.
I. Suzuki and T. Kasami, “A distributed mutual exclusion algorithm,” ACM Transactions on Computer Systems, vol. 3, no. 4, pp. 344–349, Nov. 1985.
M. Mizuno, M. L. Neilsen, and R. Rao, “A token based distributed mutual exclusion algorithm based on quorum agreements,” in 11th International Conference on Distributed Computing Systems, 1991, pp. 361–368.
J.-M. Helary, N. Plouzeau, and M. Raynal, “A distributed algorithm for mutual exclusion in an arbitrary network,” The Computer Journal, vol. 31, no. 4, pp. 289–295, 1988.
K. Raymond, “A tree-based algorithm for distributed mutual exclusion,” ACM Transactions on Computer Systems, vol. 7, no. 1, pp. 61–77, 1989.
M. Singhal, “A heuristically-aided algorithm for mutual exclusion in distributed systems,” IEEE Transactions on Computers, vol. 38, no. 5, pp. 651–662, 1989.
N. Mohamed and T. Michel, “How to detect a failure and regenerate the token in the Log(n) distributed algorithm for mutual exclusion,” in Distributed Algorithms. Springer Berlin Heidelberg, 1988, pp. 155–166.
S.MishraandP.K.Srimani,“Fault-tolerantmutualexclusion algorithms,” Journal of Systems and Software, vol. 11, no. 2, pp. 111–129, 1990.
S. Nishio, K. F. Li, and E. G. Manning, “A resilient mutual exclusion algorithm for computer networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 1, no. 3, pp. 344–356, 1990.
L. Lamport, “Time, clocks, and the ordering of events in a distributed system,” Communications of the ACM, vol. 21, no. 7, pp. 558–565, 1978.
G. Ricart and A. K. Agrawala, “An optimal algorithm for mutual exclusion in computer networks,” Communications of the ACM, vol. 24, no. 1, pp. 9–17, 1981.
O. Carvalho and G. Roucairol, “On mutual exclusion in computer networks,” Communications of the ACM, vol. 26, no. 2, pp. 146–147, Feb. 1983.
M. Raynal, “Prime numbers as a tool to design distributed algorithms,” Information Processing Letters, vol. 33, no. 1, pp. 53–58, 1989.
M. Maekawa, “A Sqrt(N) algorithm for mutual exclusion in decentralized systems,” ACM Transactions on Computer Systems, vol. 3, no. 2, pp. 145–159, 1985.
B. A. Sanders, “The information structure of distributed mutual exclusion algorithms,” ACM Transactions on Computer Systems, vol. 5, no. 3, pp. 284–299, 1987.
D. Agrawal and A. E. Abbadi,“An efficient and fault-tolerant solution for distributed mutual exclusion,” ACM Transactions on Computer Systems, vol. 9, no. 1, pp. 1–20, 1991.
M. Singhal, “A dynamic information-structure mutual exclusion algorithm for distributed systems,” in 9th International Conference on Distributed Computing Systems, 1989, pp. 70–78.
M. G. Velazquez, “A survey of distributed mutual exclusion algorithms,” Colorado State University, Tech. Rep., 1993.
N. Yadav, S. Yadav, and S. Mandiratta, “A review of various mutual exclusion algorithms in distributed environment,” International Journal of Computer Applications, vol. 129, no. 14, pp. 11–16, 2015.
S. Naseera, “A distributed ring algorithm for coordinator election in distributed systems,” ICTACT Journal on Communication Technology, vol. 7, no. 3, pp. 1341–1344, 2016.
L. V. Sơn, Hệ tin học phân tán. Nhà xuất bản Đại học Quốc gia Tp. Hồ Chí Minh, 2002.
D. H. Vĩ and L. V. Sơn, “Cung cấp tài nguyên truyền thông cho hệ phân tán trong máy ảo,” Journal of Science and Technology, The University of Danang, vol. 11, no. 108, pp. 90–94, 2016.