分布式计算拓扑理论与安全共识的迭代模型

可在www.sciencedirect.com在线获取理论计算机科学电子笔记283（2012）29-51www.elsevier.com/locate/entcs安全一致分布式计算拓扑理论简介Rodolfo Conde1，2 and Sergio Rajsbaum3，4InstitutodeMatem'ticasUniversidadNacionalAuto'nomadeM'exic oCiudadUniversitaria，M'exicoD.F. 04510，M'exico摘要分布式计算理论与组合拓扑和代数拓扑有着深刻而迷人的联系。促进分布式计算拓扑理论发展的关键思想之一是使用迭代共享内存模型。在这种模型中，进程通过一系列共享对象进行通信。 进程以相同的顺序异步地逐个访问对象序列。每个进程只访问一次共享对象。在迭代模型的最基本形式中，任何数量的进程都可能崩溃，共享对象是快照对象。 进程可以向这样的对象写入一个值，并获取其内容的快照本文的目的是介绍这一研究领域，使用基于安全共识任务的迭代模型（Afek，Gafni和Lieber，DISC'09）。 在安全共识任务中，共识的有效性条件被削弱如下。如果第一个调用解决安全共识任务的对象的进程在任何其他进程调用它之前返回，那么该进程将返回自己的输入;否则该任务返回的值可以是任意的。与共识一样，协议要求总是向所有进程返回相同的值详细描述了一种基于安全共识的迭代模型。它解释了它的运行可以用单纯复形来描述。分布式计算的拓扑理论的迭代内存模型的有用性展示了一些新的结果（非常干净和结构良好的证明）的（n，k）-集协议任务的可解性全文的主要思想是用大量直观的例子来解释关键词：分布式系统，无等待，集合一致性，一致性，安全一致性，拓扑。1引言分布式计算理论是计算机科学的一个积极发展的领域，它与组合拓扑和代数拓扑有着深刻而迷人的联系其中一个关键的想法，促进发展的拓扑1由国家科学技术委员会赠款支助2电子邮件：rodolfo@math.unam.mx3由DGAPA-PAPIME和PAPIIT赠款支助4电子邮件：rajsbaum@math.unam.mx1571-0661 © 2012 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2012.05.00430R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）29分布式计算的理论是使用迭代共享内存模型，在[10]中介绍。在这种模型中，进程通过一系列共享对象进行通信。进程以相同的顺序异步地每个进程只访问一次共享对象在迭代模型的最基本形式中，任何数量的进程都可能崩溃，共享对象是快照对象。进程可以向这样的对象写入一个值，并获取其内容的快照。众所周知，这个模型等价于标准的无等待读/写共享内存模型[10，15]，但它的运行比标准共享内存模型中的运行更结构化，更容易分析。迭代共享内存模型的递归性质对于[ 10 ]中的结果和[ 19 ]中的异步可计算性定理的证明是有用的。这个定理揭示了拓扑学和分布式计算之间存在的密切联系。基本迭代模型的扩展也被研究，其中进程通过比快照对象更强大的对象序列进行通信[16]，或者系统的可扩展性仅限于模型故障检测器[22]。关于迭代方法的概述，请参见[21]。本文的目的是介绍这一研究领域（非专业人士），使用基于Afek，Gafni和Lieber [2]的安全共识在安全共识任务中，共识的有效性条件[13] 被削弱如下。如果第一个调用解决安全共识任务的对象的进程在任何其他进程调用它之前返回，那么该进程将返回自己的输入;否则该任务返回的值可以是任意的。与共识一样，协议要求总是向所有进程返回相同的值在[2]中引入了安全一致性任务（作为一致性问题的推广），以证明[3]的g紧群重命名任务与g过程的一致性任务的等价性。本文还证明了安全共识任务与共识任务一样强大。我们以两种方式定义了一个迭代的基于安全共识的共享内存模型：经典方式和“拓扑方式”。之后，我们展示了它的有用性，以及它与拓扑的联系，展示了一些关于共识和（n，k）-集一致性的可解性的新结果（具有简单，结构良好的证明）[11]（其中n是过程的数量）。 虽然在共识任务过程中，在最多一个值上，（n，k）-set agreement任务允许进程在最多k个不同的值上达成一致。本文所研究的迭代模型是迭代模型的推广[10]有着安全共识对象的力量。安全共识对象是一个共享对象，它从进程接收输入值，并向进程返回与安全共识任务规范一致的输出值（第3节）。新模型允许进程通过使用一系列快照对象和安全共识对象进行通信。与任何迭代模型一样，计算在迭代中进行，异步地以相同的顺序访问对象的副本。在每次迭代中，每个进程首先写入共享内存，然后调用安全共识对象，最后获取共享内存的快照为R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）2931本文的目的是提供一个易于阅读的介绍该领域，我们将在我们的新扩展模型中添加一个额外的限制：序列中的每个安全共识对象必须被所有进程调用（并且以相同的顺序）。 我们称这种计算模型为迭代共享内存与完全安全共识对象（IFSC）模型。具体而言，我们提出的结果是：• （n，n-1）-set协议任务可以在IFSC模型中仅使用一个安全共识对象来实现（使用简单的单轮协议，定理3.2）;• 在IFSC模型中，不可能解决n个过程的一致性问题（定理3.6）。这些结果表明，IFSC模型确实比基本迭代模型更强大，因为（n，n-1）-集一致性不能仅使用共享内存解决[8，18，23]。但是IFSC模型仍然有局限性，因为它不能解决共识（而共识可以使用没有限制的安全共识对象[2]来解决这种不可能性并不是因为我们工作在一个迭代模型中，而是因为在每次迭代中，进程都要访问同一个安全共识对象。此外，在分布式计算的拓扑理论中，为了表示迭代模型（和扩展IFSC模型）中协议的执行，我们将对定理3.6有一些说明。众所周知，迭代共享内存模型中的协议复合体是连接的，因此不可能解决共识[7，19]。在本文中，我们认为，IFSC模型中的协议复合体是断开的，但这些协议不能解决共识。关于定理3.6的讨论在第3节。总之，我们在这篇介绍性论文中的目的包括解释：(i) 如何在迭代模型中分析协议复杂连通性(ii) 通信对象的能力如何影响协议复合体的连通性(iii) 以及连通性对任务可解性的影响。如上所述，迭代共享内存模型已经扩展了比读/写寄存器更强大的对象[16]，但是这些对象最多和设置协议任务一样强大。 据我们所知，这是第一次尝试通过添加与共识问题一样强大的对象来研究迭代模型。然而，我们强调，我们在本文中的意图不是提供新的结果，而是介绍该领域。 在本文[12]的续集，我们更深入地研究了用安全一致性对象扩展的迭代模型。其中一个模型是IFSC模型。论文的提纲如下。在第2节中，我们介绍了迭代共享内存模型的基本概念（在通常的组合方式），然后我们展示了如何表示协议的行为的组合拓扑结构，使用单纯复形。在这里，我们也给出了定义32R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）29（n，k）-集协议任务[11]，我们将集中注意力的任务。在第3节中，我们扩展了共享内存的基本迭代模型，的安全共识对象，以获得上述IFSC模型。 我们使用第2节介绍的工具研究IFSC模型。在整个论文中，我们用简单的例子解释了概念和证明背后的主要思想。第四节是我们的结论。2迭代共享内存模型我们现在介绍分布式计算的迭代共享内存模型[10]，并解释该模型中协议的运行如何具有根据单纯复形给出2.1基本计算模型我们的形式模型是标准的，参见例如[6]，所以我们不在这里详细说明。一个系统由n个进程p1，...， p n. 进程是一个确定性状态机，它有一个（可能无限的）局部状态集，包括一个称为初始状态的子集和一个称为输出状态的子集。进程通过共享内存进行通信，共享内存的结构是由有限数量的单写多读原子寄存器组成的一系列数组SM（i）[1···n]（i0）。每个寄存器可以从某个域获得值，该域包括特殊的我们不对寄存器的大小做任何假设，因此我们可以假设每个进程pi可以将其整个状态写入单个寄存器。 每个共享存储器SM（i）提供两个原子操作，它们最多只能被进程使用一次• SM（i ）。write（）：将某个值写入寄存器SM（i ）[j]，其中j是pr 〇cesspj的id。• SM（i）。snapshot（）：返回整个共享存储器阵列SM（i）的副本。我们假设w.l.o.g.进程总是交替进行写操作和快照操作。注意快照操作可以在读/写共享内存中实现[1]。一个（系统）状态由进程的本地状态和共享内存中的所有寄存器组成。形式上，状态是一个向量S = 1，...，s n; SM n，其中si是进程pi的本地状态，SM是系统的共享内存初始状态是其中每个局部状态是初始局部状态并且共享存储器中的所有寄存器都被设置为NULL的状态。决策状态是所有局部状态都是输出状态的状态事件和回合时间表系统的事件由单个进程pi执行，其仅应用以下动作之一：写（W）或读（R）操作（即，快照）。任何R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）2933（一）（二）（三）initri←0;smi ←inputi;deci ←deci;永久循环SM（ri）. write（i）;sm i← SM（ri）. return（）;i←i+1;（六）（七）（八）（九）如果（deci=0），则end if末端回路deci←δ（smi）;在这些操作之前/之后可以进行一些局部计算，形式上，将进程更改为下一个本地状态。考虑并发执行的事件是方便的。如果E是任意事件，且p i1，...，p ik是过程，则我们表示p i1，.，p ik并发地执行事件E乘E（i1，.，i k）。一个循环时间表是一个有限序列的形式E1（j11，.， j1p1），.， E r（j r1，.， j rpr），对进程执行事件E1，...，埃尔河例如，由下式给出的回合时间表：W（1，3），R（1，3），W（2），R（2），意味着进程P1、P3同时执行写和读事件;此后，P2单独执行其读/写事件。 类似地，循环调度W（1， 2， 3），R（1， 2， 3）表示p1，p2，p3并发地执行写/读操作。行动。 设n<$={1， . ，n}。 则w e表示E（1， . ，n）byE（n）;如果A≠n，n−A ={i1，.， i q}，E（n-A）表示E（i1，.， i q）;当A ={i}时，E（n-A）是E（n−i）.决策任务决策任务Δ是具有输入值的域I和域O的关系。输出值;Δ指定输入到过程的每次分配，输出过程可以决定这些分配。任务的例子包括共识[13]，重命名[9，3]和集合协议任务[11]（稍后定义）。图1. 迭代模型中协议的一般形式2.2基本迭代模型每个进程pi的状态机对本地协议Ai进行建模，该本地协议A i确定由pi采取的步骤。我们假设所有的本地协议都是相同的，即过程具有相同的状态机。协议是本地协议A1，...，An.在本文中，我们感兴趣的是在分布式计算的迭代读/写共享内存模型的协议。 从现在开始，我们称之为基本迭代模型。为了简单起见，我们使用伪代码给出协议规范，并建立以下约定：34R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）29表示一个局部变量，其子索引指示它属于哪个进程;共享内存（对所有进程可见）用小写字母表示。图1显示了迭代模型中协议的一般形式协议A的执行是状态和循环调度S0，π1，.的有限或无限交替序列，S k，πk+1，...，其中S0是初始状态，Sk是应用由过程执行的事件序列的结果状态以πk描述的方式。A的r轮部分执行是A的形式为S0，π1，.的有限执行，S r−1，πr，S r，也就是说，A的一次执行直到r轮结束。状态P被称为在A中可达，如果存在A（r0）的r轮部分执行，其在状态P结束，并且当没有混淆时，我们假设S是可达的。我们确定了每个过程状态的两个特殊组成部分：输入和输出。假设初始状态仅在输入分量的值上不同;此外，输入分量永远不会改变。协议不能覆盖输出，它最初是可重写的;一旦一个非可重写的值被写入状态的输出组件，它永远不会改变;当这种情况发生时，我们说进程决定。输出状态是具有非可调输出值的状态。如果任何有限执行α可以扩展，则协议解决决策任务Δ到执行αJ，其中所有进程决定α中输入的允许值（相应于Δ）。 因为输出不能被覆盖，如果一个进程在α中决定了一个值，那么它在αJ中必须有相同的输出。这意味着已经被过程写入的输出可以被完成为输出对于α中输入允许的所有过程。一个协议是无等待的，如果在它的任何执行中，一个进程要么有有限数量的事件，要么它决定。 这意味着，如果一个过程有无限数量的事件，它必须在有限数量的事件之后做出决定我们不要求流程停止;它们通过写入输出组件来解决决策任务并做出决策;流程可以继续参与。我们通常会考虑进程的行为，直到它做出决定，因此，上述区别并不重要。状态的性质假设A是迭代模型中的协议，S，R是状态，我们说R是A中S的后继，如果存在A的执行α，使得α = S0，π1，.，S r= S，π r+1，.，π r+k，S r+k= R，...，也就是说，从S开始，我们可以运行协议Ak轮（对于某个k0），使得系统进入状态R。如果π是任何一个循环调度，S是一个状态，则通过运行协议（从状态S开始）一次循环调度π的迭代而获得的A中S的后继由S·π表示。两个状态S，P被称为相邻的，如果存在一个非空子集Xn，使得所有在X中有id的进程在S和P中都有相同的局部状态。也就是说，对于每个i∈X，pi不能区分S和P。我们将其表示为R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）2935X我当X={i}时，我们使用符号SP。 状态S和P是如果我们能找到一个状态序列S =P1，...， P r=P使得对于所有j当1≤j≤r−1时，Pj和Pj+1相邻。迭代模型与标准模型的等价性我们定义的迭代模型似乎限制太多：进程不能返回并再次读取相同的共享数组。此外，所有进程必须以相同的顺序访问所有共享数组。正因为如此，人们可能会认为它与更标准的非迭代无等待共享内存模型相比不具有完全的通用性，该模型没有对迭代模型中的协议施加的限制。关键的问题是：是否存在一个任务在无等待标准模型中是可解的，而在迭代模型中是不可解的？答案是否定的。每一个在无等待标准模型中可解的任务在迭代模型中也是可解的。这是使用在迭代模型中模拟标准模型的算法来证明的，首先在[10]中，最近在[15]中。因此，在迭代模型中只考虑协议2.3迭代模型的几何我们所描述的研究分布式算法的框架可以用几何术语给出，使用单纯复形。我们假设读者熟悉组合拓扑的基本概念[5，4]。我们从一个例子开始，设n= 3，假设进程p1，p2和p3在迭代模型中执行协议A 在A的第一轮中，进程有几种可能的方式来执行它们对共享内存的读写操作;一种可能性是p1和p2同时执行基本操作，然后p3执行相同的步骤。这由轮调度W（1， 2），R（1， 2），W（3），R（3）表示在回合结束时，p1和p2的共享内存的本地视图只包含这些进程写入的值;它们看不到进程p3写入的值，因为它们的执行速度比p3快，p 3在p1和p2执行读取（快照）操作5之后将其信息写入共享内存。但是p3的这个（系统）状态（在A中是可达的）可以用一个2-单形Δ2表示，如下图所示5这模拟了p3只是运行得比p1和p2慢的可能性，也模拟了p3崩溃并且根本不采取任何步骤的情况。36R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）29000p3W（1，2）R（1，R（3）p1p200⊥00⊥Δ2的每个顶点都标记有进程id和该进程的本地状态（这包括内存的本地视图）。现在考虑三个进程并发执行共享操作的情况（这用轮调度W（1， 2，3），R（1， 2， 3）来描述）以及它们在第一轮结束时对内存的看法与前面的情况一样，我们将这个状态表示为2-单纯形ΔJ2。00⊥000 ⊥⊥0W（1，2） p1R（1，2）W（3）R（3）p200⊥W（1，2，3）R（1，2，3）p3000p2p1000p3中文（简体）R（3）W（1，2）R（1，2）这一次，所有进程都可以看到彼此这就是为什么单形Δ2和ΔJ2的顶点与p3的id为公共面，p 3无法区分这两个状态的原因，因为在这两个单形以类似的方式，通过W（3），R（3），W（1， 2），R（1， 2）描述的方式执行协议的第一轮获得的表示A中可达状态的单纯形与ΔJ2相邻（这次，p1和p2无法区分）。我们可以将A的第一轮中所有可能的可达状态表示为2-单纯形，并构造一个单纯复形，我们称之为A的1-轮协议复形（图2（a））。它只是一个细分的三角形。这个复合体中的每个单纯形代表一个状态S，在进程执行A的第一轮之后，系统可以达到该状态S，该轮调度使协议进入状态S。在第二轮中，进程开始以第一轮结束时的状态执行协议，然后可以重复第一轮如果我们表示这些进程的状态R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）2937(a)（b）第（1）款图2.在第一轮（a）和第二轮（b）执行后，迭代模型中3进程协议的协议复合体。第二轮的开始作为A的1轮协议复合体的对应2-单纯形（即，作为协议的第一轮的可达状态），然后使用我们正在使用计算的迭代模型的事实，我们可以将第二轮结束时系统的所有可能状态编码为细分三角形表示进程在回合结束时的状态一个.这种细分与第一轮的协议复形相同，因此我们可以将A的第二轮中所有可能的可达状态描述为图2（b）的单纯复形，这是A的2轮协议复形。注意这个复形也是一个细分的三角形，有几个同构的子复形第一回合的协议复杂性 这种行为将在所有后续轮次中重复-三个过程的迭代模型中的协议的k轮协议复合体将是2-单纯形的细分。为了得到下一轮的复形，我们只需取前一轮的复形用图2（a）的复形替换其中的每个单形，我们可以看到k轮协议复合体具有简单而优雅的递归结构。一般来说，如果我们有n+ 1个进程，则进程的每个可能的初始或最终局部状态被建模为顶点v=（i，smi），这是由进程idi和进程pi的局部状态smi。我们说顶点用进程id着色。一组n + 1个相互相容的初始或最终局部状态被表示为n-单纯形Δn，我们用它来模拟一个可能的系统状态。给定迭代模型中的协议A，其中每个进程p i接收输入值v i（i = 1，...，n + 1），对于每个轮数r0，在轮r结束时A中的所有可能的可达状态被表示为n维复合体，r轮协议复合体（为简洁起见，我们仅称之为“协议复合体”）PA，其中每个顶点被标记有进程id和轮r结束时的进程状态。因此，PA中的每个单纯形对应于执行的等价类38R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）29对于顶点上的进程来说在[10]中，PA总是一个细分的n-单形.在[19]中有关于协议复合体的更多信息。事实上，我们已经给出了r轮协议复杂度PA的定义（与进程开始执行协议时的输入值相关联），A）与[19，定义4.4，第884页]中的跨度概念密切相关。Herlihy和Saught将协议复合体定义为一个更大的几何结构，它依赖于所有可能的进程输入值和所有可能的进程执行。A方案然而，对于大多数情况，使用我们给出的协议复杂度的定义就足够了。 我们发现我们的定义足够的目的，这篇介绍性的论文。2.4设置协议任务我们感兴趣的是（n，k）-集协议任务，其中n是进程的数量和k n。这个任务是在[11]中首次提出的，它是分布式计算研究的基础。其描述如下：（n，k）-集合一致性问题在这个任务中，每个过程都从集合I（|我|n），并且必须输出一个值，使得：• 终止：每个进程最终都必须输出一些值。• k-一致性：来自所有过程的输出值的集合最多必须是大小K.• 有效性：如果某个过程输出v，则v是某个过程的初始输入集合一致性任务是一致性的自然推广，它对应于（n，1）-集合一致性任务.也就是说，流程必须就唯一的输出值达成一致。在集合一致性任务被定义之前，众所周知，即使只有一个错误过程，共识问题也是不可解的[13]。这个不可能性结果使用了简单的图连通性参数。但是自从（n，k）-集合一致性任务被提出以来，它是否可以在无等待共享记忆模型（参数为2≤k n）中解决一直是一个悬而未决的问题，直到1993年，三个独立的团队[8，23，18]表明没有可以解决集合一致性的无等待协议。定理2.1（[8，23，18]）对于1 ≤kn<，（n，k）-集协商任务在迭代共享内存模型中没有无等待读写解.由于迭代模型等价于通常的标准无等待共享模型，定理2.1意味着不可能解决集合一致任务在标准模型中。 值得注意的是，设置协议任务不是只有分布式的问题，拓扑技术已经有用。其他例子有音乐长凳[14]、重命名[19]和循环协议[17]。R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）29393迭代模型的一个扩充在本节中，我们将向迭代模型中添加更强大的共享对象，并研究此扩展模型中集合一致性任务的可解性3.1具有安全一致性我们将添加到迭代模型中的对象基于共识问题的一个变体，称为安全共识。安全共识任务。在这个任务中，每个进程都从集合I中的某个初始输入值开始，并且必须输出一个值，使得：• 终止：每个进程最终都必须输出一些值。• 一致性：所有进程都输出相同的值。• 有效性：（1）如果一个进程pi开始执行任务，并且在任何其他进程开始执行任务之前输出(2)否则，如果两个或多个进程最初并发地访问安全共识任务，则该任务可以返回来自可数集合V的任何值，使得I是V的真子集。安全共识任务是弱化共识有效性条件的结果它首先由Yehuda，Gafni和Lieber [2]提出;他们用它来证明g-紧群重命名任务[3]与g过程的共识一样强大我们现在可以定义新的对象来扩展基本的迭代模型。安全共识对象是一个共享对象，可以被任何数量的进程使用。对象从调用它的每个进程接收一个输入值，并向所有进程返回一个满足安全共识任务的协议和有效性条件的输出值。 换句话说，安全共识对象就像一个使用分布式任务作为协议中的黑盒的方法是研究分布式任务的相对计算能力的标准方法（即，如果一个任务比另一个任务弱）。可以看出，安全共识共享对象是比读/写共享存储器更强大的原语。这是因为在[2]中，作者给出了两个解决分布式计算模型中n请记住，在本文中，为了清楚地阐述该领域，我们使用safe-consensus对象通过在进程调用共享对象的方式中强加一些规则来实现。更准确地说，我们在2.2节定义的基本迭代模型中添加了一个无限的安全共识对象数组;每个对象都提供了一个exec方法，该方法将一个参数作为输入值，并向所有参与进程返回一个唯一的值，满足安全共识任务的属性我们假设40R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）29（一）（二）（三）（四）（五）initri<$0;smi<$inputi;deci<$;screti<$;永久循环SM（ri）. write（i，i，i）;i←i+1;screti←safe-consensus.exec（id）;sm i← SM（ri）. return（）;（七）（八）（九）如果（deci=0），则end ifdeci←δ（smi，screti）;(10)末端回路处理馈送到安全一致对象的输入值是它们自己的ID6。为了本文的目的，我们还假设在每次迭代中，所有的进程都调用相同的安全共识对象，也就是说，在每一轮中只有一个安全共识对象，并且它被所有进程使用。我们将这种计算模型称为具有完全安全共识对象的迭代共享内存（IFSC）模型（图3）。 最后，我们用事件扩展迭代模型的事件集 一个安全共识对象的调用该事件将由S表示。图3. IFSC模型中协议的一般形式（pi的c ode）在继续我们的论述之前，我们想对我们定义的分布式计算模型做一些评论。请注意，在图3中，对safe-consensus对象的调用被放置在写入和读取（快照）共享内存操作之间。 在本文的续集中，[12]中，我们研究了不同的迭代模型，这些模型是通过使用安全共识对象扩展基本迭代模型而产生的。我们要考虑的一个问题就是在哪里调用safe-consensus对象。 正如我们在[12]中所解释的，根据我们将调用放在安全共识对象的位置，我们可以获得非常不同的模型。事实上，[12]中研究的模型之一是IFSC模型的扩展。3.2具有安全共识在我们为基本迭代模型添加了使用安全共识对象的能力之后，我们想回答的第一个问题是：扩展模型中的协议复合体会发生什么？拓扑属性是否不变？为了回答这个问题，我们必须做的第一件事是正式定义新IFSC模型中协议的协议复合体。如果A是IFSC模型中n个进程的协议，A的协议复合体SA的定义与我们在2.3节中定义的协议复合体相同，唯一改变的是与顶点相关联的视图。SA的顶点是元组v=（i，smi，val），其中i是进程pi的id，smi是pi的局部状态，val是由所有进程调用的安全共识对象的返回值。在图4中，我们绘制了IFSC模型中三个进程的协议A的一轮执行的协议复合体SA完整的[6]不难看出，这一假设不失一般性。R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）2941R（1，2）R（1）p3p2p1p3p2p3p1p1p3p3p2p1p2p1p2p2p1p3p3p3p3p1W（1，2，3）S（1，2，3）R（1，2，3）p2p1p2p1p2p1p2（1）S（1）R（1）W（2，S（2，3）R（2，3）p2p1p3p3p3W（1，2）S（1，2）RS（3）R（3）p2p1中文（简体）p3W（2， 3）S（3）S（2， 3）R（3）R（2， 3）W（1， 2）S（1， 2）p1p2（1）S（1）图4. IFSC模型中协议的单轮协议复合体的一部分。整个复合体在底部包含子复合体的可计数数量的拷贝3.1）。复形是一个具有无限个连通分量的不连通空间。显然，这个复合体与图2的复合体不同。每个连接的组件与安全共识任务的输出值相关联。为了理解为什么这是真的，让我们仔细看看子复形，比如图3上面的T3在图4中，它有一个2-单纯形，它表示A的第一轮中的一个状态，该状态可以通过轮调度W（3），S（3），R（3），W（1， 2），S（1， 2），R（1， 2）到达。在该执行中，进程p3比p1和p2更快，因此它单独执行安全共识对象，因此通过安全共识任务的有效性条件现在，如果我们考虑T3的2-单纯形，其表示通过调度W（2， 3），S（2， 3），R（2， 3），W（1），S（1），R（1）可达到的状态，则我们知道p2和p3比p1更快，并且并发地执行安全共识对象，并且通过安全共识任务的有效性条件，共享对象可以返回任何值。所有进程，因此存在安全共识对象的返回值为3的可能性。通过对T3中其它单形的类似分析，我们可以得出结论：T3中每个2-单形的顶点所给定的安全一致值42R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）29正好是3这个子复合体不能有安全共识值为3以外的单纯形。例如，很容易证明，表示执行由W（1），S（1），R（1），W（2，3），S（2，3），R（2，3）给出的A所获得的状态的单纯形不能与T3的任何单纯形相邻（因为不同的安全一致性值）。如果我们现在取图的最左边的子复形T1和最右边的子复形T2（它们都同构于T3），我们可以证明T1只包含顶点的安全一致性值等于1的单形，而T2的所有单形都有顶点的安全一致性值为2。那么图中底部的子复形Bx呢？它包含代表状态的sim-plexes，在这些状态中，safe-consensus对象返回无效的输出值x/= 1， 2， 3。Bx中表示的所有状态都来自至少两个进程并发调用安全共识任务的执行，并且进程从共享对象获得的值正好是x。但是，任务可以返回给进程的无效输出值的数量是可数的，因此对于每个可能的无效值β，在图4的复形中应该有一个子复形Bβ（同构于Bx）。为了简单起见，我们只显示其中一个子复形。总之，协议的第一轮的协议复合体SA是断开的，具有无限数量的连接的子复合体，一个子复合体用于安全共识任务的每个可能的输出值。我们已经描述了IFSC模型中协议的单轮协议复合体。 因为我们工作在迭代模型中，在第二（第三，第四等等）轮中，协议复合体由许多子复合体组成，如T1，T2，T3和BX，前一轮的每个单纯形转换为子复合体，如SA。不难证明，我们所描述的3进程原型的行为，在IFSC模型中，推广到具有任意数量的进程n/= 3的协议。IFSC模型中任何协议的协议复合体都是不连通复合体有无穷多个连通的子复形一般来说，IFSC模型中的协议复合体的结构不像基本迭代模型中的协议复合体3.3用安全一致性解决（n，n-1）-set协议任务我们现在表明，基本迭代模型中的协议与具有安全一致性的扩展模型中的协议之间的差异不仅与几何形状有关。在本节中，我们证明了在扩展模型中，我们可以解决（n，n-1）-n2个进程的集合协议任务，我们知道在迭代模型中不可解的分布式任务[18，23，8]。但我们也证明了我们不能解决每个集合一致性任务，因为在IFSC模型中不可能解决n-一致性（（n，1）-集合一致性）（当n3时）。（n，n-1）-集一致协议图5中的协议在一轮中解决了n2个进程的（n，n-我们继续证明它的正确性。引理3.1对于执行图5中协议第9行的任何进程pi，R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）2943（一）（二）（三）（四）（五）（六）（七）（八）（九）（十）（十一）initdeci，screti，smi←;开始SM. write（i）;screti←safe-consensus.exec（id）;如果sc reti∈{1， . ，n} {\displaystyle{\sqrt}埃森我的意思是我的意思是我的意思。return（）;其他deci←smi[screti];end ifdeci←smi[αi]withαi=min{α|{i[a]/{i};decidedeci;(12)端图5. IFSC模型（codeforpi）中的A（n，n-1）-集合协议(a) 集合A i={α |sm i[α]/= n}至少为2，且min A in。(b) 如果n∈/Ai，则minAi/=n−1。证明（a）假设进程p i执行if / else块的第9行，则sc reti∈/{1， . ..在任何情况下，根据安全共识任务的有效性条件（2），必须存在两个进程pr，ps同时调用安全共识对象。 这些进程在访问safe-consensus对象之前将其输入值写入共享内存，因此当p i获取内存快照时，本地数组sm i至少包含两个非随机值，因此我们有|A我|二、现在假设α i=min A i使得α i=n。一定存在j ∈ Ai，j/= n，但jn <= α i，这是一个矛盾. 因此，我们认为，α in. （b）设n∈/Ai，we可以使用与（a）中所用的相似的公式。拿下这个案子Q定理3.2设n2.在IFSC模型中，（n，n-1）-set一致性问题可以在一轮中使用一个安全共识对象来解决。证明我们证明图5中的协议解决了（n，n − 1）-集一致性。该协议满足（n，n-1）-set协议任务的终止条件设pi为任何进程;在pi将其输入值写入共享内存后，它调用唯一的safe-consensus对象并获取内存快照，pi在第6-10行执行if/else块。首先假设scret i∈ {1，...，n}和sm i[scret i]/= n。然后进程pscreti在pi拍摄快照之前将其输入值写入共享内存，这意味着smi[screti]包含有效的建议输入值，这是进程pi的决定值。另一方面，如果smi[sc reti]=0或screti∈/{1， . .，n}，则继续执行第9行。（a）由引理3.1，集合A i={α|sm i[α]/= n}不为空，使得存在最小元素α i∈ A i，然后当p i将局部寄存器sm i[α i]的内容赋给dec i时，它有一个有效的建议输入值，使得进程p i的判定值是正确的.因此，（n，n-1）-集合一致性问题的有效性条件由协议满足。44R. Conde，S.Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）29我们现在证明，在协议的任何执行中，由进程决定的值集的大小都不大于n-1。 假设进程p i1，...，P IR （r≤n，某些进程可能会崩溃）完成协议的执行，并让D是由进程决定的值的集合。我们通过案例来论证。案例1. 两个或多个进程执行协议的第7 然后|D|当n≤n − 1时，由于所有进程调用了相同的安全共识对象，并且根据安全共识任务的Validity属性，共享对象的返回值对于所有进程都是相同的，因此如果至少有两个进程执行了第7行，则它们决定了相同的值。案例2.只有一个进程pl执行了协议的第7行。设v为安全共识对象返回给所有参与进程的值。那么对于过程pl，我们有scretl=v和sml[v]（它是非线性的）是由pl决定的值。如果v∈ {1，.，n-1}，则|D|≤n− 1，因为对于每个i /= l的进程p i，p i执行if / else块的第二部分，并且根据引理3.1的（a），p i不能决定进程p n提出的值。 另另一方面，如果v=n，则对于所有i l，screti=n和smi[screti] =n，并且这些两个事实意味着A i∈ {1，.，n− 1}。对于引理3.1的（b），我们有minAi n− 1，使得所有其他id不等于l的进程最多决定n-2个值，加上由pl决定的值，最多构成n-1个不同的值，因此|D|≤ n − 1。案例3.未执行方案第7通过引理3.1的（a），对于每个过程p i，我们有α i∈{1，...，n-1}，所以所有进程最多决定n-1个值。在任何情况下，我们都可以得出结论，判定值的集合的大小最多为n-1，因此协议满足（n，n-1）-集合一致性问题的（n-1）-一致性条件，因此协议是正确的。Q3.4IFSC模式无法达成共识定理3.2告诉我们，IFSC模型比基本迭代模型更强大，因为在新模型中我们可以解决（n，n-1）-集合一致性问题。但现在我们将证明，在IFSC模型中，我们不能解决共识，即，（n，1）-set协议。试图解决分布式系统分布式计算[13，20，7]的各种模型中一致性的不可能结果和迭代模型[19，8，24]中集合一致性的不可能结果表明，解决分布式环境中的一致性与图的