バークレーアルゴリズム

バークレーアルゴリズムは、分散コンピューティングにおけるクロック同期の方法であり、どのマシンも正確な時刻ソースを持たないことを前提としています。これは、1989年にカリフォルニア大学バークレー校のグセラとザッティによって開発されました。^{[ 1 ]}クリスティアンのアルゴリズムと同様に、イントラネット内での使用を想定しています。

クリスティアンのアルゴリズムとは異なり、バークレーのアルゴリズムでは、リーダーと呼ばれるサーバープロセスが、他のフォロワープロセスを定期的にポーリングします。一般的に、このアルゴリズムは次のようになります。

1. リーダーは、チャン・ロバーツアルゴリズムなどの選挙プロセスを通じて選出される。
2. リーダーはフォロワーにアンケートを取り、フォロワーはクリスティアンのアルゴリズムと同様の方法で自分の時間を返信する。
3. リーダーはメッセージの往復時間（RTT）を観察し、各フォロワーと自身の往復時間を推定する。
4. リーダーは、受信した時計の時間を平均化し、他のリーダーの値から大きく外れた値は無視します。
5. リーダーは、更新された現在時刻を他のプロセスに送り返す代わりに、各フォロワーがクロックを調整する必要がある量（正または負）を送信します。これにより、フォロワープロセスにおけるRTTによるさらなる不確実性を回避できます。

この方法では、平均値によって個々のクロックのずれが相殺されます。グセラ氏とザッティ氏は、彼らのプロトコルを用いてクロックを約20～25ミリ秒以内の精度で同期させた15台のコンピュータに関する結果を発表しました。

コンピュータシステムは通常、リーダーから負のクロック変更を受け取った際に、クロックを巻き戻すことを避けます。そうすると、単調時間の性質が損なわれてしまうためです。単調時間は、システム自体のアルゴリズムやmakeなどのプログラムにおける基本的な前提条件です。この問題に対する簡単な解決策は、リーダーが指定した期間、クロックを停止することですが、この単純な解決策も、それほど深刻ではないものの、問題を引き起こす可能性があります。軽微な修正の場合、ほとんどのシステムはクロックを遅くし、より長い期間にわたって修正を適用します。

多くの場合、クロックの値が許容範囲を超えるクライアントは、結果を平均化する際に除外されます。これにより、1つの誤ったクロックによってシステム全体の時刻が大幅に歪むことを防ぎます。