Two General's Problem

想起唸博班時，讀到Nancy Lynch寫的Distributed Algorithms。這本書在還沒談任何分散式演算法之前，就列出了不少的impossibility result。其中最令我吃驚的定理是，若兩個程序純粹以訊息交換(message passing)的方式溝通，那麼在訊息可能遺失的前提下，沒有任何協定可以保證這兩個程序能達成完全一致的共識(consensus)。不能達成共識的原因並非溝通的事情太複雜。例如，可以想像這兩個程序只是很單純地想共同確定某個二元變數A的值是0還是1。

如果兩個程序連單一變數的值都無法達成共識，那麼其他fancy的演算法(leader election, termination detection, gloal snapshot, self-stabilization, ...)都是建立在隨時可能垮掉的基礎上。

在網路的課程中，我們通常稱這個困境為Two General's Problem。根據這個定理，TCP的three-way handshake可能導致client與server兩端對TCP連線是否已經建立起來有不同的看法。例如，three-way handshake的最後一個ack如果沒有被server收到，則client會認為連線已建立，而server會認為未建立。而這個問題理論上是沒有辦法解決的。

理論與現實的差異就在這裡。這個理論上不完美的TCP three-way handshake已經為網際網路貢獻幾十年了，而每年學生都還是要從頭開始認識它的不完美。