Distributed Algorithm Basics (VIII) - Fault-Tolerant Consensus - 杨一江的博客 |...

Distributed Algorithm Basics (VIII)

这是分布式算法笔记的第八章，讲述了节点故障情况下同步系统中的共识算法。

共识算法是分布式算法中非常重要的算法，涉及的方面非常广泛，之前的协调进攻算法可以当作在 link failure 情况下的共识算法问题。但是由于主要参考Attiya教材，因此本章讨论的仅限于节点故障情况下的。对于非同步系统中的共识问题，将在之后的笔记中单独阐述。

• 共识算法考虑两种情况下的节点故障
  • 停机故障(crash failure)：指的是由于处理器故障，导致不能发送报文
  • 拜占庭故障(Byzantine failure)：指的是存在一些处理器，他发送的报文和当前的状态无关，这些处理器可以是抽风的，也可能是恶意的，甚至可以伪装成停机故障
• 本次问题中的网络结构是完全图(complete graph)，每一个节点都与其他节点为邻
• 只有在同步系统中才能完美地解决共识问题，在非同步的系统中共识算法并不存在，查看Simulations笔记

Synchronous System with crash failure

Formal model

• 共识算法中，对于原先的同步MP系统进行相应的补充，达到形式化停机(crash failure)描述的目的。在本次问题中。一个系统描述的重要特性是f-抗性(resilient)，指的是一个系统中最多发生停机的处理器的个数。
• 共识算法中，追加了对于执行的描述。在可靠(reliable)的同步MP系统中，一系列的轮次组成了执行，每一个轮次涵盖了报文传送和单步计算。在f-_resilient_系统中
  • 存在一个由故障(faulty)处理器组成的子集F​，最大元素个数是f​。这个子集在每一步的执行中都可能是不同的，因此无法提前知道哪些处理器出现故障
  • 每一个轮次中，对于不在F中的处理器，都有且只有一次计算事件；而对于在F中的处理器，最多有一次计算事件，并且本轮次没有计算事件的处理器往后都不再会有计算事件
  • 在某个故障处理器最后一次进行计算事件的那个轮次之后，该处理器待发送报文中有随机一部份会被发送，这个特性将会增加停机模型的难度，这种随机性的效应要求共识算法更加健壮
• 在上述的系统中，每个处理器都存在两个特殊的组件(component)，一个是作为输入的xi，另一个是作为输出的yi（也被称为主意_decision_）。开始的时候，xi的取值是良序集(well-ordered set)的某个可能的取值，一般来说是事先指定的并且不会更改，而yi的取值是待定的。值得注意的是，yi只能取一次值(irreversible)。共识问题应当满足一下的条件：
  • Termination： In every admissible execution, yi is eventually assigned a value, for every non-faulty processor pi
  • Agreement：In every execution, if yi and yj are assigned, then yi=yj (no conflicts)
  • Validity：if all the processors have the same input, then any value decided upon must be that common input. In another word, the value of y must not be a trivial or static one, it has something to do with the inputs x1,x2,…, and can respond to the incoming situation.

Algorithm

整个算法的过程中，每个处理器都在维护一个集合，涵盖了这个处理器所知道存在着的值，初始的时候是自己的输入(input)。在算法迭代的过程中，处理器向周围人发送之前没有发送过的集合元素（即v has not been sent yet），并且利用将来自其他处理器的集合Sj更新本地维护的集合。当到最后一轮的时候，选取集合中最小的元素作为输出。

Initially V = {x}

for(k = 1; k <= f+1; ++k):
	send [(v has not been sent yet) for v in V] to this.neighbors
	receive [(S[j] from p_j) for j in this.neighbors]
	V = V.conjunction(S[0], S[1], ..., S[this.neighbor.length-1])
	if (k == f+1)
		y = min(V)

由于失效节点在最后一轮计算事件之后，会随机的发送部分的待发送报文，因此在crash failure条件下共识算法需要不少于f+1轮次才能完成。

• Termination：显然，只有f+1轮
• Agreement：在每一个执行的第 f+1轮次结束的时候，对于每一对非故障的处理器来说Vi=Vj。下面证明上述引理：设第r轮的时候x第一次加入Vi，如果x初始化的时候就已经在Vi中，那么x=0
  • 当r≤f时，显然在第r+1≤f+1轮的时候能够Vi=Vj
  • 当r=f+1的时候，不妨设pj是在f+1的时候第一次接收到x的非故障处理器，因此x到达pj一定经过一条长度为f+1的传送链pi1,…,pif+1,pj。因为每个处理器不会重复发送同一个输入，因此pj之前x一定经过f+1个不同的处理器，因此这其中至少有一个是故障的处理器
• Validity：显然，每一个正常处理器的输出都是某一个处理器的输入

Synchronous system with Byzantine failure

Formal model

