分散システムの語彙
Database Internals, Chapter 8, p.182 "Distributed Systems Abstractions" のまとめ。
Fair-loss Link
2つのprocessを繋ぐのがLink。こいつはいくつかの基本的な事項を満たしていてほしい。すべて満たしていればFair-loss linkと呼ばれる。
Fair loss: SenderとRecipientが正常かつSenderが無限回リトライできるのであれば、最終的には（eventually）メッセージが配送される。
Finite duplication: 配送されたメッセージは有限回しか重複しない（配送完了後も無限にリトライし続けない）。
No creation: Senderが送ってないメッセージが勝手に出現しない。
Message Acknowledgements
いわゆるack。Recipientはメッセージを受け取ったらAckをSenderに返す。これが配送されて初めて配送状況について合意が取れる。
Message retransmits
Linkはメッセージの送信に失敗するかもしれないので、再送に関して戦略を決める必要がある。
Stubborn link: メッセージを無限に再送し続ける。Linkが確率的にしかメッセージをdropしないのであれば、Stubborn linkはいずれ送信に成功する。成功しても無限に再送し続ける。
Stubborn linkは明らかに実用的ではないので、現実にはAckと組み合わせる必要がある。
Ackを使う場合でも、リトライに際して「Ackが戻ってきていない」以上の情報は得られない。特に、Recipientがメッセージを受信して既に処理を完了したかどうかは分からない。
Idempotent operation: 冪等な処理。1回実行するのと、連続して複数回実行するのとで、最終的な結果が変わらないことを意味する。メッセージによってトリガーされる処理がIdempotentなら再送は安全になる。
実際には全ての処理を冪等に設計するのは無理があるため、現実的には冪等性と等価な保障を与えることになる。たとえばdeduplicationによって、メッセージそのものは冪等ではないが、Senderから見れば冪等であるという状況を作ることができる。
これは、同じメッセージが複数回配送されたとしても、実際には最初のメッセージしか実行されないという意味である。2回目以降に配送された同じメッセージは無視される（⇔メッセージが冪等なら、無視せずに単に実行すればよい）。
Perfect Link
全てのメッセージに連続した通し番号を振るようにして、Recipientが「今まで受信した最大値」と「今まで処理した最大値」を記録することで、deduplicationができるようになる。実装はこれに限らないが、このようなdeduplicationを含む以下の条件を満たすようなLinkをPerfect Linkという。
Reliable delivery: 一度でもSenderが送ったメッセージは、最終的にはRecipientに配送される。
No duplication: 全てのメッセージは高々1回しか配送されない。
No creation: Senderが送ってないメッセージが勝手に出現しない。
Exactly-once delivery
あるメッセージがちょうど1回だけ配送される性質をExactly-once deliveryという。同様にAt-least-once deliveryとAt-most-once deliveryも考えられる。
メッセージを複数回送信せずに信頼性の高いLinkを作ることは現実には不可能だが、上記Message retransmitsで見たように、duplicationを無視することで上位レイヤーにとってはあたかもExactly-onceであるかのように見せかけることができる。これはExactly-once deliveryとExactly-once processingに問題を分割したものと考えることができる。
一般に、Exactly-once deliveryを保障するためには、SenderとRecipientがメッセージの状態についてcommon knowledgeを持つ必要がある。すなわち、両者の間でメッセージの状態について合意が取れる必要がある。これは理論的には不可能であることが知られている（Two Generals' Problem）が、実用的にはいくつかの条件が緩和されていてもcommon knowledgeを持つと言うことがある。
FLP Impossiblity
データの状態について複数のノード間で合意が取れているとはどういうことかを形式的に扱うため、Consensus protocolを考える。これは以下の3条件からなる。
Agreement: 各ノードはデータがある特定の値であると判断を下す。この値は全てのノードで共通していなければならない。
Validity: 合意された値は、システム内のどれかのノードが提案したものでなければならない。つまり、システム全体の状態から「神」が合意されるべき値を与えてるようなモデルであってはならない。
Termination: 合意が取れているときは、全てのノードは判断を下していなければならない。
FLP Impossibility Problemは、非同期的かつ共通の時計がないシステムでは、有限時間で停止するConsensus protocolは実現不可能であるという定理である。ただし、現実のシステムには多かれ少なかれ同期的な部分があるし、ある程度の正確性を持つ時計も使えるので、実用的なconsensus protocolを考えることができる。
（この辺の話題はDesigning Data-Intensive Applicationsで詳しく議論されていたはず。）
Failure Models
失敗のモデルとして、以下のようなものが考えられる（これが全てではない）。
Crash Faults: ノードがクラッシュして、アルゴリズムは即座に停止する。クラッシュ以降は何も出力しなくなる。
Omission Faults: アルゴリズムのいくつかのステップが飛ばされるか、実行されたとしても外部からそれと分からない状態になっている。特定のステップから後すべてが飛ばされている場合はCrash Faultと等価になる。ネットワークの遅延やノードの過負荷などによって引き起こされる。
Arbitrary Faults (Byzantine Faults): ノードはアルゴリズムのステップを飛ばさず実行し続けているが、なんらかの理由によって本来の設計と矛盾する出力をしている。バグなどによって引き起こされる。