(并行与分布式计算十四)
故障模型和拜占庭故障的概念
故障模型
初始死进程: 如果在局部算法中没执行过一步，则称进程为初始死进程
损毁模型(crash model): 如果进程正确地执行局部算法到某一时刻，此后并不进一步执行，则称它是损毁的
Byzantine行为(Byzantine behavior): 如果进程执行了与局部算法不一致的任意步，则称进程是Byzantine的。尤其是Byzantine进发送的消息可能包含任意内容
健壮算法提出的正确性要求总是指正确进程的局部状态(或者输出)。初始死进程从不会产生输出，且它的状态总是等于它的初始状态。如果损毁进程有输出，则它的输出是正确的，因为到损毁发生时，进程的行为是正确的。一个Byzantine进程的局部状态或者输出可以使任意的，任何算法都不满足Byzantine进程的非平凡性要求
故障模型的层次
- 可将错误模型分为三个层次
- 初始死进程课看作损毁进程的特例
- 损毁出现在进程的第一个事件之前
- 损毁进程可看作Byzantine进程的特例
- 对Byzantine进程假设的任意行为包括根本不执行任何一步
容忍损毁要比容忍初始死进程要困难，容忍Byzantine进程更困难
- 由于规定不同，健壮Byzantine算法也是健壮损毁算法，健壮损毁算法也是健壮初始死进程算法
- 健壮初始死进程算法的不可能性蕴含着健壮损毁算法的不可能性，而健壮损毁算法的不可能性蕴含着健壮Byzantine算法的不可能性。
拜占庭故障的恢复
- 进程组的内部结构：
- 平面结构：所有的进程是平等的，没有任何一个进程处于领导地位，任何决定都是共同做出的。
- 层次结构：在最简单的层次结构的进程组中，一个进程是协调者，其他所有的进程为工作者。无论是进程组外的一个顾客，还是进程组中的一个工作者向进程组发出一个工作请求，由协调者决定哪一个工作者最适合这项工作，并且将此工作请求转交给它。
进程组管理：对于进程组通信来说，需要一定的办法进行进程组的创建和删除，同时还要允许进程能加入到一个进程组中去以及允许一个进程离开一个进程组。
- 集中式管理：设置一个进程组服务员，所有的服务请求都发送给进程组服务员。进程组服务员使用一个数据库来保存所有进程组的信息和一个进程组中所有成员的有关信息。
- 分布式管理：另外一个进程组管理的办法是采用分布式的方式管理进程组。例如当一个组外的进程要加入到这个进程组时，它向这个进程组中的所有成员发送一个报文，申明自己要加入到这个进程组。
利用进程组屏蔽错误：进程组是构造容错系统问题的一部分。特别是，如果用相同的进程来构成一个进程组，那么就能够屏蔽进程组中一个或多个出错的进程。也就是说，我们可以用多个相同的进程构造一个进程组，用这个容错的进程组取代相对脆弱的单个进程。
利用进程组进行容错需要多少个进程副本：
- 故障—停止型故障：如果进程组中有k+1个进程，那么就足以提供k故障容错。
- 拜占庭式故障：那么为了取得k故障容错，那么至少需要2k+1个进程。
利用进程副本实现的分布式容错:
对于本质上不是分布式却要求高可靠性的计算机应用设计，部分故障性质使得利用分布式(“复制的”)体系结构称为有吸引力的选择。航天飞机的主计算机系统就是一个例子。Spector和Gifford[SG84]描述了它的研制。飞机主要由不需定制的微处理器控制，在设计中主要关注的是它在航行过程中处理器发生故障的可能性。最终控制系统由4个相同处理器组成。
每个处理器只进行同样的计算，激励者号对结果进行投票，即使一个处理器发生故障，也能完全控制系统。(激励者号的物理实现表明，即使第二个处理器后来发生故障，系统也能继续运行。)尽管复制是增加可靠性的有吸引力的一种选择，但是需要协调一群(不可靠)的处理器的算法设计远非那么简单。
容错系统中的一致性算法简介
- 分布式一致算法基本目标：是使得对于某个问题来说，所有非出错的进程能够达成一致，并且能够在有限的步骤内达成一致。
- 分布式一致算法的正确性条件：
- (1) 一致性。所有正确的进程取得一致的结果，而且是最后的结果；
- (2) 合法性。所有进程同意的结果必须来自某个正确的进程的输入；
- (3) 有限性。每个进程在有限的步骤内取得一致的结果。
交互一致性：系统中的每个非出错进程都使用来自进程Pi的同样的值来进行决策。这样，一般的一致性问题就变为系统中的进程都同意一个特殊的进程(比如P0)的值。确切地说：
- 所有非出错进程都使用进程P0的同样的值v0。
- 如果发送进程P0是非出错的，那么所有非出错进程都使用P0发送的值。
- 结论：在有k个出错节点的情况下，只有进程的总数至少为3k+1时才能获得一致。
LAMPORT交互一致性算法IC
该算法是一个递归算法，存在多个递归轮次。
算法IC(m)，m<k，开始时m=0，S={}：
发送者将它的值和发送者列表S发送给其他的进程，共(n-1-m)个；
设v_i是进程P_i从发送者接收到的值或者是如果没有收到值时使用的缺省值。在IC(m+1≠k)时进程P_i作为发送者，将结果v_i和发送者列表S∪{P_i}发送给其他不在发送者列表中的n-2-m个进程。如果m+1=k，则调用IC(k)；
对每个进程P_i，设v_j是进程P_j接收到的值(但是由P_j转发给P_i)。节点使用值majority(v_j)，$j \in S$；
- 算法IC(k)：
发送者将它的值发送给其他n-k-1个进程；
每个进程使用从接收者收到的值，或者，如果它没有收到任何值，就使用缺省值。
- 结论：上述算法中，被交换的报文总数为(n-1)(n-2)…(n-k-1)，其复杂度为O(n^k)，k可以是(n-1)/3。
实例：具有7个进程的例子，P_i，0≤i≤6。假定k=2，即最多有2个故障，n=7。设P_0是初始发送者，发送值为1。不妨设P_5和P_6是出错进程，它向其他进程发送不确定的值。在这个例子中共需要k+1=3轮信息交换：
- P_0将{V_0,S}={1,{P_0}}发送给进程P_1，P_2，…，P_6
- P_1至P_6中每个进程都接收到报文{1,{P_0}} ，它们将所收到的报文转发给除了开始的发送者和它本身之外的所有其他的进程。例如P_1向P_2至P_6发送报文{1,{P_0,P_1}}。它分别从P_2至P_6处接收到报文{1,{P_0,P_2}}、{1,{P_0,P_3}}、{1,{P_0,P_4}}、{d,{P_0,P_5}}、{d,{P_0,P_6}}
- 在第三轮中，P_1将报文{1,{P_0,P_2}}以{1,{P_0,P_2,P_1}}的形式分别发送给进程P_3、P_4、P_5、P_6，将报文{1,{P_0,P_3}}以{1,{P_0,P_3,P_1}}的形式分别发送给进程P_2、P_4、P_5、P_6，将报文{1,{P_0,P_4}}以{1,{P_0,P_4,P_1}}的形式分别发送给进程P_2、P_3、P_5、P_6，将报文{d,{P_0,P_5}}以{d,{P_0,P_5,P_1}}的形式分别发送给进程P_2、P_3、P_4、P_6，将报文{d,{P_0,P_6}}以{d,{P_0,P_6,P_1}}的形式分别发送给进程P_2、P_3、P_4、P_5。第三轮递归结束，返回第二轮
- 进程P1收到报文{1,{P_0,P_2,P_3}}、{1,{P_0,P_2,P_4}}、{d,{P_0,P_2,P_5}}、{d,{P_0,P_2,P_6}}，连同在第二轮中收到的报文{1,{P_0,P_2}}，将这5个报文中的值执行majority(1,1,d,d,1)=1，得到的这个新值1作为报文{1,{P_0,P_2}}的新值，记为新报文{1,{P_0,P_2}}’。同样的道理，得到新报文{1,{P_0,P_3}}’、{1,{P_0,P_4}}’、{1,{P_0,P_5}}’、{1,{P_0,P_6}}’。第二轮递归结束，返回第1轮
- P1对6个报文{1,{P_0}}、{1,{P_0,P_2}}’、{1,{P_0,P_3}}’、{1,{P_0,P_4}}’、{1,{P_0,P_5}}’、{1,{P_0,P_6}}’ 中的值执行majority(1,1,1,1,1,1)=1，这个新值是P1所确信的最终值。
可以通过对每个发送者都重复同样的协议将交互一致性扩展到多个发送者的情况。 扩展的方法：在第k轮收到的值将被发送到所有的其他节点，而不仅仅是那些没有被发送过的节点。
- 实例：假定有4位将军，其中有一个叛徒。将军之间相互通报自己的人数，忠诚的将军说实话，叛徒恶意地将不同的值通报给其他将军。不失一般性，设将军P1是叛徒，它分别向其他3位将军谎报自己军队的人数是x、y、z，将军P2向所有的将军通报自己的人数是4000，将军P3向所有的将军通报自己的人数是5000，将军P4向所有的将军通报自己的人数是6000。
- 分析：
- P_i要对每个P_j的值做判定
- 判定的方法是根据其它进程的内一轮的判定来取多数值（majority）
- P_i对于每个P_j来做的判定，如果系统中存在k个错误，则在IC算法的最内轮次至少需要2k+1个进程的投票才能实现可靠的判定（因为有k个投票可能是错的）