• 共识算法中，对于原先的同步MP系统进行相应的补充，达到形式化停机(crash failure)描述的目的。在本次问题中。一个系统描述的重要特性是f-抗性(resilient)，指的是一个系统中最多发生停机的处理器的个数。
• 共识算法中，追加了对于执行的描述。在可靠(reliable)的同步MP系统中，一系列的轮次组成了执行，每一个轮次涵盖了报文传送和单步计算。在f-_resilient_系统中
  • 存在一个由故障(faulty)处理器组成的子集F，最大元素个数是f。这个子集在每一步的执行中都可能是不同的，因此无法提前知道哪些处理器出现故障
  • 每对于在F中的处理器，每次计算事件之后的处理器状态将不再限制(constrain)报文的内容，也就是说，这个故障的处理器表现得乖张(arbitrarily)，甚至是恶意的(maliciously)。当然，这个故障的处理器也可以伪装成(mimic)停机故障
• 在上述的系统中，每个处理器都存在两个特殊的组件(component)，一个是作为输入的xi，另一个是作为输出的yi（也被称为主意_decision_）。开始的时候，xi的取值是良序集(well-ordered set)的某个可能的取值，而yi的取值是待定的。值得注意的是，yi只能取一次值(irreversible)。共识问题应当满足一下的条件：
  • Termination： In every admissible execution, yi is eventually assigned a value, for every non-faulty processor pi
  • Agreement：In every execution, if yi and yj are assigned, then yi=yj (no conflicts)
  • Validity：if all the processors have the same input, then any value decided upon must be that common input

Exponential Algorithm

整个算法分为两个阶段，第一阶段是收集信息，第二阶段是根据收集到的信息，逐层归纳。因此，我们通过构建前缀树来描述整个算法的过程。抗性为n≥3f+1，是根据对于某个报文所经过的处理器中非故障处理器占主要部分(n−f≥2f+1)产生的。

前缀树的构建

• 每个处理器都在本地维护一棵前缀树
• 深度为f+1，并且从树根到叶子都要经过f+2个节点
• 每个节点都有标签串，树根是空串\empty。记中间节点v
  • v的标签i1,i2,…,ir，r是v所在的深度，该节点上的取值来自于处理器ir。
  • 对于每一个未在i1,i2,…,ir中出现的处理器j，节点v都有对应的子节点i1,i2,…,ir,j【没有一个处理器会在标签串中出现两次】

####Gathering stage: exactly f+1 rounds

• 开始阶段
  • 每个处理器向所有人（包括自己）发送初始输入x，并将初始输入保存在根节点
  • 当收到来自pj的报文xj，将其保存在标签为pj的节点上
  • 如果从pj收到的x不合法(not legitimate)或者是没有收到来自pj的报文，给标签为pj的节点写上v⊥
  • 将x打上标签pj，并发送给除了pj的其他处理器
• 在第r轮的时候
  • 处理器pi接受到来自pj的报文x，其标签为i1,i2,…,ir。将x存储在标签为i1,i2,…,ir,j的节点上，记该节点的值为treei(i1,i2,…,ir,j)
  • 报文不合法或者未接受的，对应节点写上v⊥
  • 将x打上标签i1,i2,…,ir,j，并发送给标签上未出现过的处理器。
• 在第f+1轮的时候，等到本地维护的前缀树每个节点都有赋值时，进入归纳阶段

Reduction stage

归纳阶段是建立在之前建立好的前缀树上，记在以π为根节点的子树上的归纳为resolvei(π)，而处理器yi的取值就是对于根节点的归纳resolvei(\empty)。归纳函数resolve的递归定义是：

1. 若π为叶子节点，那么resolve(π)=tree(π)
2. resolve(π)取π的所有子节点归纳结果中最为频繁的一个，如果没有就取v⊥

• 时间复杂度O(f+1)
• 报文复杂度O(n2(f+1))，但是报文的长度指数级上升，最长的报文包含的标签长度可以达到n(n−1)(n−2)…(n−(f+1))=Θ(nf+2)

*有效性前引理

1. Lemma 5.9 对于每个非故障的处理器pi的前缀树，树上每个标记为π=π′j且pj为非故障处理器的节点，该节点上的归纳都满足resolvei(π)=treej(π′)

   1. 如果π是叶子节点，那么resolvei(π)=treei(π)。由于treej(π′)的值是上一轮由pj发送到pi的，并且根据算法被pi保存到treei(π′j)=treei(π)的，因此，如果pj不是故障节点，那么就满足resolvei(π)=treei(π)=treej(π′)（对于拜占庭式故障节点，由pj发送的报文可能是任何值，因此存在treei(π)≠treej(π′)的情况），得证

   2. 如果π是中间节点，我们假设在它任意的非故障子节点πk中（即pk为非故障处理器），满足resolvei(πk)=treek(π)。

      • 因为pj也是非故障的，因此pj能够准确的将treej(π′)的值发送给pk，因此treek(π′k)=treej(π′)，因此，对于每个非故障节点pk，都能满足resolvei(πk)=treej(π′)

      • 它的深度不会超过f。每个节点的度数(degree)与深度有关，满足d=n−r。因此，π的度数至少为n−f≥2f+1，因此非故障子节点总能占到大多数
      • 根据定义resolvei(π)取子节点归纳结果中的大多数。由于正常的节点归纳结果都为treej(π′)，并且正常节点占子节点中的大多数，因此resolvei(π)=treej(π′)

