图的局部对称性和半局部模型：匿名图中选举问题的解决方案

理论计算机科学电子笔记154（2006）113-120www.elsevier.com/locate/entcs图的局部对称破缺正在进行的工作Dobieslaw Wroblewski多比斯瓦夫·弗罗布莱夫斯基1，2波兰科学波兰华沙摘要我们考虑有限连通无向图作为计算机网络的一个模型图的节点表示计算机或处理器，而图的边对应于它们之间的链接我们提出了一个分布式计算模型，称为半本地。这种经典局部模型的扩展打破了局部对称性。因此，许多有用的任务在每个网络中变得确定性地可解决，假设关于其图表示的初始知识非常少这些任务之一是在任意匿名环中创建令牌-选举领导者的示例。提出了一个半局部的解决方案，这个问题关键词：变换和改进，验证和分析，局部计算，图重新标记系统，选举，匿名图，环，令牌环网络。1介绍、相关工作有限连通标号图是计算机网络的自然模型它的节点代表计算机或处理器，它的边代表通信链路，它的标签代表网络状态。标号图称为匿名图，如果它的标号是一致的。图标号的一系列变换是网络中计算的模型1作者感谢科学研究和信息技术部2004-2005年3 T11 C 006 27号拨款2Ema il：wrobldob@wars.i pi pan. w aw. pl1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.03.036114D. 《理论计算机科学中的电子笔记》154（2006）113在无向图中提出了不同的分布式计算模型（[1，2，3，6]）。它们被称为局部计算模型。在这些模型中，[3]中提出的模型具有最大的计算能力我们将[3]中提出的模型称为（经典）局部模型。某些任务在此模型中无法解决最重要的例子是任意结构的匿名图中的选举问题[3]。局部模型的弱点来自某些类型的匿名图的对称性。这样的图是局部不可区分的，从其他的，而不是同构的。半局部计算模型是打破局部对称性的经典局部模型的最不为人所知的扩展因此，所有可用全局方法求解的问题也是半局部可解的[5]。 这包括选举问题。在文献[5]中，我们给出了一个任意未知大小和结构的匿名图的半局部选举协议。该协议的主要缺点是其定义的复杂性。在本文中，我们提出了另一个实际应用相同的想法：一个半本地的解决方案，以创建一个独特的令牌在任意大小的匿名环的著名问题这个问题是选举任务的一个例子，并被证明是局部可解的，只有环的先验已知的素数大小[4]。虽然[5]中提出的算法可以在没有任何修改的情况下应用于这种情况，但我们决定通过应用通用协议中使用的一般思想来定义一个新的环优化新的协议是非常简单和可读的，当被定义为一个重新标记系统。反过来，[5]中提出的协议以不同的形式主义定义，并且仅在重新标记系统方面被证明是可定义的（由于其预期的复杂性和可读性，实际定义被跳过在定义协议之前，我们简要介绍了半局部模型，并将其与经典的局部模型进行了比较。标准的数学符号在整个文件中使用假定读者熟悉图论的基本概念按照惯例，我们使用粗体字体来表示标记图。本文的组织结构如下。第2节介绍了半局部计算模型。第3节定义了环的半本地令牌创建最后得出结论，并对算法的复杂性进行了讨论，对进一步的研究进行了展望。D. 《理论计算机科学中的电子笔记》154（2006）1131152局部性与半局部性图变换被表示为标记图集合中的二元关系我们说一个变换T是一个重标号，如果它只改变标号，即对于所有的（G，GJ）∈T，G和GJ的基础图等于3。我们说，对于所有的（G，GJ）∈T，重标号T在Hi ∈ H i中是局部的，使得H是G的一个子图：(a) 标签在H之外不会改变，并且(b) 这种变化不依赖于H以外的图的结构或标号。H称为T的定域。注意，如果T在H中是局部的，那么它在每个HJ中也是局部的，使得H<$HJ<$G。T的最小局部区域表示为reg（T）。分布式计算是由局部重新标记的序列建模的然而，局部区域不相交的重新标记可以同时应用在经典的局部模型中，要求在每一个关系序列中，所有的变换都是半径为1 ~4的球中的局部变换，即子图由一些节点与它的邻居（见图）。①的人。更正式地说，在经典的局部模型中，对于每个序列的标记图（ G1，G2，. ），使得对于每个i∈N（Gi，Gi+1）∈Ti（其中Ti是重新标记），对于所有j∈N，我们有：reg（Tj）<$B（vj），其中v j是G j的节点。Fig. 1.在本地模型中连续两次重新标记。局部区域用灰色背景表示，其中心用箭头指示。[3]平等的要求（不仅仅是同构）有其实际的解释。底层图对网络进行建模，网络的物理结构在其逻辑状态改变后保持不变[4]更一般地，在某些先验选择的半径k∈N的球中（k-局部模型）。116D. 《理论计算机科学中的电子笔记》154（2006）113在半本地模型中，我们采用了分布式协议可能在每一步中收集有关网络的结构知识的事实（在本地模型中被忽略）。也就是说，如果协议的某个步骤是以某个节点v为中心的球B（v）中的局部变换，则我们假设该结构B（v）的定义。 现在，取任意节点w∈B（v）。在本地模型中，下一个变换（协议的下一个步骤）可能在B（w）中是局部的。然而，这意味着，尽管事实上w∈B（v），先前收集的关于B（v）的结构的知识将被忽略。为什么不使用B（v）→B（w）作为新的局部区域？因此，在半局部模型中，我们允许在每一个序列的rela- bellings，每个变换是局部的一些球的半径为15，或在一些连接的子图，这是一个总和，这样的球和一些局部区域中使用的前面的变换（见图1）。2）的情况。更正式地说，在半局部模型中，对于每个序列的标记图（ G1 ，G2，. ），使得对于每个i∈N（Gi，Gi+1）∈Ti（其中Ti是重新标记），对于所有j∈N，我们有：reg（Tj）<$B（vj），或reg（T j）是[reg（T1）]的连通子图. reg（T j−1）]其中v j是G j的节点。图二.在半局部模型中连续两次重新标记（比较图1）。①的人。这意味着初始局部区域是半径为1的球，然后它们可以使用局部方法（通过添加半径为1的球）进行生长因此，半局部过程仍然符合局部计算的直观含义，但它能够解决所有可用全局方法解决的任务下一节提供了一个代表性的例子。3环中令牌的半本地创建最简单的对称网络架构可以用环来建模我们假设左（右（v））=右（左（v））=5更一般地说，一个事先选定半径为k∈N的球（k-半局部模型）。D. 《理论计算机科学中的电子笔记》154（2006）113117v对于每个节点v6.我们的任务是定义一个半局部协议，它从一个匿名环开始，并将其初始的统一标记转换为这样一个标记，其中只有一个节点的标记与其他节点不同此节点将被赋予令牌。这样的任务是领导者选举的典型例子，结果标签打破了最初的对称性。我们的协议的想法很简单。设群是环的连通子图.协议的全局状态是一组用非零自然数编号的组。每个节点最多可以属于两个组，它可以是它所属的任何组的左边界、内部或右边界 如果一个节点不属于任何组，我们称之为自由节点。最初，组的集合是空的，因此每个节点都是自由的。 在后续步骤中，创造者，创造者。边界节点）或合并（当两个不同的组具有相同的边界时节点）。每个创建、扩展或合并的产品都以这样的方式进行编号，即任何两个偶发事件组都具有不同的编号。经过一系列的扩展和合并，所有节点都属于同一个组，并且只有一个节点是它的左边框和右边框。此节点被选中并获取令牌。设R是任意有限环。R是固定的，直到第3节结束。R的节点集节点的局部状态由标记函数l，i，r：V→N和t：V→ {0，1}描述，其中对于每个v∈V：• l（v）/i（v）/r（v）/左边框，分别为7;对于自由节点，它们都为0;最初为0，• t（v）标号图（R，l，i，r，t）记为R，初始标号是匿名的.设v∈V. 协议转换列表如下。 符号l、i、r、t表示变换之前的标记，而带撇号的符号lJ、iJ、rJ、tJ表示其结果。• 如果一个节点v是自由的，设w=left（v），x=right（v）。 从w，v，x创建一个新组，即：[6]这个全局假设简化了我们的算法。然而，它可以很容易地避免：算法的定义将大约长两倍。7请注意，符号l（v）对应于文本 直觉告诉我，L（v）表示从v向左（即，在v的左邻居所指的方向上）跨越的组的编号。这意味着v是编号为l（v）的组的右边界。对于符号r（v），情况是对称的。118D. 《理论计算机科学中的电子笔记》154（2006）113l（v）=i（v）=r（v）= 0gmax =max（l（w），r（x））rJ（w）=iJ（v）=lJ（x）= 1 +gmax（见图1）。3a）。• 如果节点v是某个群G的左边界，而不是任何其他群8的右边界，则令w=left（v），令x是群G的另一个边界节点。G. 群G被w扩张，即：l（v）=i（v）= 0<$r（v）>0<$gmax =max（l（w），r（v），r（x））<$rJ（w）=iJ（v）=lJ（x）= 1 +gmaxrJ（v）= 0y ∈ G − {v，x} iJ（y）= 1 + gmax（见图10）。3b）。• 如果一个节点v是某个群G的右边界，左边界是另一个群H，则设w是G的另一个边界节点，x是H的另一个边界节点。G和H组合并，即：l（v）>0i（v）=0r（v）>0gmax =max（l（w），l（v），r（v），r（x））rJ（w）=iJ（v）=lJ（x）= 1 +gmaxlJ（v）=rJ（v）= 0y∈（G<$H）− {w，v，x}iJ（y）= 1 +gmax（见图10）。3c）。• 如果一个节点v是同一个群G的右边界和左边界，并且它还没有一个令牌，那么它被赋予令牌，即：t（v）= 0l（v）>0i（v）=0r（v）>0l（v）=r（v）tJ（v）= 1。图三.例如a）创建，b）扩展和c）合并组。这些组用灰色背景表示，它们的编号放在附近。定义的协议的完整运行的示例如图所示。4图四、算法运行的一个例子接收令牌的选定节点以黑色背景指示。8 v是右边界而不是左边界的情况是对称的。D. 《理论计算机科学中的电子笔记》154（2006）113119本文的范围不允许详细讨论定义的协议的属性。相反，我们以下面定理的形式定理3.1所定义的协议是半局部的，并且在R中创建一个唯一的令牌，|V|转变证据该协议是半本地的，因为每个转换都是本地重新标记，• 在以自由节点为中心的半径为1的球中，或• 在一个组中，半径为1的球以一个节点为中心求和，该节点是该组的左边界，而不是任何其他组的右边界，或者• 在两个不同的组中，其交点是第一组的右边界和第二组的左边界的节点，或者• 在同一组的右边界和左边界的单个节点中，并且每个组是在某些先前变换中使用的局部区域每一次试验都使用|V|转型，因为：• 每个变换都需要节点v，使得i（v）= 0和t（v）= 0;在变换之后，这些标签之一变为非零值，但仅对于v• 只要存在使得i（v）= 0且t（v）= 0的节点v，就可以执行变换，在初始构形中，对所有v∈V，i（v）= 0，t（v）= 0.由协议的变换创建的所有组如果相交则被赋予因此，如果对于某个节点v，我们有l（v）=r（v）>0，那么v是同一个群的右边界和左边界这意味着组包含环的所有节点，因此对于所有节点w因此只有V可以被给予令牌。我们有i（w）>0，另一方面，随后的变换增加了i（w）>0的节点w与此同时，适当的群体是创建、扩展或合并。 只要对所有的w v，i（w）>0，节点属于同一组。这意味着v将被给予令牌。Q120D. 《理论计算机科学中的电子笔记》154（2006）1134结论计算的半局部模型使得几个有用的任务在不使用全局变换并且利用关于对网络建模的图的非常少的知识的情况下确定地可解提出了一个代表性问题的解决办法未来的工作将包括详细讨论定义的协议的属性，包括其复杂性测量为单个标签的实际变化的数量我们目前估计它是O（|V |2）的情况。然而，我们的主要重点是定义一个自稳定版本的protocol。我们相信环的协议是一个很好的起点，因为它远没有[5]中定义的通用协议复杂另一方面，我们希望实现环的自稳定将很容易推广到普遍的情况。引用[1] Angluin，D.，处理机网络中的局部和全局性质，第12届计算理论研讨会论文集（1980），第82[2] 查洛平，J。、Y.我也是。Zielonka，Election，naminganddcellularedgelocalcomputations，Proc. of ICGT[3] Go d ard，E. ，和Y. M'etivier，Acharacterizationofamilliesofgraphsinwhichhicelectionispossible，LNCS2303（2002），159-171.[4] Mazurkiewicz，A.，异步排序问题的可解性，信息处理快报28/5（1988），221[5] 我很高兴，D。，UniversalSemi-localElectionProcolUsingForwarLinks，FundamentaInformaticae67/1-3（2005），287-301.[6] Yamashita M.，和T. Kameda，Computing on anonymous networks：Part I - Characterizingthe solvable cases，IEEE Transactions on Parallel and Distributed Systems7/1（1996）69