Berkeley’s Algorithm 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 trường hợp một số hoặc tất cả các hệ thống của mạng phân tán có một trong những 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 phân tách 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 chủ / nút lãnh đạo. Điều này được thực hiện từ các nút nhóm trong máy chủ.
Thuật toán là -
-
Quá trình bầu cử chọn nút chính trong máy chủ.
-
Sau đó, người lãnh đạo sẽ thăm dò những người theo dõi cung cấp thời gian của họ theo cách tương tự như Thuật toán của Cristian , việc này được thực hiện định kỳ.
-
Sau đó, nhóm dẫn đầu sẽ 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ầu, là thời gian trung bình được cung cấp cho nút lãnh đạo.
Hãy tổng hợp các bước tiếp theo để đồ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 (master node) N2 -> 13: 46 N3 -> 14: 15
Bước 1 - Người đứng đầu được bầu chọn, nút N1 là nút chính trong hệ thống.
Bước 2 - người lãnh đạo 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 - Người lãnh đạo tính trung bình thời gian và gửi lại thời gian hiệu chỉnh cho 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 cách sử dụng thuật toán của Berkeley.