メッセージ順序付けとマルチキャスト

グループ通信は、FIFOから因果的順序、そして全順序に至るまで、指定された信頼性と順序付けの保証をもって、一連のプロセスにメッセージを配信します。

Definition

マルチキャストは、単一のメッセージをプロセスグループの全メンバーに配信します。順序付けの保証は、メッセージの相対的な配信順序を制約するものであり、FIFOは送信者ごとの順序を保持し、因果的順序は「happened-before」順序を保持し、全順序はすべてのメンバーで同じシーケンスで全てのメッセージを配信します。

Scope

このトピックでは、信頼性の高いマルチキャストと、配信順序の階層（FIFO、因果的、全順序（アトミック））について扱います。これらを実現するためのシーケンス番号、論理クロック、シーケンサーまたはトークン方式を用いた実装、そして順序付けられたマルチキャストと一貫性のあるグループメンバーシップ変更を統合する仮想同期モデルについても説明します。全順序（アトミック）ブロードキャストは、合意形成と同等の能力を持つことが示されています。

Core questions

• アプリケーションはグループ通信にどのような信頼性と順序付けの保証を要求しますか？
• 因果的および全順序の配信はどのように効率的に実装されますか？
• 全順序ブロードキャストが合意形成と同等であるのはなぜですか？

Key theories

順序付けの階層

配信順序は階層を形成します。FIFOは因果的順序よりも弱く、因果的順序は全順序よりも弱い関係にあります。それぞれ、送信者ごとのシーケンス番号、ベクトルタイムスタンプ、またはグローバルに合意されたシーケンスなどの追加のメタデータによって強制されます。

仮想同期

仮想同期は、グループメンバーシップの変更とマルチキャストメッセージをすべてのメンバーに一貫した順序で提示します。これにより、プロセスは同じイベントシーケンスとビュー変更を認識し、レプリケートされたサービスの構築を簡素化します。

アトミックブロードキャストと合意形成の等価性

全順序（アトミック）ブロードキャストと合意形成は相互に還元可能であり、一方の解決策は他方の解決策をもたらします。また、両者は非同期性と障害下での同じ可解性限界を共有します。

Clinical relevance

順序付けられた信頼性の高いマルチキャストは、ステートマシンレプリケーション、パブリッシュ/サブスクライブシステム、およびレプリケートされたデータベースの基盤となります。これらのシステムでは、すべての一貫性を保つために、すべてのレプリカが同じ更新を同じ順序で適用する必要があります。

History

BirmanとJosephは、1980年代にISISシステムを通じて仮想同期と順序付けられたマルチキャストを導入しました。アトミックブロードキャストと合意形成の関係は1990年代に明確化され、Defago、Schiper、およびUrbanによる2004年の調査では、多くの全順序アルゴリズムが体系化されました。

Key figures

• Kenneth Birman
• Thomas Joseph
• Andre Schiper
• Leslie Lamport

Seminal works

• birman1987
• defago2004
• lamport1978

Frequently asked questions

因果的順序付けと全順序付けの違いは何ですか？

因果的順序付けは、因果関係のあるメッセージのみを制約し、並行するメッセージは異なるプロセスで異なる順序で配信されることを許容します。全順序付けは、すべてのプロセスがすべてのメッセージを同一のシーケンスで配信することを要求し、これは厳密に強力であり、合意形成と同程度の困難さがあります。