LẬP
TRÌNH
ĐỒNG
THỜI
&
PHÂN
TÁN
BÀI 8:
BÀI TOÁN BẦU CỬ
Giảng viên: Lê Nguyễn Tuấn Thành
Email: thanhlnt@tlu.edu.vn
1
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
2
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,
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