计算同步与异步系统中的集协议问题统一的公理化方法及其下界证明

理论计算机科学电子笔记230（2009）79-102www.elsevier.com/locate/entcs计算同步与异步系统（初步版本）Maurice Herlihy1计算机科学系，布朗大学普罗维登斯，RI 02912，美国Sergio Rajsbaum2InstitutodeMatem'ti cas，UNAMCiudad Universitaria，D.F.04510，墨西哥马克·塔特尔3惠普实验室地址：One Cambridge Center，Cambridge，MA 02142，USA摘要我们提出了一个统一的，公理化的方法来证明在同步和异步消息传递模型中的k集协议问题的下界。 证明涉及到构建一组可达状态，证明这些状态是高度连接的，然后呼吁一个众所周知的拓扑结果，高连通性意味着集协议是不可能的。我们使用我们定义的轮运算符以迭代方式构造可达状态集，并且我们的连通性证明是基于这种迭代构造和轮运算符的简单性质的保留字：容错，一致性，集合一致性，同步，异步，拓扑。1介绍共识问题[18]受到了极大的关注。 在这个问题上- lem，n+1个处理器从输入值开始，并且所有处理器必须在其中一个上达成一致1电子邮件：mph@cs.brown.edu2电子邮件：rajsbaum@math.unam.mx。 部分由亚 太 经 社会-墨西哥国立自治大学赠款支助。3电子邮件：mark. hp.com1571-0661/© 2009由Elsevier B. V.出版，CC BY-NC-ND许可下开放获取。doi：10.1016/j.entcs.2009.02.01880M. Herlihy等人/理论计算机科学电子笔记230（2009）79−值作为其输出值。 费舍尔、林奇和帕特森[7]震惊了世界通过证明在异步系统中，如果允许一个处理器失败，解决共识是不可能的。这让人想知道是否有任何方法可以削弱共识，以获得一个问题，可以解决在存在k1个失败，但不存在k个失败。Chaudhuri [5]定义了k-set协议问题，并证明这是一个这样的问题，三篇论文[4，13，19]证明了她是正确的。k-集一致性问题是一致性的推广，在这里我们放松了处理器对单个值达成一致的要求：处理器选择的输出值集可以包含多达k个不同的值，而不仅仅是1。集合一致性（特别是一致性）在同步和异步计算模型中都有研究，但大多是独立的。事实上，这些模型的先前证明似乎没有什么共同之处，正如该领域的主要教科书[14]的组织所反映的那样，其中第一部分专门讨论同步系统，第二部分讨论异步系统。 最近的工作已经揭示了越来越多的功能和结构这两个模型的共同点[8，12，15，16]。然而，这些结果是以模型之间的转换的形式，或者在两个模型中具有相似结构的证明。只有[15]描述了一个包含这两个模型的抽象模型，具有执行一致不可能结果所需的明确识别的属性。从一致性到集合一致性是复杂性的一大步，因为人们必须处理高维拓扑而不仅仅是图，正如上面提到的三篇论文[4，13，19]所发现的那样。本文的贡献是提出了一种新的公理化方法，可以得出一致的不可能性证明同步和异步模型在一个统一的方式。所有已知的集合一致性下界的证明都依赖于--无论是这些证明实质上考虑了单纯复形表示一个集合协议的所有可能的可达状态，然后讨论这个复形的连通性。这些集合一致性的下限来自于这样的观察，即如果可达状态的复合体是充分高度连通的，则集合一致性不能被解决。连通性和集合一致性之间的这种联系已经以通用的方式[11]和特定计算模型的方式[1，4，6，10，11，12，19]建立。然而，一旦建立了连接，问题就归结为对协议的可达复合体的连通性的推理。这项工作的主要贡献是一个新的，基本上更简单的证明如何连接的同步和异步复杂的演变随着时间的推移。我们的证明依赖于两个关键的见解：(i) 一个循环运算符的概念，它将一个全局状态映射到通过一轮计算从这个状态可到达的全局状态集，这个运算符满足一些简单的代数性质。(ii) 吸收偏序集的概念将全局状态集组织成一个M. Herlihy等人/理论计算机科学电子笔记230（2009）7981偏序，从连通性证明遵循容易使用轮运算符我们相信这种新方法具有几个新颖而优雅的特征。首先，我们能够分离出一小部分轮算子的基本组合性质，这些性质可以以一种与模型无关的方式与经典拓扑学建立联系。第二，这些属性只需要局部推理计算如何从一轮到下一轮。最后，大多数连通性参数都很难遵循，因为它们混合了语义、组合和拓扑参数。这些论点在这里被清楚地分开了。轮运算符的定义依赖于语义：它是同步模型属性的组合重述。然而，一旦定义了轮运算符，我们就不再求助于原始模型的性质。我们的理由在一个纯粹的组合的方式对全球国家的交叉点，以及如何将它们放置在一个偏序。 一旦这些组合论证到位， 著名的拓扑学定理来建立连通性。这些拓扑理论被视为此外，我们的吸收偏序集非常类似于可壳复形[3]，这是拓扑学家的工作与分布式计算之间的又一个联系。我们的大部分证明都在附录中。2预赛2.1模型我们考虑两个（标准）消息传递模型，同步和异步模型。 在这两个模型中，我们将注意力限制在计算上，循环结构：每个处理器的初始状态是其输入值，并且计算以循环序列进行。在每一轮中，每个处理器向其他处理器发送消息，接收该轮中其他处理器发送给它的消息，执行一些内部计算，并改变状态。我们假设处理器遵循全信息协议，这意味着每个处理器在每一轮中将其整个本地状态发送给每个处理器。这是一个标准的假设时，证明下限。处理器可能会在一轮中崩溃而失败，在这种情况下，它只将其状态发送给子集在这一轮的处理器。一旦处理器崩溃，它就不会再发送另一条消息。在同步模型[2，14]中，所有处理器同时执行回合r，并且处理器P未能从处理器Q接收到消息，则Q必须在该回合或前一回合中崩溃在异步模型中，对处理器步进时间和消息传递时间都没有限制，因此无法区分崩溃的处理器和缓慢的处理器。然而，我们的结果只依赖于无限的消息传递时间。由于我们的目标是证明不可能的结果，我们可以自由地限制我们的82M. Herlihy等人/理论计算机科学电子笔记230（2009）79P;0R;1Q;2R;PRQ;PQQ不合格R失败PQR P，PQ无失效PQR QP失败Q;QRR;QRFig. 1. 全局状态S和从S开始一轮后的全局状态集合S1（S）。注意执行，其中处理器以规则的速度采取步骤，并且仅延迟消息传递时间。在我们考虑的行为中，从一个处理器到另一个处理器的消息是按FIFO顺序传递的，但是当从P到Q的一个消息被传递时，从P到Q的所有未完成的消息都被同时传递。以下面的遗漏-失败形式重铸异步模型是很方便的。在每一轮中，最多f个处理器表现出错误的行为，尽管这个集合可能会从一轮到另一轮而变化。在每一轮中，非故障处理器将其状态广播给所有处理器（包括故障处理器）。每个故障处理器将其状态广播给处理器的某个子集，并且可能忽略发送给其他处理器。处理器永远不会崩溃。可以证明，在这个遗漏故障模型中的k-集一致性下限可以延续到标准异步崩溃故障模型;类似的论点见[9]2.2组合拓扑我们用一个顶点来表示一个处理器的本地状态，这个顶点用处理器的id和它的本地状态来标记我们将全局状态表示为一组标记的顶点，标记有不同的处理器，表示该全局状态中每个处理器的局部状态在拓扑学中，单形是顶点的集合，而复形是在包含下封闭单形的维数等于它的顶点数减1。拓扑在分布式计算中的应用通常假设这些顶点是空间中的点，而单纯形是这些点的凸包，以便能够使用标准拓扑结果。当你阅读这篇论文时，你可能会发现用这种方式思考单纯形是很有帮助的，但是在本文所做的纯组合工作中，单纯形只是一组顶点。作为一个例子，考虑图1所示的单纯形和复数。 对在左侧，我们看到一个表示初始全局状态的单纯形，其中处理器P、Q和R从输入值0、2和1开始每个顶点标记为M. Herlihy等人/理论计算机科学电子笔记230（2009）7983SSSPPPC CPC−P| |PC C−一个处理器的id和它的本地状态（在本例中只是它的输入值）。 对右边我们看到一个复合体，代表一轮后出现的一组状态如果允许一个处理器崩溃，那么在同步模型中从这个初始状态开始的计算量。顶点的标记由处理器id（例如P）和处理器id串（例如P Q）示意性地表示。 字符串PQP在该轮期间从处理器P和Q听到但不从R听到的事实，因为R在该轮失败。 (We忽略输入值 （注：这是为了简化符号）。表示一轮后状态的单形是中心的二维三角形和从三角形辐射的一维边（包括三角形本身的边）。中间的三角形表示一轮之后没有处理器失败的状态。每条边表示一个处理器发生故障后的状态。例如，具有标记为P;PQR和Q;PQ的顶点的边表示在一轮之后的全局状态，其中R通过向P发送消息而不向Q发送消息而失败：P从所有三个处理器听到，但Q没有从R听到。我们在本文中所做的是定义轮算子，如将图1左侧的单纯形S映射到右侧的复形1（S）的轮算子11（S）。 非正式地说，0维的连通性只是普通的图连通性，而更高维的连通性意味着在复合体中没有该维的“洞”。 当我们推理连通性时，我们经常谈论单形S的连通性，而实际上我们指的是由S和S组成的诱导复形的连通性。所有的面孔。例如，图1中的两个复形都是0-连通的，因为它们在图论意义上是连通的。 事实上，左边的复形也是1-连通的，但右边的复形不是，因为有给定一个单形S，S从集合V的一个标号是一个新的单形，它是通过用一对（s，v）替换S的每个顶点s而构造的，其中v ∈ V。给定一个单形S和一个集合V，我们将伪球面（S，V）定义为S与V的元素的标号的集合。(We称（S，V）为伪球面，因为它具有球面的一些拓扑性质。面S称为伪球面的基单形，给定伪球面（S，V）的单形T，我们定义基（T）为伪球面的基单形Sk-集合一致性的输入复形是（S，V），其中每个顶点都标记有来自集合V的输入，其中V> k。具有初始状态（S，V）的协议P的所有可达状态的集合是协议复合体=（（S，V））。k-集一致性和连通性之间的基本联系可以用下面的定理来表达（例如，[11]）：定理2.1设P是一个协议，设P是它的协议复形。若P是（k1）-连通的，则P不能解k-集一致.因此，我们的主要任务将是证明它是（k1）-连通的。证明复形的并集是连通的，通过下面的定理4变得更容易。通知4实际上，这个定理是Mayer-Vietoris序列的一个众所周知的推论，84M. Herlihy等人/理论计算机科学电子笔记230（2009）79CC我如果A和B是复形，那么A<$B和A<$B都是复形。定理2.2（Mayer-Vietoris）设A，B是两个复形。则A<$B是c-连通的，如果A和B是c-连通的，并且A<$B是（c-1）-连通的。考虑这个陈述的特殊一维情况：一个由子图A和B组成的图是0-连通的（在图论意义上是连通的），如果A和B是0-连通的，并且A<$B是-1-连通的（非空的）。为了证明一个复杂的是c连通的，我们就分开了分解成子复合体，越来越少的单形，并反复应用迈耶-维托里斯定理。在这个递归的底部，我们得到只有一个单纯形的复形，并使用以下事实。定理2.3维数至少为l的单形是（l-1）-连通的。在本文中，我们从拓扑学出发所需要假设的就是前面的两个定理。两者都是出现在标准教科书中的非常基本的代数拓扑事实，如[17，20]。3吸收偏序集与舍入算子两个单形S0和S1的余维数是它们有多少的度量 共同定义为codim（S0，S1）=max{dim（Si）−dim（jSj）}其中dim（n）=−1是emp ty单纯形的维数。这个定义的两个有用的特性是，如果S是T，则codim（S，T）= dim（T）−dim（S），如果SXT，则codim（S，T）= codim（S，X）+codim（X，T）。设S是单形的非空集合，且≤S上的偏序。定义3.1我们说（S，≤）是吸收偏序集，如果对每两个单形S且T在S中，且T/≤S，存在TS在S中，TS≤T，使得（1）第一章：codim（TS，T）= 1（2）codim（S，T）≤ codim（S，T）.（三）前两个性质说，当考虑成对的单丛交叉时-正如我们在Mayer-Vietoris论点中经常做的那样-成对的高大多数代数拓扑教科书;例如见[20]第4章第6节。M. Herlihy等人/理论计算机科学电子笔记230（2009）7985S∩≤一≥一QQQQQ/LLL余维数被 第三个属性只是说 T S满足与S和T相同的性质，即codim（ST，X）codim（S，T），其中X=S，T。吸收偏序集几乎等价于可壳复形[3]。在一个可壳复形中，方程2和3只适用于复形的主面（因此，每个吸收偏序集诱导一个可壳复形，但反之则不然。引理3.2如果A是单形集，使得每对单形都有余维1，则（A，<）是吸收偏序集，其中<是A上的任意全序。证据 对于任意的单形S和T，使得S< T，取TS=S。 用S代替TS，很容易检查定义3.1的三个条件是否满足：ST STcodim（S，T）= 1codim（S）≤ codim（S，T）.Q3.1公理单纯算子是一族映射。每个映射l携带一个维数为m l的单形到一个非空的单形集合，其中每个单形的维数最多为m。下标l是算子的次数。对于l<0，定义为l（S）是空集。 注意l（）=为了所有的我，0（S）=对于任何非空单形S。单纯形算子自然地扩展到单纯形的集合。如果是一组单丛，Ql（A）=Ql（A）。（四）A∈A单纯算子的语义解释因模型而异。在同步消息传递模型中，l是每轮中可能崩溃的处理器数量在异步模型中，l是在每一轮中保持部分静默的处理器的数量我们使用QkQl（S）来表示应用于S的Qk和Ql的复合，Qr（S）表示应用于S的Ql的r-倍复合，并且Qr（S）表示由集合Qr（S）诱导的单纯复形（即，封闭在容器中）。我们假设单纯算子满足以下公理。 第一个公理说，在l个处理器失效后可达到的状态在更多处理器失效公理3.3当l≤m.Ql（S）Qm（S）86M. Herlihy等人/理论计算机科学电子笔记230（2009）79S∈ QKRKK第二个公理描述了多轮执行。我们引入一个模型特定的、非负的、整数值线性函数φ。非正式地，φ（f）是在一轮中隐藏f个故障处理器的存在所需的故障数。我们将看到，在同步模型中，故障处理器崩溃，因此φ（f）= 0。在异步模型中，故障处理器无法发送消息，因此φ（f）= f。公理3.4设k ≥ l，S <$T，其中c = codim（S，T）. 对于所有r> 0，对于所有Jrk−φ（c） Ql−c（S），存在TJ∈ QrQl（T）使得SJ<$TJ且codim（SJ，TJ）≤c。从初始状态T开始的执行，其中不在S中的进程在每一轮都被静默，对于S中的进程来说，看起来与具有较少失败的执行相同，其中静默的进程不参与。公理3.5设k≥l. 对于所有r >0，如果c=codim（S0，S1），Qr Ql（S0）k kk−φ（c）这个等式的右边是处理器的状态集，这些处理器不能分辨初始状态是S0还是S1。能够分辨出差异的处理器必须在第一轮中保持沉默，这需要额外的c次失败，并且必须在剩余的轮中保持沉默，这需要在随后的每一轮中增加φ（c）次失败。最后一个公理说有一个偏序，公理3.6对任何单形S，Ql（S）是吸收偏序集.4定理与引理下面是公理3.4的直接结果。引理4.1设i≥j. 对于所有r >0，如果S≠T，QrQj（S）我其中c = codim（S，T）。i+φ（c）引理4.2设k≥l. 对于所有r >0，如果c=codim（S0，S1），=。k kk−φ（c）证据"因为S0<$S1<$S1，且codim（S0<$S1，S1）≤c，公理3.4意味着Qk−φ（c）Ql−c（S0<$S1）<$$> QrQl（S0）<$，对称地，对于。QM. Herlihy等人/理论计算机科学电子笔记230（2009）7987S ≤⊂≥J∈AJLLL引理4.3如果（，）是一个吸收偏序集，且S，T和TS如定义3.1所定义，则codim（S T，T S T）0。 由于Qr−1Qk（S）<$Qr−1Qm（S）的归纳假设，JL我们有QrQk（S）=QjQr−1Qk（S）<$QjQr−1Qm（S）<$QlQr−1Qm（S）=QrQm（S）。Q引理4.5设（S，≤）是吸收偏序集，T ∈S是关于≤的极大单形. 本文证明了下列集合都是吸收偏序集：（L，≤），其中L={L|L∈ S−{T}}，且（M，≤），其中M={T}。引理4.6设（A，≤）是包含多个单形的吸收偏序集设A∈A是关于≤的极大单形. 对于A中的每个B A，存在一个满足定义3.1的三个条件的AB。我们声称，B={A B<$A|B ∈ A− {A}}是A−{A}中元素的任意全阶的吸收偏序集<88M. Herlihy等人/理论计算机科学电子笔记230（2009）79KKKKKPPP⊆⊆引理4.7如果QrQl（A）中的每个单形的维数至少为d，则A中的每个单形引理4.8设Qr Ql是单纯算子的复合，其中k ≥ l。 如果（S，≤）是吸收偏序集，则对于S中的每两个单形S和T，且T/≤S，存在S中的TS，且TS≤T，使得QrQl（S）k k k kcodim（TS，T）= 1codim（S，T）≤ codim（S，T）.引理4.9如果（A，≤）是一个吸收偏序集，其中l是A中任意单形的最小维数，则A是（l− 1）-连通的。定理4.10设QrQl是单纯算子的复合，其中k≥l，（A，≤）是一个吸收偏序集。 如果QrQl（A）中的每个单形的维数至少为l，则<$Qr Ql（A）<$是（l − 1）-连通的。5同步模型我们假设一个标准的同步消息传递模型与崩溃故障[2，14]。系统有n+1个处理器，在任何给定的执行中，最多有f个处理器会崩溃。每个处理器开始于由其输入值组成的初始状态，并且计算在一系列轮中进行。在每一轮中，每个处理器向其他处理器发送消息，接收该轮中其他处理器发送给它的消息，执行一些内部计算，并改变状态。我们假设处理器遵循全信息协议，这意味着每个处理器在每一轮中将其整个本地状态发送给每个处理器。这是一个标准的假设时，证明下限。处理器可能会在一轮中崩溃而失败，在这种情况下，它只将其状态发送给子集在这一轮的处理器。一旦一个处理器崩溃，它就再也不会发送另一条消息了一个单形X在两个单形T和R之间，如果T XR. 我们使用[T：R] 来表示T和R之间的单形集合。定义5.1给定单形S、T和R，伪球面（S，[T：R]）是S与T和R之间的单形的所有可能标号的集合。我们称这个集合为伪球面，因为诱导复形具有球面的一些拓扑性质。 单形S称为伪球面的基单形，给定伪球面（S，[T：R]）的单形X，我们定义基（X）为S。给定一个单形S和一个处理机集合D，设F=S/D是S的面，它是通过删除D中标记有处理机的顶点而从S得到的。 通过一轮同步计算从S可到达的状态集，其中D中的处理器失败，可以用伪球表示（F，[F：S]），集合F和S之间的单形的F的所有可能标号。M. Herlihy等人/理论计算机科学电子笔记230（2009）7989F≤≥≥SS ≥100S∈ SKK≤KK接下来，我们定义失败操作符。给定一个单形S和一个整数l0，l-失败算子l（S）将S映射到S的所有面F的集合，其中codim（F，S）l是通过从S删除至多l个顶点而获得的所有面的集合。这对在S的一轮计算中可能失败的至多l个处理器的集合进行建模。定义5.2对于每个整数l0，同步轮运算符l（S）定义为：Sl（S）=F∈F<$（S）P（F，[F：S]）。我们现在检查同步轮运算符是否满足我们的公理。引理5.3Sl满足公理3.3：Sl（S）Sm（S）当l≤m.证据由于l≤m意味着Fl（S）<$Fm（S），因此，Sl（S）=F∈F<$（S）P（F，[F：S]）F∈Fm（S）P（F，[F：S]）= Sm（S）。Q在这个模型中，整数值线性函数φ简单地是φ（f）= 0。引理5.4l满足公理3.4：令kl，令ST，其中c = codim（S，T）。对于所有r > 0，对于所有Jrk−φ（c） Sl−c（S），存在TJ∈ SrSl（T）使得SJ<$TJ且codim（SJ，TJ）≤c。引理5.5Sl满足公理3.5：设k≥l。对于所有r >0，如果c=codim（S0，S1），SrSl（S1）SrSl−c（S0。为了证明Sl满足公理3.6，我们在单形上强加了一个偏序S1（S）。 记得Sl（S）=P（F，[F：S]）。F∈F<$（S）这个表达暗示了一种词典顺序。我们将把Fl（S）中单形F的全序与每个P（F，[F：S]）的单形的偏序结合起来我们假设一个完整的顺序处理器id上的id，这会导致单形的顶点。我们首先在S的面F上强加一个字典序全序。首先，我们通过降低维度来对面进行排序，以便大面出现在小面之前。然后，我们根据处理器id上的总顺序，使用相当任意的规则对相同维度的面进行排序：如果90M. Herlihy等人/理论计算机科学电子笔记230（2009）79PPPSK−≤P≤≤[2014-05-23][2014-05-23]S PP≤ S≤S S≤一标记F而不是G中的顶点的最小处理器id位于标记G而不是F的最小处理器id之前。形式上：定义5.6用Fdim（G）或(ii) dim（F）= dim（G）和pF 0，对于所有J rk−φ（c）Al−c（S），存在TJ∈ ArAl（T）使得SJ<$TJ且codim（SJ，TJ）≤c。引理6.4Al满足公理3.5：设k≥l。对于所有r >0，如果c=codim（S0，S1），ArAl（S0）为了证明Al满足公理3.6，我们在单形上加了一个偏序Al（S）。 记得Al（S）=P（S，[F：S]）。F∈F<$（S）如果F J F，则（S，[F J：S]） （S，[F：S]），因此我们可以将注意力限制在余维l的面上。 与同步模型不同，在同步模型中，单纯形具有92M. Herlihy等人/理论计算机科学电子笔记230（2009）79一≤≤≤ A≤A A≤不同的维度，在这个集合中的所有单形都是S的标号，并且都具有维度n。我们在处理器id上使用相同的全阶id，在单形S的面上使用相同的全阶1时，QrQl（A）=Qk（Qr−1Ql（A））。 根据单纯形的定义，算子Qk，Qr-1Ql（A）中的每个单形的维数至少为d，因为Qk（Qr-1Ql（A））中的每个单形的维数为d通过归纳定理，A中的每个单形至少有d维，因为Qr-1Ql（A）中的每个单形都是d。Q94M. Herlihy等人/理论计算机科学电子笔记230（2009）79K/≤S≤S ≤SRk−φ（c−d）- ≤ − ≤−Rk−φ（1）LM引理4.8设QrQl是单纯算子的复合，其中k≥l。若（S，≤）是吸收偏序集，则对S中的任意两个单形S和T，T/≤ S在S中有一个TS，其中TS≤ T，使得QrQl（S）k k k kcodim（TS，T）= 1codim（S，T）≤ codim（S，T）.证据 因为（，）是吸收偏序集，所以对于每两个单形S和T，其中T S，存在TS，其中TS T满足等式1，2和3。根据引理4.2，Qr Ql（T）。K K其中c=codim（S，T）。k−φ（c）设d=codim（ST，TST）.根据引理4.1和φ的线性，Qk−φ（c）Ql−c（ST）QrQl−c+ d（T S<$T）<$.由引理4.3， QrQl（T）<$k−φ（1）k k将这些夹杂物结合起来会产生所需的结果。Q引理4.9如果（A，≤）是一个吸收偏序集，其中l是A中任意单形的最小维数，则A是（l−1）-连通的。证据 假设A包含m个单形。我们用归纳法来论证m。当m= 1，一个维数至少为l的单形是（l − 1）-连通的（定理2.3）。假设m >1，归纳假设对m−1成立。设T是A关于≤的极大元，且设L={S|S∈A −{T}}且M={T}。根据引理4.5，和都是吸收偏序集。 通过构建，每个 少于m个单形，所有这些单形的维数至少为l。从归纳假设可以得出，复形L和M都是（l−1）-连通的我们现在称<$L <$M是（l−2）-连通的。由于（A，≤）是一个吸收偏序集，对于L中的每个L，存在L中的TL，使得L TT LTcodim（T L，T）= 1.RM. Herlihy等人/理论计算机科学电子笔记230（2009）7995KKKKKKKLMKKKKKKKKKKKKK设N={T L<$T|L∈L}。请注意，N= LM。 引理4.6表明N是一个包含少于m个单形的吸收偏序集。通过假设， QrQl（A）中的每个单形至少有l维。因为L<$A，所以QrQl（L）中的每个单形也是如此。通过构造，对于N中的每个单形N，存在单形TS∈L使得codim（N，TS）≤ 1。公理3.4意味着，对于每个单形NJ，QrQl（N），则在QrQl（L）中存在一个单形LJ使得codim（NJ，LJ）≤1.k−φ（1）Jkr特别地，dim（N）≥l−1，所以Qk−φ（1）Ql（N）中的每个单形都有维数至少l-1。m的归纳假设意味着QrQl（N）是（l−1）-连接.k−φ（1）我们已经证明了，<$Lvl和<$Mvl都是（l−1）-连通的，并且<$Lvl <$Mvl是（l−2）连通的，所以<$L <$M是（l−1）-连通的。Q定理4.10设QrQl是单纯算子的复合，其中k≥l，（A，≤）是吸收偏序集. 如果QrQl（