Thuật toán Berkeley là một thuật toán được sử dụng để đồng bộ hóa đồng hồ trong các hệ thống phân tán. Thuật toán này được sử dụng trong các trường hợp khi một số hoặc tất cả các hệ thống của mạng phân tán gặp phải một trong các vấn đề sau:
A. Máy không có nguồn thời gian chính xác.
B. Mạng hoặc máy không có máy chủ UTC.
Hệ thống phân tán chứa nhiều nút được tách biệt về mặt vật lý nhưng được liên kết với nhau bằng mạng.
Thuật toán Berkeley
Trong thuật toán này, hệ thống chọn một nút làm nút master/leader. Việc này được thực hiện từ tập hợp các nút trong máy chủ.
Thuật toán như sau:
Một quá trình bầu cử chọn nút master trong máy chủ.
Nút leader sau đó thăm dò các nút follower cung cấp thời gian của chúng theo cách tương tự như Thuật toán Cristian, việc này được thực hiện định kỳ.
Nút leader sau đó tính toán thời gian tương đối mà các nút khác phải thay đổi hoặc điều chỉnh để đồng bộ hóa với thời gian đồng hồ toàn cục là trung bình của các thời gian được cung cấp cho nút leader.
Hãy tóm tắt các bước được thực hiện để đồng bộ hóa đồng hồ bằng thuật toán Berkeley,
Các nút trong hệ thống phân tán với thời gian đồng hồ của chúng:
N1 -> 14:00 (nút master) N2 -> 13: 46 N3 -> 14: 15
Bước 1 - Leader được bầu cử, nút N1 là master trong hệ thống.
Bước 2 - Leader yêu cầu thời gian từ tất cả các nút.
N1 -> time : 14:00 N2 -> time : 13:46 N3 -> time : 14:20
Bước 3 - Leader lấy trung bình các thời gian và gửi thời gian hiệu chỉnh trở lại các nút.
N1 -> Corrected Time 14:02 (+2) N2 -> Corrected Time 14:02 (+16) N3 -> Corrected Time 14:02 (-18)
Điều này cho thấy cách đồng bộ hóa các nút của hệ thống phân tán được thực hiện bằng thuật toán Berkeley.