Song song hóa thuật toán Lamport trong loại trừ tương hỗ phân tán

  • Đặng Hùng Vĩ Trường Đại học Sư phạm, Đại học Đà Nẵng
  • Lê Văn Sơn Trường Đại học Sư phạm, Đại học Đà Nẵng
  • Nguyễn Xuân Huy Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam
Keywords: Hệ phân tán, đồng hồ lô-gic, thuật toán Lamport, loại trừ tương hỗ phân tán, truyền thông điệp

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.

Author Biographies

Đặng Hùng Vĩ, Trường Đại học Sư phạm, Đại học Đà Nẵng

Đặng Hùng Vĩ sinh năm 1980 tại Đà Nẵng. Tốt nghiệp đại học tại Trường Đại học Bách khoa, Đại học Đà Nẵng năm 2003 chuyên ngành Công nghệ Thông tin. Nhận bằng Thạc sỹ Khoa học Máy tính năm 2008 tại Đại học Đà Nẵng. Hiện đang là nghiên cứu sinh chuyên ngành Khoa học máy tính tại Đại học Đà Nẵng. Lĩnh vực nghiên cứu: Mạng máy tính, mã mạng, hệ phân tán, điện toán đám mây.

Lê Văn Sơn, Trường Đại học Sư phạm, Đại học Đà Nẵng

Lê Văn Sơn sinh năm 1948 tại Điện Bàn, Quảng Nam. Tốt nghiệp Đại học năm 1978, bảo vệ luận án Tiến sĩ năm 1997 tại Trường Đại học Tổng hợp Donesk, Ukraina. Công nhận Phó Giáo sư năm 2004. Hiện công tác tại Hội tin học Đà Nẵng. Lĩnh vực nghiên cứu: Hệ điều hành, mạng máy tính, hệ phân tán, tính toán đám mây.

Nguyễn Xuân Huy, Viện Công nghệ Thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam

Nguyễn Xuân Huy sinh năm 1944 tại Hải Phòng. Bảo vệ luận án Tiến sĩ năm 1978 chuyên ngành Toán-Tin tại Liên Xô. Bảo vệ Tiến sĩ Khoa học năm 1988 thuộc chuyên ngành Công nghệ Thông tin tại Liên Xô. Công nhận Phó Giáo sư năm 1992. Nguyên Chủ tịch Hội đồng Tư vấn Giáo dục Microsoft Việt Nam, Nghiên cứu viên cao cấp Viện Công nghệ thông tin, Viện Khoa học và Công nghệ Việt Nam. Lĩnh vực nghiên cứu: Công nghệ phần mềm, cơ sở dữ liệu.

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.

Published
2019-12-31
Section
Bài báo