共识算法的作用和意义（共识算法涉及的概念）

通信复杂度

大家可以发现网络消息数从O(NN)下降到O(N)
  
  
  
  
  
  
  
，但因为每个prepareQC包含2f + 1 签名 
  
  
  
  
  
  
 ，所以通信量复杂度还是O(NＮ)
  
  
  
  
  
  
  
。

密码学的进步：包含2f + 1 签名信息的prepareQC 


 


 


 


 


 


 


 ，使用门限签名
 
 
 
 
 
 
 
，使得占用空间降至O(1)  
   
   
   
   
   
   
 ，整个通信量复杂度下降到O(N)

通信模型

通信模型定义了对手延迟消息的权力限制 

 

 

 

 

 

 

 ，有三种基本通信模型：同步模型              、异步模型和部分同步模型 
  
  
  
  
  
  
 。

同步模型：假定最大的网络延时T

 

 

 

 

 

 

 
，得设置比较大（min级别？） 


 


 


 


 


 


 


 。因为实际情况              ，网络可以出问题 
 

 
 

 
 

 
 

 
 

 
 

 
 

 ，而解决问题可能几分钟














，也可能几小时                     ，甚至几天
 
 
 
 
 
 
 
。

异步模型: 网络时延无保证 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，网络是无法保证达成共识的





















，著名的FLP定理

-半异步模型: partial synchronous model              ，上面两个模型的折中也叫部分同步 
 
  
 
  
 
  
 
  
 
  
 
  
 
  ，网络可能处于异步状态













，但是GST（global stable time）后会进入同步状态

大部分共识算法都是基于半同步模型
  
  
  
  
  
  
  
，这也符合实际情况 
  
  
  
  
  
  
 ，可以参考下文  
   
   
   
   
   
   
 。

https://decentralizedthoughts.github.io/2019-06-01-2019-5-31-models/

响应性（Responsiveness）

一旦网络进入同步状态 


 


 


 


 


 


 


 ，好的leader以实际网络延时的速度
 
 
 
 
 
 
 
，达成共识 

 

 

 

 

 

 

 。

也叫做(Optimistic) Responsiveness乐观响应性  
   
   
   
   
   
   
 ，我觉得也比较直观

 

 

 

 

 

 

 
。就是网络达到同步状态（GST）后 

 

 

 

 

 

 

 ，即解决了所有网络问题后

 

 

 

 

 

 

 
，真正干完活所需的时间和实际网络延迟一致              。类似于要搬1000块砖              ，现在砖也准备好了 
 

 
 

 
 

 
 

 
 

 
 

 
 

 ，人也吃饱喝足了














，那么假定一分钟搬10块砖                     ，100分钟就能搬完 
 

 
 

 
 

 
 

 
 

 
 

 
 

 。

(Optimistic) Responsiveness After GST, any correct leader, once designated, needs to wait just for the first (n−f) responses to guarantee that it can create a proposal that will make progress. “As fast as the network propagates, on a good day
  
  
  
  
  
  
  
”

安全性（safety）

坏事情永远不发生 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，即所有的好节点不可能提交(commit)相冲突的数据

注意区别密码学的security





















，这个概念其实和共识算法无关              ，区块链中的security是通过密码学保证














。

活性（liveness）

只要系统网络进入同步状态 
 
  
 
  
 
  
 
  
 
  
 
  
 
  ，系统最终都能达成新共识                     。

区块链中就是链的高度会增长













，不断出新块 
 
 
 
 
 
 
 
 
 
 
 
 
 
 。

参考链接https://blog.csdn.net/wenyuanhust/article/details/125495449