อัลกอริทึมของเบอร์เกลีย์ (Berkeley's Algorithm) เป็นอัลกอริทึมที่ใช้สำหรับซิงโครไนซ์นาฬิกา (clock synchronization) ในระบบกระจาย (distributed systems) อัลกอริทึมนี้ใช้ในกรณีที่ระบบบางส่วนหรือทั้งหมดในเครือข่ายกระจายมีปัญหาดังนี้:
A. เครื่องไม่มีแหล่งเวลาที่แม่นยำ
B. เครือข่ายหรือเครื่องไม่มีเซิร์ฟเวอร์ UTC
ระบบกระจาย (Distributed system) ประกอบด้วยโหนดหลายตัวที่แยกทางกายภาพแต่เชื่อมต่อกันผ่านเครือข่าย
อัลกอริทึมของเบอร์เกลีย์
ในอัลกอริทึมนี้ ระบบจะเลือกโหนดหนึ่งเป็น master/leader node จาก pool ของโหนดในเซิร์ฟเวอร์
ขั้นตอนของอัลกอริทึม:
กระบวนการเลือกตั้ง (election process) เลือก master node ในเซิร์ฟเวอร์
Leader จะ polling ตัวติดตาม (followers) ที่ให้เวลาของพวกเขาในลักษณะคล้าย อัลกอริทึมของคริสเตียน (Cristian's Algorithm) ทำเป็นระยะ
Leader จะคำนวณเวลาสัมพัทธ์ที่โหนดอื่นๆ ต้องปรับเพื่อซิงโครไนซ์กับเวลานาฬิกาสากล (global clock time) ซึ่งเป็นค่าเฉลี่ยของเวลาที่ส่งให้ leader node
มาสรุปขั้นตอนการซิงโครไนซ์นาฬิกาโดยใช้ Berkeley's Algorithm:
โหนดในระบบกระจายพร้อมเวลานาฬิกาของพวกเขา:
N1 -> 14:00 (master node) N2 -> 13:46 N3 -> 14:15
ขั้นตอนที่ 1 - เลือก Leader, โหนด N1 เป็น master ในระบบ
ขั้นตอนที่ 2 - Leader ขอเวลาจากทุกโหนด
N1 -> time: 14:00 N2 -> time: 13:46 N3 -> time: 14:20
ขั้นตอนที่ 3 - Leader คำนวณค่าเฉลี่ยเวลา และส่งเวลาปรับกลับไปยังโหนดต่างๆ
N1 -> Corrected Time 14:02 (+2) N2 -> Corrected Time 14:02 (+16) N3 -> Corrected Time 14:02 (-18)
นี่แสดงให้เห็นว่าการซิงโครไนซ์โหนดของระบบกระจายทำได้อย่างไรโดยใช้ Berkeley's Algorithm
