图形重标记系统的分布式算法可视化及工具开发

电子笔记在理论计算机科学50第3期（2001年）。GT-VMT 2001网址：http://www.elsevier.nl/locate/entcs/volume50.html11页基于图重标记系统的分布式算法可视化1M. Bauderon，S.Gruner，Y.M etivier，M.Mosbah和A.Sellami2LaBRIUniversit e Bordeaux 1 - ENSEIRB - IUT（法国）我是说，我是说。fr摘要在本文中，我们提出了一个统一的方法来模拟和可视化的分布式算法编码的图形重新标记系统。特别地，我们使用局部重标记规则的分布式应用来自动显示整个分布式算法的结果。我们已经开发了一个Java原型工具，用于实现和可视化分布式算法。我们说明了我们的框架使用各种分布式算法，包括选举和生成树的不同方面。1引言算法的可视化和动画可以帮助设计，调试，验证以及算法的解释[4，3]。特别是，由于进程间通信和同步的复杂性，可视化对于分布式算法可能变得极其重要[19]。 在分布式计算中，事件在多个站点同时发生，每个处理器的状态既取决于其内部操作，也取决于从其他进程接收的消息。显示消息交换和进程当前状态的能力会带来直觉，理解甚至改进分布式算法。有一个重要的教学兴趣与算法可视化，它可以被学生单独使用或在课堂演示[28，33]1 这项工作得到了欧洲TMR研究网络GETGRATS和阿基坦大区委员会的支持。2 第二作者的当前地址是ECS，南安普敦大学（英格兰），sg@ecs.soton.ac.ukc2001年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2GT-VMT 2001 { M. Bauderon等人已经做了大量的工作来将可视化集成到分布式计算的各个阶段算法动画系统的重点，而不是高层次的抽象事件的可视化。分布式算法的动画带来了许多技术挑战。概念框架需要模块化和简化动画设计过程[27]。在这项工作中，我们提出了一种基于局部图变换可视化分布式算法的方法。我们的工作超越了已知的分布式算法的孤立例子的动画。我们表明，一个大类的分布式算法，这可以描述一些图形变换系统，可以自动模拟和可视化。图重新标记系统以及更一般地，图中的局部计算是强大的模型，其提供了用于编码分布式算法、用于证明其正确性以及用于理解其能力的通用工具[14]。我们考虑一个匿名网络的任意拓扑结构的处理器，表示为一个连接的，无向图的顶点表示处理器，和边缘德-笔记直接通信链路。算法通过局部重新标记进行编码。附加到顶点和边的标签被局部修改，即在给定图的固定半径k的子图上，根据仅取决于子图的某些规则（k个局部计算）。执行重新标记，直到不再可能进行转换相应的con-因此，我们说，这是正常的形式。 两个连续的重新标记步骤是如果它们应用于不相交的子图，则称为独立。在这种情况下，它们可以以任何顺序甚至同时应用分布式计算的模型是一个异步的分布式进程网络，这些进程通过交换消息进行通信。为了克服某些非确定性分布式算法的问题以及具有高效和容易的实现，我们使用随机化[6，32，25]。关于随机分布算法的一般考虑可以在[32]以及设计和随机化分析中使用的一些技术。在[23，25，6]中给出了算法M etivier等人[20，21]已经研究了随机算法以实现由本地计算指定的分布式算法。直觉上，每个进程随机尝试与它的一个邻居或所有邻居同步，这取决于我们选择的模型，然后一旦同步，就可以进行本地计算。两个相邻点之间的同步称为同步，一个顶点与其所有相邻点之间的同步称为星同步。在[20，21]中给出并讨论了实现同步的过程我们使用这些技术来可视化分布式算法的执行。将显示整个网络中的所有随机本地同步，还将显示在这些同步期间交换的消息。因此，执行整个算法的可视化直到终止。我们开发了一个具有交互式视觉的原型工具，3GT-VMT 2001 { M. Bauderon等人图形编辑器来构建网络，以及一个接口来实现和可视化分布式算法。本文的结构如下。第2节介绍了图重新标记系统，以及它们用于描述分布式算法。 第3节提出了一种方法来模拟和可视化的分布式算法编码的图形重新标记系统。第4节介绍了未来的工作，并总结了本文。2图形重标记系统我们考虑的所有图都是有限的、无向的、简单的和连通的。一个图G是一个对（V（G）; E（G）），其中V（G）是顶点的集合，E（G）ffv;v0g j v;v0 2V（G）;v0 6 =v g是边的集合。 主要内容可参见[26]。一个L标号图是指其顶点和边用一个可能的有限字母表L中的标号标号的图。它将被表示为（G;），其中G是图并且：V（G）[E（G）！ L是标记函数。图G称为（G;）的基础图，是G的一个标号. L标号图类记为yGL，如果L的α b从上下文中是清楚的，则记为G。设（G1）和（G0;0）是两个标号图，（G1）是（G0;0）的一个子图，记为y（G1）（G0;0），如果G是G0的一个子图 并且是0到V（G）[E（G）]的限制。A映射：V（G）[E（G）！V（G0）[E（G0）]是f（G1）到（G0;0）的同态，若'是G到G0的同态 其中存在标号，即对于每一个x2V（G）[E（G）]，0（x（G））=（x）成立。（G1）在（G 0 ; 0）中的一条边是（G1）与（G0;0）的某个子图（H1）之间的同构.本文仅举一个例子，并回忆了图的几个定义重新标记系统。关于这些系统的详细结果和各种类型，读者应参见[11，12，15，13，14]。示例：生成树假设所有顶点最初都处于某种中性状态（由标签N编码），只有一个顶点处于活动状态（由标签A编码），并且所有边都具有标签0。在计算的每一步，A标记的顶点u可以激活它的任何中立邻居，比如v。在这种情况下，u保持其标号，v成为A-标号的，而边fu; v g成为1-标号的。因此，多个顶点可以同时是活动的。如果两个步骤涉及不同的顶点，则允许并行步骤。一旦所有顶点都被激活，计算就会停止。生成树由1-标号边给出.410011110101A N AA01GT-VMT 2001 { M. Bauderon等人该 算 法 是 由 图 关 系 标 注 系 统 R1 实 现 的= （ L1;I1;P1 ） 定 义 为L1=fN;A;0;1 g，I1=fN;A;0 g，且P1=fR g，其中R是以下重新标记规则：R：0图1描述了使用该算法的示例计算。根据前面的讨论，读者应该记住，某些重新标记步骤可能会同时应用。无0 0无0 0无0 0A N0 0N NA0N1 0A A0 1N AAA0 0NNA0N1 0AA0 1AAA A0 1N AA0A1 1A A0 1A A图1.一、生成树的分布式计算请注意，其他重标记系统，具有不同的行为方面的终止，可以用来生成生成树（见[13，2]）。图重新标记系统和更一般的本地计算满足以下约束，这些约束在描述具有分散控制的分布式计算时似乎是自然的（C1）它们不改变底层图，而只是改变其组件（边和/或顶点）的标记，最终标记是计算的结果，（C2）它们是局部的，即每个重标记步骤只改变底层图中固定大小的连通子图，（C3）它们是局部生成的，即重标号的应用条件仅取决于重标号子图的局部上下文.对于这样的系统，分布式方面来自于这样一个事实，即几个重新标记步骤可以同时在“足够远”的子图上执行，以任何顺序给出与它们的顺序实现相同的结果图重新标记系统由标签的集合L（在重新标记的图中使用的标签）、初始标签的集合L（开始重新标记过程的每个图仅具有I中的标签）和重新标记规则的集合来定义;它可以配备有本地控制重新标记规则的应用的机制，例如，优先级禁止的上下文重新标记规则r50GT-VMT 2001 { M. Bauderon等人包括重新标记一个 固定连通子图Gr ：r：（Gr;）！（Gr; ）设一个标号图（G;l）与（G;l0）是相关的，如果存在一个允许的从（G; 1）到（G;10）的重新标记的应用的序列。在经典的分布式算法中，可以通过图重新标记系统进行编码，我们回顾以下内容[2]：具有全局终止的局部检测的生成树的分布式计算[13]在树和完全图中的选举[15]Mazurkiewicz的通用图重建算法[17]稳定性质的检测（Szymanski，Shi和Prywes [30]）。3分布式算法考虑一个表示网络的图，其中节点对应于处理器，边对应于通信信道。分布式算法的可视化包括显示和动画其执行。处理器之间交换的数据，以及处理器和通道的状态和标签更新都显示在屏幕上的y上。当然，其他有趣的事件取决于算法本身。例如，为了确定生成树，重要的是标记属于生成树的边。在我们的方法中，动画的分布式算法的任务主要依赖于一种类型的本地计算的选择，并重新标记系统的设计前者定义了由重新标记系统的规则执行的本地计算的模型。3.1本地计算在[20，21]中研究了三种类型的局部计算。在异步消息传递系统中实现这些局部为了可视化的目的，这种随机化的实现是有用的，因为它使最终用户能够观察算法的整个执行过程。这些本地计算是：Rendezvous（RV）：在计算步骤中，附加到K2的顶点的标签（2个顶点的完全图）的随机化过程：为了实现RV，我们考虑下面的分布式随机化过程。该实现被划分为轮;在每轮中，每个顶点v随机选择其邻居c（v如果c（v）=v，则v和c（v）之间存在会合;我们说v和c（v）是同步的。当v和c（v）为6GT-VMT 2001 { M. Bauderon等人synchronized有一个v和c（v）的消息交换：这个交换允许两个节点改变它们的标签。局 部计算1（LC1）：在计算步骤中，根据取决于星的标签的一些规则修改附接到星的中心的标签，不修改叶的标签。LC1的实施是以下随机的地方选举。它被划分成多个轮，并且在每个轮中，每个处理器v从集合f1中随机选择整数rand（v）;Ng：处理器v向其邻居b发送值rand（v）：顶点v在以d为中心的星形中被选择，并且表示为Sv;如果对于Sv的每个叶w：rand（v）> rand（w）：在这种情况下，允许Sv上的计算步骤：中心收集叶的标签，然后改变其标签。局 部计算2（LC2）：在计算步骤中，可以根据取决于星的标签的一些规则来修改附接到星的中心和叶的标签。LC2的实施是以下随机的地方选举。 它被划分成若干轮，并且在每一轮中，每个处理器v从集合f1中随机地选择一个整数rand（v）;：;NG：处理器v向其邻居发送值r和（v）：当它从每个邻居接收到一个整数时，它向每个邻居w发送它从不同于w的邻居接收到的整数集合的最大值：如果对于以半径为2的v为中心的球的任何顶点w，rand（v）严格大于rand（w），则选择星Sv的顶点v中心;在这种情况下，可以在Sv上进行计算步骤：在该计算步骤期间，Sv的节点进行标签的总交换;该交换允许Sv的节点改变它们的标签。3.2实施重新标签制度我们将通过同步来参考先前类型的本地计算。现在，我们将展示如何结合同步和重新标记规则，以这种方式，重新标记系统可以在网络上随机应用。每个处理器都试图与它的一个邻居或所有邻居同步，这取决于上面讨论的本地计算的类型。一旦处理器v参与同步，就可以执行重写步骤。也就是说，v与它的邻居交换标签和属性，检查是否找到其中一个规则的左侧（w.r.t同构），如果是，则根据规则的右侧更新它的标签和属性。然后，同步被中断，并且v和它的邻居可以自由地重试新的同步。请注意，我们所有示例所需的重新标记规则要么是K2 规则或明星规则。3.3ViSiDiA：分布式算法我们已经开发了一个名为ViSiDiA的原型工具[1，2]，以帮助实现和可视化如上所述的重新标记系统正如先知以赛亚书上记7GT-VMT 2001 { M. Bauderon等人Java语言，处理器由Java线程模拟为了对重新标记系统进行编程，高级原语库允许用户实现本地计算。特别地，提供了实现先前同步的三个函数（renaltVous（）、starSyn-chro 1（）和starSynchro 2（））。此外，处理器之间的通信可以用sendTo（neighbor，message）和receiveFrom（neighbor）等原语来表示。一个说明性的示例显示了第2节中要使重新贴标系统可视化，最终用户必须 首先创建一个图形模式-算法1生成树public void run（）{neighbor= renewalVous（）; sendTo（neighbor，myLabel）;neighbor Label =receiveFrom（neighbor）;if（myLabel=='N'）（neighborLabel=='A'）{myLabel='A';边[邻居]=1}return（）;}在网络上。为此，我们的工具具有友好的图形用户界面，可以使用鼠标按钮构建任意图形（见图2（a））。节点的可视属性（标签、颜色、形状）可以由用户自定义。控制面板允许用户播放动画，在执行过程中的任何点暂停动画，并停止动画。用户还可以选择一个节点并将其标签设置为A。例如，节点5的标签是A。要开始动画，用户按下开始按钮。在这种情况下，ViSiDiA会自动为每个顶点创建一个线程。图2（b）示出了在动画期间网络的状态。在该快照中，节点4和7具有同步。应用了重新标记系统规则的所有边都属于生成树。最后，图2（c）示出了所得到的生成树。在[13]中证明了这个重新标记系统的正确性。许多分布式算法已经实现，可以直接动画[2]。这些包括以下内容树、弦图和完全图中的领导选举，随机选举和随机地方选举，生成树，Mazurkiewicz的泛图重构，稳定性能检测我们的方法的一个有趣的优点是，我们只需要实现8GT-VMT 2001 { M. Bauderon等人(a) 执行前的初始步骤（b）执行(c)执行结果图二. 生成树计算的可视化本地重新标记来编码复杂的分布式算法。因此，可视化这些算法的执行包括动画分布式本地计算。此外，我们的实现保留了重新标记系统的属性，如正确性和终止。9GT-VMT 2001 { M. Bauderon等人4结论在本文中，我们简要地介绍了我们的工作现状的可视化的分布式算法的基础上图重标记系统。我们认为图变换对于简化和以统一有效的方式描述分布式应用程序是有用的[8，22，31]。然而，我们的工具还需要改进，特别是在处理大型图和真实网络方面。该工具的部分正在开发中，目标是提供更直观的交互和显示。我们已经使用我们的工具进行了许多实验，用于分析几种分布式算法[1，2]。我们认为，我们的工具是有用的教学目的，解释分布式算法的执行，也为研究人员在分布式算法谁需要工具进行测试和实验。引用[1] M. Bauderon，S. Gruner和M. Mosbah：一个新的分布式算法仿真和可视化工具。LaBRI报告1245-00，波尔多第一大学，2000年10月（2001年5月21日至23日在图卢兹举行的2001年多边基金会会议上[2] M. Bauderon，Y.M etivier，M.Mosbah和A.Sellami：从本地计算到异步消息传递系统。LaBRI报告，波尔多第一大学准备中[3] M.布朗 Zeus：一个算法动画和多视图编辑系统。《视觉语言学报》，第4 -9页，1991年10月[4] M. 布朗 算法动画。 MIT Press，1988[5] H. Ehrig，H.-J. Kreowski，U.Montanari和G.Rozenberg（编辑）：并发、并行和分布|图文法和计算的图形变换手册，第3卷。 世界科学出版社新加坡1999年[6] R.古普塔河A. Smolka和S. Bhaskar序贯和分布式算法中的随机化。 ACM计算苏尔，26（1）：7{86，1994.[7] M.T. Heath，AD. Malony和D.R.流浪者并行性能数据的可视化显示。 IEEE计算机，28（11），21（28，1995.[8] D.詹森斯 演员语法和本地动作。 第二章，第57 -106页[5][9] J. Joyce，G. Lomow，K. Slind和B.昂格尔分布式系统的监视计算机系统学报，5（2）：121{150，1987。[10] M.洛舍尔高级规范语言CSP（LP）的设计与实现PADL'01会议录，LNCS，Springer-Verlag Berlin 2001[11] I. Litovsky和Y.我的天用优先级图重写系统计算树。树自动机和语言，第115页{139，1992。10GT-VMT 2001 { M. Bauderon等人[12] I. Litovsky和Y.我的天使用具有优先级的图重写系统计算。理论计算。Sci. ，115：191{224，1993.[13] I. Litovsky，Y. M etivier和E.索佩纳图形重新标记系统的不同本地控制。数学系统 理论，28：41{65，1995.[14] I. Litovsky，Y. M etivier和E.索佩纳图形重新标记系统和分布式算法。In H.Ehrig，H.J. Kreowski，U.蒙塔纳里，G. Rozenberg，编辑，Handbook of graph grammars and computing by graphtransformation，第3卷，第1页{56。World Scienti c，1999.[15] I. Litovsky，Y. M etivier和W. Zielonka。关于具有局部计算的图族的识别。信息与计算，118（1）：110{ 119，1995。[16] N.林奇分布式计算的一百个不可能性证明。在第八届分布式计算系统国际会议上，第1页，1989年。[17] A.马祖基维奇分布式枚举。Inf. Processing Letters，61：233{ 239，1997.[18] C.E. McDowell和D.P Helmbold。并行程序。ACM计算 调查员：2 1 （4）：593{622，1989.[19] A. Mester和H.克鲁姆协议和分布式系统的动画。Journal of ComputerScience Education，10（3）：243{265，2000.[20] Y. M etivier，N. Saheb和A.泽马里随机集合在数学和计算机科学：算法，树，组合数学和概率，数学趋势，第183页{194，2000年。[21] Y. M etivier，N. Saheb和A.泽马里随机地方选举：概率与效率分析。技术报告，LaBRI，波尔多大学1。[22] 联 合 蒙 塔 纳 里 湾 Pistore 和 F. Rossi ： Modeling Concurrent ， Mobile andCoordinated Systems via Graph Transformation.第四章，第189 -268页[5][23] R. Motwani和P. Raghavan。随机算法。剑桥大学出版社，1995年。[24] C.M. Pancake 和 S. 完 了 并 行 调 试 器 中 的 模 型 。 Proceedings ofSupercomputing'89，627{636，1989.[25] J. Ramirez-Alfonsin，M.哈比卜角McDiarmid和B.里德，编辑们离散数学的概率方法Springer-Verlag，1998.[26] K.H.罗森编辑离散与组合数学手册。CRC Press，2000.[27] J.T. 斯塔斯科路径转换范例：一种向程序接口添加动画的实用方法J. ofVisual Languages and Computing，1（3）：213{236，1990.11GT-VMT 2001 { M. Bauderon等人[28] J.T. Stasko，A.Badre和C.刘易斯. 算法动画是否有助于学习？实证研究与分析。在Proc. ACM Conf. Human Factors in ComputingSystems，pages 61{66，1993.[29] J.T. Stasko和E.克雷默并行系统的可视化|概述。 并行与分布式计算学报，第18卷第2期，105 - 117页，1993年[30] B. Szymanski，Y. Shi和N.普赖斯分布式消息传递系统中联立方程的终止迭代解。在第四届分布式计算系统国际会议上，第287{292}页，1985。[31] G.坦策岛菲舍尔，M。Koch和V.Volle：分布式图形转换及其在分布式系统可视化设计中的应用第五章，第269 -340页[5]。[32] G.电话分布式算法简介。剑桥大学出版社，2000年。[33] A.凡·达姆电子教室：教学工作站。人机研究国际期刊？2 1 （4）：353{363，1984.