Omission fault

プロセスのOmission fault

• プロセスがメッセージの送受信に失敗する

ネットワークのOmission fault

• 通信リンクがメッセージを消失する

定理: Omissionに耐え、両プロセスが停止する決定性送信アルゴリズムは存在しない(Two generals problem, Coordinated attack problem)

• プロセス$P$からプロセス$Q$へ、リンク$l$を介してメッセージ$m$を送信することを考える
• $l$は脱落故障を起こしメッセージが消失する可能性がある
• $P$はメッセージ$m$を繰り返し$Q$に送信することでOmission failureに耐えようとするが、いかなる時間上限$\delta$を設定したとしても(=Partially synchronous system, Synchronous System?)全ての送信が失敗する可能性があるので、永遠に送り続ける必要がある
• $Q$はメッセージを受診したら返信$A_Q(m)$を返すことで、Pの送信をやめさせようとする
• $A_Q(m)$も繰り返し送り続ける必要がある…(Pが更に返答を返し、Qが更に返答を返し…無限ループ)
• 背理法: いつか解消されると仮定し最後に必要となるメッセージを$A_P{A}_Q...A_Q(m)$とする。$P$はある回数だけ$A_P{A}_Q...A_Q(m)$を送信した後、終了する。送信された全ての$A_P{A}_Q...A_Q(m)$が消失する可能性があるから、結局Qは $A_P{A}_Q...A_Q(m)$ を受診しなくとも終了できることになる。すなはち、最後のメッセージ$A_P{A}_Q...A_Q(m)$は不必要であることになり、矛盾が導かれる

参考

• Some constraints and tradeoffs in the design of network communications (SOSP’75)