分布式计算中的弱对称破缺问题的归纳式算法研究

−C以前的研究表明，C= 1 +n1i=0n+1ki，对某些系数ntski∈Z. 这种特征化C一期+1可在www.sciencedirect.com在线获取理论计算机科学电子笔记283（2012）13-27www.elsevier.com/locate/entcs一种归纳式的对称单色单形计数方法及其在分布式计算中的应用阿曼多·卡斯塔·恩·埃内达1和塞尔吉奥·R·a·jsbaum2，3InstitutodeMatema'ticasUniversidadNacionalAuto'nomadeM'exi co CiudadUniversitaria，D.F. 04510，M'exico摘要在弱对称破缺（WSB）任务中，n+1个进程中的每一个都必须决定0或1，这样不是所有进程都决定相同的值。WSB算法应该是无等待的，也就是说，进程是异步的（它们的相对速度没有限制），并且可能出错（任何适当的子集都可能没有警告）。此外，它应该是基于比较的，也就是说，进程只能对它们从内存中读取的值使用比较操作（<，>，=）单形的对称色细分已被用来表示分布式解决WSB任务的算法。非正式地，这样的细分的每个单纯形对应于算法的执行。 每个顶点都用执行中的进程的本地状态来标记;它用进程ID，以及进程在执行中决定的二进制值。这种复合物的对称性来自WSB算法的基于比较的要求设C表示单次代数n的个数。 - 通过定向计算的子分区的相似复合体。的意味着n+1个进程上的WSB任务是可解的，当且仅当n使得二项式系数是相对素数，或者等价地，当且仅当n不是素数幂。本文提出了一种归纳式的程序，产生的特征的另一种证明，.粗略地说，证明包括在一个过程中逐渐修改的对称色细分的二元着色，并计算在该过程中产生的地图的程度关键词：分布式计算，弱对称破缺，重命名，组合拓扑。1介绍n+ 1个进程上的任务T由输入复合体I，输出复合体I，O，以及输入-输出关系Δ。 输入复合体指定可能的输入1电子邮件：acastanedar@uxmcc2.iimas.unam.mx2电子邮件：rajsbaum@matem.unam.mx3由墨西哥国立自治大学的PAPIIT和PAPIME项目支助。1571-0661 © 2012 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2012.05.00314A. 卡斯塔涅达湾Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）13−是的。文[4]证明了C= 1 +.- 是的Σn1i=0n+1个 k i，对于某些整数k0，...， kn−1。n+1个 ，...，n +1个1n一期+1to the processes流程. I中的每个单纯形指定过程的输入值。对于每个输入单形，Δ指定一组输出单形，包含允许进程在执行中决定的值。拓扑方法已经在分布式计算中使用，以研究哪些任务可以被解决，以及具有什么复杂性（参见例如[3，9，10，11，12，13]）。粗略地说，在输入单纯形中开始的任务T的分布式算法的执行可以由算法复合体表示。这样一个复合形的每个单纯形对应于算法的一个执行。 一个单纯形的顶点被标记为进程在执行中的局部状态;每个顶点都用一个不同的进程id着色，因此这个复合体被称为色的。由过程决定的值诱导出一个从算法复形到输出复形的单纯映射，该映射遵循Δ给出的规范。使用算法复形的拓扑不变量，可以证明T是不可解的，或者导出求解T的算法。 为 在本文所考虑的无等待模型中，拓扑不变量是算法复形总是导致输入复形的细分。在无等待模型中，进程是异步的（它们的相对速度没有限制），并且可能出错（任何适当的子集都可能在没有警告的情况下停止）。此外，进程使用读/写共享内存相互通信在本文中，我们感兴趣的是弱对称破缺（WSB）任务[8]：n +1个过程中的每个过程在[n] ={0，...，n}，并且在彼此通信之后，进程决定0或1，使得不是所有进程都决定相同的值。WSB任务的算法需要基于比较：进程只能对从内存中读取的值使用比较操作（<，>，回想一下，当M= 2n时，WSB任务等价于著名的M-重命名任务[1]。在这个任务中，每个进程都从一个大的命名空间中获得一个唯一的名称，在相互协调之后，进程从一个大小为M的（小得多的）命名空间中选择唯一的名称。先前的研究[2，5，10，11]已经表明，WSB算法的执行可以表示为n-单形的色细分K，其顶点上的二进制着色在边界上是“对称的二元着色表示进程决定的值，K的单色n-单形对应于所有进程决定相同输出值的执行。设C表示单次多项式的个数。K中的n-s-n-S.这是一个很好的地方。C的中心化对WSB任务的解决方案有影响：如果1n不是互质的，那么就没有整数k0，...， k n−1使得C= 0，这意味着对于n+ 1个进程没有WSB算法。否则，存在WSB算法。 在[6]中观察到n是素数幂当且仅当n+1，.， n+1不是素数。因此，存在WSBn+ 1个进程的算法当且仅当n不是素数幂。文[4]介绍了证明C的特征的两种组合方法。两者都基于索引引理5.2，它是[7]中推论2的重述。一种方法是用一个非常简单的复形代替K的内部，其中单色单形的数量可以计算出来，A. 卡斯塔涅达湾Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）1315注意到这个数不被修改，只要所得复形的边界与K的边界相同，由指数引理。这种方法在[5]中有详细描述。它是在[6]第三种方法，这是代数。粗略地说，它包括，首先，注意到K的着色诱导出一个从K的链复形到n维环的链复形的链映射φ，它与[n]上的对称群等价;然后，利用φ的对称性质，它计算φ的次数，这意味着C的特征。在本文中，我们详细描述了[4]中的另一种方法。我们提出了一个归纳式的程序，产生的特征的另一种证明梭该过程逐渐修改细分的二元着色，确保每次改变一个顶点的二元着色时，边界上其他顶点的二元着色也会改变，以保持二元着色的对称性。证明在于计算这些颜色中的每一种如何改变矢量C。在代数拓扑语言中，证明包括计算由过程中产生的单纯映射引起的链映射的度。本文的其余部分组织如下。第二节简要介绍了一些组合拓扑的概念，第三节介绍了定理中C的特征化的形式陈述中所使用的分像的第6.1条.第4节和第5节包含在第6节定理6.1的证明中使用的一些引理。2组合 拓扑结构我们假设读者熟悉的概念，如（组合）单纯形，（组合）复合，单纯映射和定向。设K是一个n-复形. K的i-图，0≤i≤n，对于K的每一个i-单形都有一个结点，如果两个顶点共享一个（i-1）-面，则它们之间有一条边。我们说K是i-连通的，如果它的i-图是连通的，或者当i= 0时它由一个顶点组成。如果我们说一个n-复形是连通的，我们指的是最高维n，即，复形是n连通的。一个复形Kn是一个n-伪流形，如果它的每个i-单形，i≤n，是至少一个n-单形的面，并且它的每个（n-1）-单形是一个或两个n-单形的面。伪流形Kn的边界bd（Kn）是由包含在一个n-单形中的（n−1）-单形诱导的复形K的着色是从其顶点到一组颜色的函数f。单形τ∈ K的顶点的颜色集合记为f（τ）。K的二元着色是颜色为{0， 1}的着色。一个单形的染色是正常的，如果它给不同的顶点不同的值。如果一个单形的着色给出相同的值，[4]这个定义并不等同于i-连通的通常定义。粗略地说，i-连通的通常定义意味着复形没有16A. 卡斯塔涅达湾Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）13Jb到每个顶点，我们说单形是b-单色的或只是单色的。一个n-复形是色的，如果它有一个使用n+ 1种颜色的着色，并且它的每一个单形都是适当着色的。设σn是一个单形，它有[n]的真染色id那么，d =+1表示包含序列0，1，.的正取向，n，即，顶点的序列是v0，v1，...，v n满足id（v i）= i，0 ≤i≤n，且d = −1表示负定向。如果σn是定向的d，它的（n-1）-面没有颜色i，接收诱导定向（-1）id。一个伪流形Kn是可定向的，如果可以给它的每个n-单形一个定向，使得如果σ，σJ∈Kn共享一个（n− 1）-面τ，则τ从σ和σ得到相反的诱导定向。这样的定向是Kn的相干定向。3分割图像在[2]中引入并研究了分割图像，以模拟与分布式算法相关联的复杂结构。本节简要回顾这些组合拓扑对象的主要性质定义3.1[2，定义4.1]设Kn，Ln是复形，λ是将Ln的每个单形映射到Kn的有限子复形的函数。复Kn是Ln的一个分割像，如果：(1)（(2) <$τ∈Kn，存在单形σ∈Ln使得τ∈<$（σ）(3) <$σ0∈Ln，<$（σ0）是一个单顶点(4)（σ2）(5)<$σ∈Ln，<$（σ）是dim（σ）-伪流形，满足bd（<$（σ））=<$（bd（σ））复Kn是Ln的一个分像，如果存在λ，使得Kn是Ln在λ下的一个分像.图1描绘了一个2维的分割图像，其中L2是由2-单纯形及其所有面组成的复合体，箭头显示了L2的顶点如何映射。值得注意的是，分割的图像不一定是细分，即使它是连接的。例如，一个2维的环面L，其中一个2-单形τ被移除，是一个2-单形σ的分割图像：bd（σ）被映射到bd（τ），σ被映射到L。设 Kn是Ln的一个分像.Kn是连通的，如果对每个i-单形σ∈ Ln，如果i≥1，则<$（σ）是i-连通的，如果i≥2，则bd（<$（σ））是（i−1）-连通的。类似地，Kn是可定向的，如果对每个σ∈Ln，<$（σ）是可定向的。Kn是相干定向的，如果对任意n-单形σ∈Ln，n-伪流形ε（σn）是相干定向的.单形τ∈Kn的载体carr（τ）是最小维数的单形σ∈Ln，使得τ∈L（σ）.假设Ln是色的。单形σ∈Ln的色集记为id（σ）.如果每个单形τ∈Kn，则分割像Kn是色的A. 卡斯塔涅达湾Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）1317K我我Fig. 1. 二维的分割图像。其中dim（τ）=dim（carr（τ）），用id（carr（τ））适当着色。图2描绘了2-单纯形的彩色分割图像设Kn是σn的一个可分像.Kn的一个交叉边是一个1-单形{u，v} ∈bd（Kn）使得存在σ n的不同i-面σ，σj，0 ≤i≤n− 2，满足u∈n（σ），u∈/n（σJ），v∈/n（σ）andv∈n（σJ）. 这意味着，如果Kn没有交叉边，则对于每个σ<$σn，存在v∈<$（σ）使得carr（v）=σ。图1中的粗体边缘是交叉边缘。粗略地说，分割图像的j-角是在边界中具有i -面的j -单形，对于每个i≤j。用小十字标记的2-单形是图1中分割图像的2-角。定义3.2设n是σn在n下的一个分割像，σj是σn。 （σj）的j-角的集合是：j-corners（<$（σ j））={τ j∈ <$（σ j）|<$0 ≤ k ≤ j，<$σ k，ρ k，使得σ k <$σ j，ρ k∈<$（σ k）和ρ0<$ρ1<$. ρj=τj}4关于可定向性的这一节给出了一些关于色分象可定向性的引理。对于本文的其余部分，对于一个用[n]适当着色的单形σn，令σn−1表示σn的没有颜色i∈[n]的（n−1）-面引理的证明4.1很容易，留给读者。引理4.1设Kn是图的色的、连通的、可定向的分割像，σn小于σ n。在K n的任何相干取向中，<$（σ n−1）具有相干诱导的导向引理4.2设Kn是σn的色连通可定向可分像，在σ n下的可分像. 在Kn的任意相干定向中，所有n角单形（Kn）都具有相同的定向.证据考虑面σ1，σ2，...，σ n−1的σ n使得σ1<$σ2<$. σn−1。当1≤i≤n− 1时，设Ki表示复数（σi）。假设Ki具有由Ki+1诱导的取向。根据引理4.1，Ki是相干定向的。我们对n进行归纳。对于基，我们知道K1有奇数个1-单形18A. 卡斯塔涅达湾Rajsbaum/Electronic Notes in Theoretical Computer Science 283（2012）13K我我K−μ因为K1是色的并且是连通的K1的1-角是包含其边界的两个顶点的1-单形不难看出，这些单形具有相同的方向。假设引理对i−1成立。我们证明它对i成立。通过n-角点的定义3.2，包含每个（i-1）-角点的单形（Ki-1）在i-角单形（Ki）中。然而，每一个i-角点的单形（Ki）包含一个（i−1）-角点的单形（Ki−1）并不是必然的设τi−1和ρi−1是（i−1）-角（Ki−1）的单形，τi和ρi是i-角（Ki）的单形，使得ρi−1<$ρi和τi−1<$τi。通过可定向性的定义，τ i将其定向乘以（− 1）k导出为τ i−1，ρ i将其定向乘以（− 1）k导出为ρ i−1，对于某个k。此外，通过归纳假设，（i − 1）-角点（Ki−1）的单形具有相同的方向，因此τ i和ρ i具有相同的方向。 现在考虑σi的面λi−1，使得λi−1/=σi−1。 让Li−1表示复数<$ （λi−1），Li−2 表示复数<$（σi−1<$λi−1）。考虑一个由（i−2）个角点（Li−2）组成的单形γi−2设τi−1∈（i−1）-角点（Ki−1），ρi−1∈（i−1）-角点（Li−1）和τi，ρi∈i-角点（Ki）是单形，使得γ i−2<$τ i−1 <$τ i和γ i−2<$ρ i−1 <$ρ i。 利用Ki是连通的且通过对彩色分割图像的分析，可以证明τ和ρ具有相同的方向。 根据前一个案例，这一个成立。 这就完成了证明。Q对于单形σn，下面设σn表示包含σn的所有面的复形。考虑σ n的色分像Kn在σ n下.设σ和σJ是σn的i-面. 一个单纯双射μ：μ（σ）→μ（σJ）是保id的，如果对每个u，v∈φ（σ），如果id（u）=id（v），则id（μ（u））=id（μ（v））. 此外，对于每u∈k（σ），rk（id（u））=id（μ（u）），其中rk：id（σ）→id（σJ）是双射，使得 如果xy则rk（x）

下载后可阅读完整内容，剩余1页未读，立即下载