比特币 - 共识机制之两军问题
先来看一下人与人之间的共识机制
人与人的合作活动，无时不刻在发生，绝大多数情况下，达成共识是前提条件。先来想一想生活中最常见的情形，有利于理解电脑/进程间如何达成一致
达成共识涉及的元素
达成共识包括:
提议(若m个提议Pi, 0 < i <= m)
决定人群(n个决定人Di, 0 < i <= n)
达成共识的人群(s个达成共识的人Ci, 0 < i <= s)
我们不考虑反悔，以及阳奉阴违的情况。
达成共识的不同情形
提议可以来自于任何人，可以是做决定的人，或达成共识的人，甚至其他的人。
同时提议可能是开放型，任意的，比如开会时大家可以自由提出解决方案。
也可能是有限的选项，比如选举。
决定的人只有一个，这叫独裁或家长制。做决定的人是部分的达成共识的人，这叫人民代表或议会制度。全体达成共识的人都参与决定，这叫P2P对等网络，哈哈哈。
达成一致的条件有全体同意; 全体同意但一两票反对; 绝对多数，比如80%、90%; 简单多数即大于50%
有意思的是consensus和agreement是不同的。前者相对后者不同在于即使决议对某些人不是最有利的，所有人也一致接受
所以共识不但表示我认同了某个信息，我还知道其他人也认同了同样的信息。为了达到这样的一致性，人们通过各种媒体进行交流都觉得不够，还需要面对面开会来协商。
两军问题 - 一个悲伤的故事
话说两位将军要合力攻击一个敌人，他们单独的实力都没有敌人强，独自攻击只会遭受失败，被各个击破，是送死的行为，只有同时进攻才能获得胜利。现在的问题是如何约定同一个时间发动攻击。他们的位置如下图，意味着信使可能被敌军拦截
图片来自wiki
于是将军A1通过信使M发送给将军A2消息'明天临晨5点进攻'。第二天将军A1准时发起进攻但是将军A2没来，结果A1失败，而A2很快也将被单独打败，原来是信使M被敌军拦截了。还好将军A1还可以使用SL大法，再来一次，这次将军A1决定等到确认了将军A2收到信息以后再发起进攻。
因为是SL，第二次信使M成功躲开敌军将消息发给了将军A2，但是却不小心在回将军A1的路上被抓了。结果是将军A1没有收到确认按兵不动，而将军A2独自进攻，后果不言自明。
还好可以SL，这一次将军A2决定受到了将军A1确认的消息以后再发动进攻。不幸的是这次M虽然成功给A1确认，却在再次给A2确认的路上被抓了，结果A1独自进攻，而A2按兵不动。
A1将军此时也悲伤地意识到了，即使有SL大法也无法完全保证两边100%确认同时进攻，因为这样的确认将无穷无尽。
FLP impossibility
In 1985 Michael Fischer, Nancy Lynch, and Michael Paterson showed that fault-tolerant agreement is impossible in an asynchronous system.
他们的论文中给出了数学证明，因此获得业界的Dijkstra奖，FLP正是三人名字的缩写。
有兴趣的童鞋请自行搜索相关资料了解。
而我在发现分布式算法的大坑以后果断绕行。
两军问题在现实生活中的解决方案
也许你会象我一样疑惑现实中我们为什么没有遇到这样的问题，下面来看看其中两个解决方案
工业解决方案
假定信使传递信息需要t时间，发出消息2t时间后，将军A1若收到来自A2的ack则不再发送信息而是决定进攻，若未收到A2的ack则继续发消息。若将军A2在收到A1的消息后，比如200t后都未收到新消息，那么也决定攻击。因为200t的时间里都未收到新消息，表示要么A1已确认收到A2的ack，要么A1再发出的100条消息都被拦截，这样的概率可能极小。我们可以在消息上加上顺序号来估算n次通信失败的几率来决定n的大小。
中心化
考虑我们使用网上银行，支付宝的情形，我们难道不是再查询一次发现余额正确就放心了吗？实际上这里只以银行为准，你可以找银行确认，但是银行并不会向你确认，这就是中心化的模式。由于达成一致如此之难，中心化是一个非常常见的解决方案，而信任本身就是价值，生活中随处可见。中心才有决定权，还有最多的信息，你只能提议(甚至不能提议)，被达成共识，这个世界也基本上这样运行。
仍然还有疑问
概率的计算
如果确认的次数越多，信心就越强，考虑到信心即概率，这个概率该如何计算呢？(数学渣啊)
两军问题在同步的场景下的解决方案
既然这是个异步场景才会发生的问题，那么在同步机制下又是什么情况呢？我开始怀疑自己原来对同步异步的理解
PAXOS
你说啥？你说还可以聊一聊著名的paxos算法以及实现，比如Google的chubby, 阿里巴巴的oceanbase，还引出了CAP。但是现在我只想了解比特币，谢谢逃
