tailieunhanh - Bài giảng Lập trình đồng thời và phân tán: Bài 8 - Lê Nguyễn Tuấn Thành

Bài giảng "Lập trình đồng thời và phân tán - Bài 8: Bài toán bầu cử" cung cấp cho người học các kiến thức: Bài toán bầu cử, thuật toán dựa trên vòng tròn (thuật toán Chang-Roberts, thuật toán Hirschberg-Sinclair). . | Bài giảng Lập trình đồng thời và phân tán: Bài 8 - Lê Nguyễn Tuấn Thành LẬP TRÌNH ĐỒNG BÀI 8: THỜI BÀI TOÁN BẦU CỬ & 1 PHÂN TÁN Giảng viên: Lê Nguyễn Tuấn Thành Email: thanhlnt@ NỘI DUNG ▪Bài toán bầu cử ▪Thuật toán dựa trên vòng tròn ▪Thuật toán Chang-Roberts ▪Thuật toán Hirschberg-Sinclair Bài giảng có sử dụng hình vẽ trong cuốn sách “Concurrent and Distributed Computing in Java, Vijay K. Garg, 2 University of Texas, John Wiley & Sons, 2005” Bài toán bầu cử ▪ Một bài toán quan trọng trong hệ thống phân tán là Bài toán bầu cử tiến trình lãnh đạo ▪ Tiến trình lãnh đạo có thể được sử dụng như người điều phối trong những thuật toán tập trung cho bài toán mutex 3 Giao diện Election ▪ Phương thức getLeader() trả về định danh của tiến trình được chọn là lãnh đạo ▪ Nếu định danh của tiến trình lãnh đạo chưa được biết, thì phương thức này sẽ khóa cho đến khi người lãnh đạo được chọn. 4 Bài toán bầu cử: Giải pháp (1) ▪ Bài toán bầu cử người lãnh đạo tương tự như bài toán loại trừ lẫn nhau ▪ Trong cả 2 bài toán, chúng ta đều quan tâm đến việc chọn ra một trong số các tiến trình, được gọi là tiến trình đặc quyền ▪ Các giải pháp dựa trên người điều phối cho bài toán mutex không thể áp dụng cho bài toán bầu cử người lãnh đạo ▪ Lý do: việc quyết định tiến trình nào đóng vai trò người điều phối hoặc giữ token là tương đương với bài toán bầu cử người lãnh đạo 5 Bài toán bầu cử: Giải pháp (2) ▪ Thuật toán mutex của Lamport có thể áp dụng cho bài toán bầu cử ▪ Tiến trình đầu tiên đi vào CS được xem là người lãnh đạo ▪ Tuy nhiên thuật toán này không tổng quát, do: ▪ Nền tảng giao tiếp mạng phía dưới phải kết nối hoàn toàn ▪ Các thông điệp phải truyền đi theo thứ tự FIFO ▪ Mỗi tiến trình phải giao tiếp với mọi tiến trình khác 6 Bài toán bầu cử: Giải pháp (3) Trong trường hợp các tiến trình trong hệ thống phân tán được sắp xếp theo hình tròn, tồn tại các thuật toán hiệu quả hơn của bài .