两将军问题,又被称为两将军悖论、两军问题, 是一个经典的计算机思想实验 。
首先,为避免混淆,我们需要认识到两将军问题虽然与拜占庭将军问题相关,但两者不是一个东西 。拜占庭将军问题是一个更通用的两将军问题版本,通常在分布式系统故障容错、区块链中广泛讨论 。1.双将军问题
![两将军问题和TCP三次握手](http://img.zhejianglong.com/231018/0F33V549-0.png)
文章插图
两支军队,驻扎在两个山头,准备攻击山谷里的同一伙敌人,两将军只有同时发起进攻才能获胜,两将军通信的的唯一方式是派遣信使通过山谷,山谷处于敌占区 。如果信使被俘获了,那么攻击信息将会丢失 。
宏观现象一: 两将军先后派遣信使,交替确认收到的攻击信息,交替确认是无止尽的,两将军不能达成共识 。
微观现象二: 将军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三次握手](http://img.zhejianglong.com/231018/0F33U103-1.png)
文章插图
知乎上有个问题: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 三次握手是在两个方向确认包的序列号 , 增加了超时重试,是两将军问题的一个工程解 。
(本文部分内容提炼自知乎 , 感谢这届网友的智慧)
推荐阅读
- C++栈和典型迷宫问题
- .Net Framework中的AppDomain.AssemblyResolve事件的常见用法、问题,以及解决办法
- JavaWeb505错误,IDEA版问题解决
- ArcMap布局添加图表问题
- 剑网三会战唐门老一的问题 剑三会战唐门攻略
- Java并发编程 | 从进程、线程到并发问题实例解决
- 一个 dubbo 和 springboot 的兼容性问题
- 申请qq号是怎么申请的(怎么申请两个qq号)
- 怎么养兔子 兔子怎么养(两只公兔子一只母兔子能一起养吗)
- 关于HM NISEDIT在新版系统下编译并运行提示权限不足问题的解决方案