時刻同期アルゴリズムは広く使用されています。
たとえば、Unix システムでは、Make コマンドは、新しく変更されたコード ファイルをコンパイルするためにのみ使用されます。 Make コマンドは、実行中のクライアントのクロックを使用して、どのファイルが変更されたかを判断します。ただし、コードがファイル サーバー上に配置され、make コマンドを実行するホストの時刻とファイル サーバーの時刻が異なる場合、make コマンドが正しく動作しない可能性があります。
たとえば、Dota をプレイする場合、全員の画像の一貫性を保つために、複数のクライアントが同期された時計を必要とします。 , たとえば、PC コンピュータの同期サーバー時間は、非常に高い同期精度を実現できます。
時刻同期アルゴリズム
時刻同期アルゴリズムには次の解決策があります。
クリスチャンのアルゴリズム
Cristian のアルゴリズム アルゴリズムのアプリケーション バックグラウンドは、主に、プロセス P がサーバー S に似た時間を要求する場合です。
1. P は S に要求パケットを送信して時刻を要求します。
2. S は P の要求パケットを受信した後、現在の S 時刻をパケットに追加して送り返します。
3. P がデータ パケットを受信した後、現在時刻を T+RTT/2 に設定します。
RTT はラウンドトリップタイムを表し、P がデータパケットを送信してから受信するまでの時間です。このアルゴリズムでは、ネットワーク上でパケットの送信と受信に同じ時間がかかると想定しています。また、リクエストを処理する際の S の時間は無視できるものと想定されます。上記の仮定に基づいて、アルゴリズムは次のように改善できます。
P から S に複数の要求パケットを送信し、RTT を 2 で割った値として最小の RTT を取得し、それをこのパケットに含まれる時間に加算します。
アルゴリズムの精度分析: min は S から P までの最短時間、T は上で定義した RTT に含まれる時間であると仮定します。したがって、P 設定時間の範囲は [T+min, T+RTT-min] となります。このようにして、時間偏差の範囲は RTT-2min 以内になります。改良されたアルゴリズムの精度は RTT/2 分である必要があります。
アルゴリズム バークレー アルゴリズム
BerkeleyアルゴリズムはCristianアルゴリズムとは利用環境が異なります。 Cristian アルゴリズムは、クライアントがサーバーに正しい時刻を要求するときに使用されます。 Berkeley アルゴリズムは、複数のクライアント間でクロックを同期するためのアルゴリズムです。具体的なアルゴリズムは次のとおりです。
1. まず、変更とロバートのアルゴリズムを通じてリングからマスターとしてノードを選択します。
2. マスターは、Cristian アルゴリズムを使用して各ノードの時刻を要求します。
3. マスターは、平均 RTT を記録し、大きな偏差のある RTT を除外することによって、各ノードの時間偏差を評価します。
4. マスターは各ノードの時間偏差を各ノードに送信し、ノードが自ら修正できるようにします。
一般的に、クライアントは時刻を受信した後、現在の時刻を調整し直すことはありません。これにより、プログラムに不可解なエラーが発生するためです。なぜなら、多くのアルゴリズムでは、時間が調整されて戻らないことが基本的な前提となっているからです。たとえば、make コマンドです。
解決策はあります。時計の動作を遅くするだけです。時間をかけて正しい時刻に調整してください。
さらに、アルゴリズムの変更とロバートのアルゴリズムについても議論する必要があります。このアルゴリズムは時刻同期アルゴリズムと同じであり、Dota をプレイするときに必要になります。 dota を初期化するときは、各プレーヤーの時計を同期する必要があります。オフラインになった後は、特定のアルゴリズムを使用して新しいホストを見つける必要があります。
変化とロバートのアルゴリズム
Change および Robert のアルゴリズム アルゴリズムは、各プロセスが UID を持ち、リング状のネットワーク内に方向性のない通信チャネルが存在する可能性があることを前提としています。アルゴリズムは次のとおりです。
1. まず、リング内の各ノードは自身を非参加者として識別します。
2. プロセスはホストがオフラインであることを検出すると、まず自身を参加者として識別し、次に自身の UID を含むホストが選択したパケットをネイバーに送信します。
3. データ パケットがネイバーに到達すると、まずそれを自身の UID と比較し、自身の UID がこの UID より大きい場合、自身を参加者として識別し、データ パケット内の UID を変更し、これをデータ パケットで送信します。時計回りのデータ。
4. プロセスがデータ パケットを受信し、データ パケット内の UID が自身の UID と同じであることを検出すると、アルゴリズムの第 2 フェーズが開始されます。
5. このプロセスは、自身を非参加者として識別し、UID 情報を含む、選択されたホストに関する情報を近隣ホストに送信します。
6. このサイクルは、プロセスがホストとして選択されたプロセスに戻るまで続き、プロセス全体が終了します。
これは、分散システムでホストを選択するためのアルゴリズムです。もちろん、特定の状況下では、ネットワーク速度が最も速いものや CPU が最も速いものをホストとして選択するなど、選択条件を変更できます。同時に、このアルゴリズムは、複数のプロセスが同時にホストがオフラインであることを検出し、複数のプロセスが同時にホストをシークする状況も回避できます。
このアルゴリズムの擬似コードは次のように記述できます。
開始 : M:= i:
<i> を隣人に送信します。
メッセージ <j> を受信すると、
M<j の場合、M:=j。
<j> を近隣に送信します。
エルセイフ M=j の場合はリーダー。
エンディフ;
このアルゴリズムの複雑さの分析、数学的モデル、統計表の詳細については、次の文書を参照してください。
http://www.vs.inf.ethz.ch/publ/papers/MsgCplxElecAlgo.pdf
この記事では、集中システムのいくつかの時刻同期アルゴリズムのみを分析し、分散システムのネットワーク タイム プロトコルおよびリファレンス ブロードキャスト同期アルゴリズムについては分析しません。今後時間があるときにNTPについて勉強してみます。