1. 首頁 > 生活百科 > >

兩將軍問題和TCP三次握手

生活百科

兩將軍問題，又被稱為兩將軍悖論、兩軍問題， 是一個經典的計算機思想實驗 。

首先，為避免混淆，我們需要認識到兩將軍問題雖然與拜占庭將軍問題相關，但兩者不是一個東西 。拜占庭將軍問題是一個更通用的兩將軍問題版本，通常在分布式系統故障容錯、區塊鏈中廣泛討論 。
1.雙將軍問題
兩將軍問題和TCP三次握手

文章插圖
兩支軍隊，駐扎在兩個山頭，準備攻擊山谷里的同一伙敵人，兩將軍只有同時發起進攻才能獲勝，兩將軍通信的的唯一方式是派遣信使通過山谷，山谷處于敵占區 。如果信使被俘獲了，那么攻擊信息將會丟失 。
宏觀現象一： 兩將軍先后派遣信使，交替確認收到的攻擊信息，交替確認是無止盡的，兩將軍不能達成共識 。
微觀現象二： 將軍A派遣信使，過了很長時間未收到回復，將軍A不知道是自己的信使被俘獲了還是將軍B的確認信使被俘獲了 。
我們意識到無論交替傳遞多少次信息，兩將軍都不能達成同一時間攻擊的共識 。
兩將軍問題是無解的，目前的tcp三次握手、四次揮手都是工程解(這個一會再聊) 。
2.雙將軍問題的頭腦風暴許多人試圖解決/緩解雙將軍問題，提出了一些能落地的實踐 。
這里我們依舊還是假設通道的不確定性 ， 信使只會被俘獲 ， 但是不會叛變篡改 。
2.1 霰彈打鳥如果A將軍每次派遣100名信使(編號1到100) ， 期待B將軍最差也能收到一名信使的信息 。
B將軍根據收到的信使數量，評估這條通道的可靠性，并根據概率也派遣合適數量的確認信使 。
eg: A 將軍派遣100信使，B將軍收到10名信使的信息，B將軍基本可確認這條信道可靠度為1/10 ， B將軍最少應派出10名信使(根據概率會有1名信使到達對岸) 。
2.2 間歇性重試霰彈打鳥的姿勢太費信使了，但是可以幫助將軍提高信心，達成共識 。
還有一種少費信使(并能提高將軍信心)的策略 ， 假設跨越山谷到達對岸并返回耗時20min，A將軍可間隔20min派遣信使到對岸，直到收到對岸B將軍的首次信使確認(就不再派遣) 。
以上兩種策略分別是對速度和成本的權衡，采用哪一種取決于哪一種更適合我們遇到的問題 。
3. 為什么說tcp三次握手是雙將軍問題的工程解？
兩將軍問題和TCP三次握手

文章插圖
知乎上有個問題：TCP 為什么是三次握手，而不是兩次或四次？分別從三個角度回答 。
  • ① TCP 為什么是三次握手，而不是兩次或四次？ - 朋克雪球兔的回答 - 知乎
  • ② (TCP 為什么是三次握手，而不是兩次或四次？ - 車小胖的回答 - 知乎
  • ③ TCP 為什么是三次握手，而不是兩次或四次？ - wuxinliulei的回答 - 知乎
希望大家仔細讀一讀 。
首先我們要知道：
三次握手是為了在兩個方向上同步(syn)序列號(seq=m)，同步一次序列號需要一去一回兩個包，倆方向就4個包 。第2，3個包由一側發出可以合并到一起所以最后三個包 。
但是根據雙將軍問題，誰說一來一回兩個包就能確保同步成功 。
為了緩解雙將軍問題，tcp3次握手增加了超時重試的機制 。
第一個包： A發送給B的SYN中途丟失 ， 沒有到達B
A會周期性超時重傳，直到收到B的確認 。
第二個包，即是發送給A的SYN+ACK 中途丟失 ， 沒有到達A
B會周期性超時重傳，直到收到A的確認 。（實際上，A因為沒有收到確認，也會重傳）
第三個包：即A發送給ACK 中途丟失，沒有到達B
A發完ACK ， 單方面認為tcp Established狀態 ， 而B顯然認為tcp為Active狀態 。
a. 假定此時雙方都沒有數據發送，B會周期性超時重傳，直到收到A的確認，收到之后B的TCP 連接也為 Established狀態，雙向可以發包 。
b. 假定此時A有數據發送，B收到A的 Data + ACK，自然會切換為established 狀態，并接受A的 Data 。
c. 假定B有數據發送，數據發送不了，會一直周期性超時重傳SYN + ACK，直到收到A的確認才可以發送數據 。
小林coding 有一篇講解了握手異常 很是牛叉
總結本文記錄了兩將軍問題: 對于不可靠信道，無數次確認都不能達成可靠共識 。TCP 三次握手是在兩個方向確認包的序列號 ，  增加了超時重試，是兩將軍問題的一個工程解 。
（本文部分內容提煉自知乎 ， 感謝這屆網友的智慧）

推薦閱讀