2. Definition

   1. 公共节点(common node)：对于任意两个非故障处理器pi,pj，有resolvei(π)=resolvej(π)，那么π就是个公共节点
   2. 公共阵线(common frontier)：在子树中，如果从根到叶的每一个路径上都存在一个公共节点，那么这棵子树局势公共阵线

3. Lemma 5.10 如果以π为根节点的子树是个公共阵线，那么π就是个公共节点

   1. 如果π是叶子节点，显然
   2. 如果π是中间节点，根据假设π的所有子节点都满足这样的性质。反设如果π-子树是公共阵线但π不是公共节点，那么根据公共阵线定义可以推出，所有子节点的子树都是公共阵线，因此所有的子节点都是公共节点。根据归纳定义，resolvei(π)取自最常见子归纳；根据公共节点定义，这些子归纳在任何正常处理器上都相同，因此在任意正常处理器上的π归纳也相同，得证

####有效性

• Termination: 显然f+1轮结束
• Agreement: 前缀树表示了报文传播路径，而每一条从根节点到叶节点的路径长度都是f+1，意味报文经过了f+1个不同的处理器，那么至少有一个处理器一定是正常的，因此在这个正常的处理器对应的节点应当是公共节点（在同一轮的发送阶段，正常处理器对所有处理器发送的报文应该是一致的），那么意味着这整棵都是公共阵线，因此对于所有正常的处理器，做出相同的决定
• Validity: 如果所有处理器的输入都是v，那么对于任意一个处理器pi，由于yi=resolvei(\empty)，因此yi应当是子节点归纳中最频繁的一个。而对于任意的子节点j，resolvei(j)=treej(\empty)=xj=v，这样根据定义pi的决定就是v，满足Validity

Polynomial Algorithm

该算法使用多项式长度的报文，但是带来了更多的轮数和更弱的抗性(resilience)，为n≥4f+1，是根据收到的报文始终占所有处理器中的大部分(n−f>n/2+f)产生的。每个处理器都会维护一个本地的pref数组记录当前最受欢迎的选择。该算法可以将运算的过程分为f+1个阶段(phase)，每个阶段分为有两轮：

• 第一轮是选择(preference)阶段，选择出现最多次数的选择(<maj,m_count>)，如果找不到，就拿v⊥标记
• 第二个阶段就要判断下一轮的选择，如果接受到的最多次选项出现的频率超过n/2+f个，那么就将第一轮中最多出现次数的选择(this.maj)作为下一轮的选择(pref[i])，否则就将来自主宰(king)处理器中最多出现的选择(king_maj)作为自己的选择。

Initially pref[i] = x and pref[j] for any j != i

in the round 2k-1 (1<=k<=f+1):
	send pref[i] to this.neighbors
	receive v[j] from other proccessors and store at pref[j]
	from pref[0...n-1] select the majority <maj, m_count> except <nil, 0>

in the round 2k (1<=k<=f+1):
	if i == k
		send this.maj to this.neighbors
	receive king_maj from this.kings[k].pid
	if this.m_count > n/2 + f
		pref[i] = this.maj
	else
		pref[i] = king_maj
	if k == f+1
		y = pref[i]

*有效性前引理

1. persistence of agreement: if all non-faulty processors prefer v at the beginning of phase k, then they all prefer v at the end of phase k, for all k:1≤k≤f+1
   • 在第一阶段，每个处理器（加上自己发送的）会接受到至少n−f个相同的报文v
   • 在第二阶段，由于n≥4f，因此n−f≥n/2+f，因此会坚持第一阶段中的众数作为pref[i]
2. Lemma 5.13: Let g be a phase whose king pg is non-faulty. Then all non-faulty processors finish phase g with the same preference
   • 假设所有的非故障节点都不能满足this.m_count>n/2+f的条件，那么自然的都会选择king_maj
   • 假设一些非故障节点满足this.m_count>n/2+f的条件，比如说pi，那么说明pi接收到的报文v的个数超过n/2+f，那么说明其他处理器接收到至少有n/2个该报文v，包括king，因此king_maj=v，从而pi的选择也和king相同

• Termination: 显然2(f+1)轮结束
• Agreement: 整个系统中最多有f个故障节点，而在算法的f+1轮中，总有一个非故障节点能够成为king。根据Lemma 5.13引理，所有的非故障节点都能得到相同的v，再根据persistence of agreement这些相同的v将成为最终的一致的选择
• Validity: 借助persistence of agreement性质，我们可以知道，如果所有的非故障处理器拥有相同的初始v，那么整个算法的过程中他们会一直选择v，最终在f+1阶段选择v作为输出