理论计算机科学电子笔记180（2007）21-40www.elsevier.com/locate/entcs分布式协议的原型平台1AlbertoBaragatti，RobertoBruni，Hern'anMelgratti，Ugo Montanari and GiorgioSpagnoloDipartimentodiInformatica，Universita`diPisa，I-56127Pis a，Italy，{baragatt，bruni，melgratt，ugo，spagnolo}@di.unipi. It摘要我们提出了一个原型应用程序，用于协调分布式协议在多方谈判中，参与者可以动态地加入正在进行的谈判，参与者只知道他们互动的那些政党。我们的原型是专为Ad Hoc网络的情况下，涉及分配任务的救援队在灾区工作。我们的应用程序是基于异步通信，它利用D2PC协议来提交或中止协商。缔约在Jocaml+Perl和Polyphonic C中开发。提交协议的实现允许两种类型的组件参与同一协商。保留字：多路交易，分布式谈判，分布式2PC，Jocaml，Polyphonic C1引言当开发分布式应用程序时，特别是当组合独立的异构组件时，协议的编排成为一个典型的问题。因此，处理分布式协商的模式和框架变得至关重要[8]。在本文中，我们介绍了一种编排协议的方法作为一个运行的案例研究，我们认为一个典型的情况下，移动自组织网络（MANET），即代理移动性与动态基础设施和网络拓扑共存的网络。MANET是用于小型移动单元及其基础设施（紧急小组、医疗1.在IS-MANET项目（困难环境中移动Ad-Hoc网络的软件基础设施）框架内由意大利MIUR1571-0661 © 2007 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.10.04422A. Baragatti等人/理论计算机科学电子笔记180（2007）21团队、安全单位、新闻和信息组、高科技研究和商务会议），许多当地代理商都参与其中（笔记本电脑、PDA和最新一代移动电话）。我们的案例研究考虑了一个由一个中心基地和几个团队组成的救援单位，每个团队都有一个领导者和几个操作员。粗略地说，这个想法是在交换了几条消息之后，每个成员可以决定在任务中提交她/他的协商参与，或者在分配的活动无法执行时中止协商。请注意，团队成员通常对任务中的其他参与者了解有限，即，他们只知道他们已经（通过发送或接收消息）交互的那些成员为了以完全分布式的方式实现这种协议，我们依赖于[3]中提出的分布式两阶段提交协议（D2PC）D2PC在Join演算[7]中通过利用其主要特性，即异步通信，进程的响应描述，新名称的创建和名称移动性而被指定。因此，D2PC可以用任何实现Join特性的编程语言直接进行编码，例如Jocaml[6]或Polyphonic C[1]。我们的原型实现利用了这两种语言，并允许在运行Jocaml和Perl代码的Linux组件和用Polyphonic C编写的.Net组件之间协调协议。由于不同的参与方通过TCP套接字进行通信，因此两种类型的组件都可以参与相同的协商。运行Jocaml和Perl代码的组件分为三层。底层托管分布式事务管理器，它是用Jocaml编写的。另外两个层（GUI和coordinator）是用Perl编写的，因为它对于开发原型来说很简单。用Polyphonic C编写的组件遵循面向对象的范式：类d2pc的实例负责执行提交协议。在这两种情况下，应用程序级别的程序只负责跟踪相关方并启动协议协议。提交协议的执行对应用程序级（因此对团队成员）是透明的，它由Jocaml和Perl实现中的两个较低层或Polyphonic C中的d2pc类处理。这将应用程序级从协议的编排中抽象出来，使协商机制可重用于开发新的应用程序。论文的结构第2节给出了一个描述救援队活动分配的原始案例研究。编排协议的机制在§ 3中介绍，而D2 PC在§ 3.1中总结。我们的原型实现的架构和功能在§ 4中详细介绍。2场景本节介绍了一个典型的场景，该场景需要在多个参与方之间协调分布式协议。A. Baragatti等人/理论计算机科学电子笔记180（2007）2123图1. 救援单位的逻辑结构。该场景在[9]的更一般的上下文中，并考虑以分层方式构建的救援团队（如图1所示），其中不同的节点对应于不同的计算和通信能力。注意，图1中的树不是通信图。我们将从路由机制中抽象出来，并假设任何团队成员都可以向任何其他可到达的成员发送消息。 该应用程序的主要目标是提供一个在地面行动期间支持救援单位协调的一套功能。救援单位分为几个救援小组，并从能够通过卫星或蜂窝电话与有线网络进行通信的基地进行协调。此外，基地可以与在该地区工作的不同救援队进行通信（即，通过使用802.11设备）。任何救援队都有一名负责协调救援队的队长，包括：五个运营商。如果需要的话，团队领导者也可以充当操作员，但是他们有不同的计算能力：领导者有笔记本电脑，而操作员有PDA。此外，所有操作员都配备了地理参照系统装置，向基地提供关于其位置的任务的分配是以自上而下的方式组织起来的。也就是说，基地通过向团队领导者发送消息来将一般活动分配给不同的团队。领导者将依次将任务分解并分配给团队操作员。显然，在不同的情况下，活动的分配可能需要所有相关成员之间达成协议。请注意，协议不能单方面建立，提交需要所有参与者的共识。下面描述的场景考虑了由四个小组组成的救援单位，它们覆盖雪崩发生区域的不同连续区域（如图2所示）。 此场景指定Base如何尝试将活动分配给团队T1。2.1场景：活动正常流量：(i) 当基地向团队T1的领导者11发送消息时，场景开始，该消息通知需要在位于团队T1和T2覆盖的区域之间的区域中寻找气体泄漏。(ii) 在接收到请求之后，领导l1决定将需要两个操作员来覆盖整个区域。24A. Baragatti等人/理论计算机科学电子笔记180（2007）21图2. 分布在灾区的救援队。(iii) 因此，领导者11从T1中选择更接近受危害区域的三个操作员，希望他们中的至少两个将能够执行任务，并向他们发送消息，要求他们执行新任务的可用性之后，l1等待接线员(iv) 接收到请求的任何操作员将通过询问她/他的可用性或通过拒绝任务来应答消息。经营者在拒绝请求时承诺参与谈判，因为他们对协议的结果（请注意，拒绝不是中止）。(v) 当l1收到来自三个运算符的答案时，会发生以下情况之一：(a) 所有的操作员都回答了问题。在这种情况下，l1选择其中两个，并向它们发送执行活动的详细指令。此外，l1将决定传达给被排除的操作员。此外，l1向基地确认活动的成功分配并提交协商。(b) 两名接线员已表示愿意提供帮助，另一名则拒绝了这一请求。 在这种情况下，选择是显而易见的，领导者只向两个选择的操作员和基地发送消息，他/她提交。(c) 只有不到两名操作员可执行所需任务。在这种情况下，有三种选择：• l1通过中止协商来拒绝活动。 在这种情况下，基地将尝试将活动分配给另一个团队，例如T2。•l1询问T1的其余操作员他们的可用性.从第4点开始，• l1需要其他团队的帮助（场景如下节2.2所述）。(vi) 如果l1已成功分配任务，则所选操作员将收到执行活动的特定指令。在那之后，他们将履行协议。(vii) 此外，Base还收到成功将活动分配给T1的通知，并提交协议。A. Baragatti等人/理论计算机科学电子笔记180（2007）2125(viii) 当所有参与者均已作出承诺时，所有参与者均会获通知协议已顺利完成。任何参与者都可以在明确承诺之前的任何时刻撤回其决定在这种情况下，场景结束时，所有参与者都知道这样的决定。典型案例如下：• 后勤基地获悉，天然气供应商已安全地停止向该地区供应天然气，因此这项活动已不再有用。• 团队领导11接收执行具有更高优先级的活动的请求，例如将人员移出该区域。• 操作员意识到无法到达该区域。如前所述，在分配活动期间，特定团队可能需要一些额外的操作员来执行任务。团队在执行已经分配的任务时也可能需要帮助，即如果操作员无法完成变得更难或更复杂的活动。在这种情况下，操作员将通过向领导者发送消息来请求对其自己的团队的支持，领导者将设法将新任务分配给团队的其他成员（类似于上面描述为正常流程的任务分配）。这可能是团队无法提供所需支持的情况下，做必要的参与，从其他团队的操作员。以下场景描述了这种情况。2.2场景：一个团队需要其他团队的支持正常流量：(i) 队长11要求基地从其他团队中寻找额外的操作员，例如n个操作员。(ii) 基地选择k个最近的队伍并转发请求。(iii) 当leader收到请求时，它遵循与§2.1中描述的协议类似的协议来询问操作员的可用性。(iv) 在收到操作员的答复后，组长通知基地可用操作员的数量。(v) 当基地收到足够的答案来满足l1的原始请求时，它会通知所有被选中的团队和l1。基地此时隐含地承诺该(vi) 收到确认后，l1决定提交协议。(vii) 被选中的领导者将收到的通知转发给他们的运营商，并签署协议。(viii) 被选中的操作员收到确认，然后提交。(ix) 当所有参与者作出承诺时，所有参与方均会收到通知与第2.1节中的情景类似，任何参与者都可以撤回其决定并中止。在这种情况下，场景结束时，26A. Baragatti等人/理论计算机科学电子笔记180（2007）21附表1一附表2B附表1C 一附表2C B操作者1运营商2操作者1运营商2附表C附表甲乙丙 C片头1(a) 初步情况。片头1(b) 互动之后图3. 协议中任务之间的交互参与者知道中止。3协调模式在我们的案例研究中，协议主要取决于救援单位的不同成员之间的特定动态因此，谈判的全球结构既不能先验地确定，也不能静态地固定。最常见的场景由分布式流程组成，这些流程可以启动要在较大协商的上下文中执行的本地活动。当参与者启动一个活动作为协议的一部分时，它会创建一个本地管理器来处理此类协商。本地管理器遵循下面描述的[3]的分布式提交协议（参见第3.1节）。图3（a）显示了救援团队中的几个组件在启动其事务流程后的状态的部分视图。特别地，参与者领导者1具有用于处理特定任务的分配的活动过程调度 由于Schedule作为协议的一部分运行，因此它由本地协调器C管理。类似地，任何参与者操作员i都有一个由相应的协调员（A或B）管理的活动进程调度i现在假设活动调度向进程调度1发送一个消息，用于将特定活动分配给操作员1。该交互将活动Schedule和Schedule1加入到同一协商中。在我们的方法中，这是通过使两个参与者都知道相应协调员的身份来实现的。类似地，如果领导者1也需要操作者2的支持来执行该活动，然后领导者1联系操作者2，则所涉及的各方的状态被更新，如图3（b）所示。考虑此时所有参与者leader1、operator1和operator2都具有独立决定提交或中止所需的所有信息。在这种情况下，每个参与者都在本地激活下面描述的提交协议，并等待结果决策。A. Baragatti等人/理论计算机科学电子笔记180（2007）21273.1分布式两阶段提交协议（D2PC）本节对[3]中提出的D2PC进行了非正式的描述。最初，人们提出实现零安全网，这是Petri网的事务扩展。D2PC是去中心化2PC协议的一个变体[2]。粗略地说，它在一组参与者（或他们的管理者）之间实现了一个分布式协议，这些参与者对整个参与方都有部分了解。该算法假设参与者之间的可靠异步通信。此外，参与者可以中止，但不会崩溃。 D2PC已被证明是正确的，在这样的设置，确保所有参与者将异步采取相同的决定（细节可以在[3]中找到）。虽然在一个MANET节点可以断开和通信不是高度可靠的，在这项工作中，我们不处理故障，因为我们的目的是研究如何像D2PC协议可以用于协调§2中描述的场景中的谈判。注意，当通信可靠性不能由MANET中间件（动态路由和重传机制）保证时，D2PC的正确性证明就不再有效。 为了处理更一般的情况，我们计划开发和使用一个合适的分布式版本的三阶段提交协议（非阻塞和较少的保证），但这是留给未来的工作。D2PC中的所有参与者都充当事务管理器，它们都具有相同的行为，并以异步方式进行通信。任何管理器都维护一个所有已知方的列表（对于该事务），称为同步集（S）和提交方列表（C）。 在交易开始时，两个列表都是空的。在事务处理期间，同步集被更新以包括从其接收消息的各方以及向其发送消息的各方。因此，当D2PC被激活以结束事务时，同步集只包含与其发生直接交互的那些方。列表S和C都在协议执行期间被更新，直到存在中止或者两个列表变得相等（意味着事务的所有其他参与者都是已知的，他们已经投票支持提交，并且提交投票已经发送给他们所有人）。更准确地说，任何参与者都执行图4中描述的算法。对于Join中协议的正式定义，我们请感兴趣的读者参考[3]。（也许符号的含义是：对于包括同步集的那些消息，意味着同步集中的各方被“锁定”，/abort已建立。）在图5中，我们展示了一个D2PC的运行，其中有三个协调器A、B和C，来自图3（b），他们中的任何一个都愿意提交。初始配置（图5（a））显示了任何参与者对协议中其他各方的部分看法（参见本地同步集S）：A和B只知道C是协议过程的一部分，而C知道A和B。此外，每个参与者都将提交确认集合C与空集进行比较。当协议开始时（图5（b）），每个参与者将其准备提交投票连同其同步集S一起发送到任何已知参与者。在这一轮之后（图5（c）），所有参与者都用信息28A. Baragatti等人/理论计算机科学电子笔记180（2007）21第j个参与者Pj的初始状态。• S j：所有已知参与方（Pj直接合作的参与方）的集合。• Cj=0• 状态j∈ {提交，失败}算法• 承诺。在状态提交中，执行以下步骤(i) 如果Sj=Cj，则具有“限制”的finn ish。(ii) 否则，将自己的同步集Sj发送给Sj中尚未发送消息的每个已知方（消息Sj）。(iii) 对于接收到的故障信息（Si），从Pipi pi· Sj= Sj<$ Si· Cj=Cj{Pi}(iv) 如果收到消息ABORT，则发送所有REQ消息，然后转到失败状态。(v) goto 1.• 失败. 当达到失败状态时，以“abort“结束。在状态下，对任何接收到的类型为“ABORT”的消息的应答失败。图4. D2PC算法S= {C}C={}S= {C}C={}S= {C}C={}S= {C}C={}S={B，C}C={C}S={A，C}C={C}一BS={A，B}C={}(a) 初步情况。S={A，B}C={}(b) 首轮S={A，B}C={A，B}(c) 第一轮之后。S= {B，C}C={C}S= {A，C}C={C}S= {B，C}C={B，C}S= {A，C}C={A，C}{B，C}一B{A，C}一BCCS= {A，B}C={C}(d) 二轮S={A，B}C={A，B}(e) 最后的情况。图5. commit的例子包含在接收到的消息中。请注意，C收到了A和B的投票，但没有其他参与者的信息。在这种情况下，C的集合S和C都重合，因此C知道谈判中的所有各方都愿意承诺。此时C可以提交，因为没有任何一方决定中止。不同的是，A和B已经从C收到了包含先前未知的参与者的提交投票，因此它们更新了它们的状态，并且必须继续执行协议。在下一步中，A和B将他们的决策发送给最近已知的参与者（图5（d））。之后，它们更新状态并提交（图5（e））。CA{C}{C}B{A，B}{A，B}C一BCA. Baragatti等人/理论计算机科学电子笔记180（2007）2129ABT一B一BCCS= {C}C={}S={C}C={}S={B，C}C={C}一BS={A，B}C={}(a) 初步情况。S={A，B}C={}(b) 首轮S={A，B}C={A}(c) 第一轮之后。S={B，C}C={C}S= {B，C}C={C}一BCS= {A，B}C={C}(d) 二轮(e) 第二轮之后。S={B，C}C={C}(f) 第三轮（g）第三轮之后。图6. abort的例子考虑一个不同的场景，其中A和C愿意提交，但B决定中止。初始情况如图6（a）所示。我们不显示中止组件的同步集，因为它是无用的。当协议开始时，提交状态中的每个参与者（即，A和C）将其投票发送给已知的各方。与前一种情况类似，提交参与者更新他们的状态（图6（c））。请注意，C不能提交，因为它没有收到来自B的确认。两个A都不能提交，因为它已经收到了身份B，发现了一个新的参与者要联系。在下一轮（图6（d））中，A将其投票发送给B。相反，B回答前一轮用abt从C发出信号，表示协商的中止在第二轮之后（图6（e）），C由于从B接收到消息abt而中止，而A仍在等待来自B的相应投票。最后，在第三轮中（图6（f）），B用abt回答来自A的提交投票。在这一轮之后（图6（g）），所有参与者都中止。C一A{C}B{A，B}{A，B}CBC{B，C}一BCABT30A. Baragatti等人/理论计算机科学电子笔记180（2007）214执行图7. 用户操作。我们已经开发了一个原型应用程序，它在介绍和§2中描述的场景的上下文中实现了一组最小的功能。它允许用户交换文本消息，并在交互的各方之间达成协议。在我们的原型中，参与方可以是两种不同的类型：（i）运行Jocaml和Perl代码的Linux组件;（ii）用Polyphonic C编写的.Net组件。由于各方通过TCP套接字进行通信，因此两种类型的组件都可以参与同一协商。在本节中，我们将描述启发我们实现设计的架构和原则。特别是，从用户的角度来看，组件的功能在§4.1中进行了详细说明，而各方之间的通信在§4.2中进行了总结。然后，§4.3和§4.4分别介绍了Jocaml+Perl和Polyphonic C最后，§4.5讨论了Join、Jocaml和Polyphonic C中D2PC的各种编码之间的主要差异以及一些性能方面。4.1用户视图我们的应用程序允许用户交换带有文本内容的消息，试图与其他可到达的用户（从一组先验固定的方中选择，并从配置文件中选择）建立某种协议。用户可以随时决定是提交还是中止。图7显示了包含核心小部件的图形界面片段：一个用于输入消息的文本框，一个用于发送键入消息的按钮，一个用于投票提交的按钮，另一个用于投票中止的按钮。在作为协议的一部分向其他用户发送和接收消息之后，用户将投票提交或中止。我们假设每个参与者都会在有限的时间内投票提交/中止。如果用户投票中止，则整个协议被中止。因此，图形界面会立即显示中止状态。此外，该协议中的所有剩余用户将在投票后知道中止。相反，当用户投票提交时，等待其他各方的所有决定，并且只有当谈判中的每个其他参与者都投票提交时，状态才会被提交实现决策的方式对用户是隐藏的，用户只需按下提交按钮，然后等待结果显示。此外，我们假设救援单位的结构是静态固定的，并且是先验已知的。因此，我们为任何用户提供一个配置文件，A. Baragatti等人/理论计算机科学电子笔记180（2007）2131描述救援单位的所有成员。 特别是，任何用户都使用唯一的ID进行标识，该id在启动应用程序时作为命令行参数提供。此外，配置文件将ID与IP地址相关联。各方通过阅读配置文件知道如何到达其他节点。此外，各方通信的端口完全取决于节点ID。这确保了在同一IP地址上运行的不同应用程序在使用TCP端口时不会发生冲突（对实验很有用）。因此，应用程序和协调程序级别的通信只需要对等伙伴的ID请注意，在参与者集合无法静态定义的情况下，可能需要发现机制。这些情况需要特定的协议来动态发现超出本工作范围的节点这种协议应该在物理介质访问级别上实现，以便尽可能多地节省例如，我们可以使用蓝牙和802.11技术（l2ping，etherping）上可用的类似hwping的工具，这使得实现强烈依赖于所采用的无线物理层：任何L2媒体都需要自己实现发现机制。作为一个额外的功能，我们的原型提供了一个小的机制，用于监测节点的可达性，这是独立于物理介质，因为它依赖于UDP数据包。它通过向echo端口发送一个虚拟UDP数据包来不断轮询IP当连接不可能时，主机被认为是不可访问的。这个工具不需要任何特殊的root权限（像icmp那样），它减少了TCP消息（SYN，ACK，PUSH等）的数量潜在地对无线媒体进行加密。我们可以通过实现迭代自动选举算法来摆脱配置文件，该算法类似于NTP协议用于选举主节点或解决OSPF中指定路由器选举问题的算法（其中根据其接口MAC地址执行例4.1作为一个运行示例，我们考虑一个由三个节点组成的系统。如前所述，不同的节点通过名称（通常是IP，但我们在测试床中也使用了DNS可解析的名称）和ID进行标识，定义为配置文件。在这种情况下，所有参与者都使用以下配置文件：dotto：1131.114.2.205：2131.114.3.110：3一旦应用程序启动，每个用户界面都将显示可到达的节点。例如，ID为1的用户（缩写为User1）将看到其他两个用户，即用户2和用户3（图8（a））。类似地，用户2看到关于用户1和用户3的可达性信息（图8（b）），并且用户3具有关于用户1和用户2的信息（图8（c））。现在，假设User3向User1发送消息在这种情况下，用户1的接口（图9）将在其联系节点列表中显示用户2和32A. Baragatti等人/理论计算机科学电子笔记180（2007）21(a)用户1。（b）用户2。（c）用户3。图8. 可达性信息。图9. 与用户2和用户3交换消息后用户1的状态。图10. 从User1接收消息后User2的状态。图11. 与用户1交换消息后用户3的状态。用户3。此外，消息类似地，用户2（图10）和用户3（图11）的界面将在联系节点列表中显示用户1的地址，并在接收消息列表中显示消息请注意，此时User2和User3从未交换过消息，但它们是同一协商的一部分，因为它们都与User1进行了交互。他们所知道的关于彼此的信息只涉及可达性，即他们可以交流。假设此时所有用户都按下Commit按钮，这将激活每个节点中分布式提交协议（D2PC）的执行。由于所有参与者都已投票提交，提交协议将透明地关闭协议，每个GUI的状态栏最终将显示值Commit（在这种情况下，D2PC的执行将类似于图5）。图12显示了User2的最终状态（在其余参与者的GUIA. Baragatti等人/理论计算机科学电子笔记180（2007）2133图12. 在D2PC终止后的用户2。4.2各方之间的沟通各方（或节点）之间的通信发生在两个不同的级别：（i）应用程序级别;和（ii）协调员。在应用层，各方交换与协议逻辑相对应的消息，如§3所述。相反，协调器交换的消息对应于D2PC协议。下面总结了可能发生的两种参与方之间的通信，以及相应的消息格式。应用层通信。在应用程序级别，当一个用户向另一个用户发送消息时，双方交换消息在这种情况下，发送器和接收器都用另一参与者的身份来更新它们的同步集，即，从这一刻起，两个参与者都是同一谈判的一部分。应用程序级别的消息具有以下形式：[free text]来自用户ID>还应包括谈判标识符。不失一般性，我们在这里假设每个GUI只涉及一个协商。(In一般来说，谈判的局部渐进编号将是可行的。）协调员之间的沟通协调器交换与第3.1节中描述的D2PC相对应的消息，以投票提交或中止：• LOCK-l1;l2;.; ln-l1-a1-发送具有同步集合l1;l2;.; ln. 逻辑名称l1和a1表示要使用的端口由其他参与者发送D2PC 向当地协调员发送消息。（请参阅相应的TCP端口容易从L1和A1导出，L1和A1是为了方便而使用的逻辑ID）。• ABORT-通知发送方已到达中止。34A. Baragatti等人/理论计算机科学电子笔记180（2007）21图形界面41协调员32D2PC图13.分层架构。4.3用Jocaml和Perl编写的组件参与方已经实现为图13所示的分层架构。任何层的功能总结如下。• 图形界面处理GUI事件以允许用户向其他方发送消息，以及提交或中止当前协议。• 协调器负责提交协议的分布式执行。它与其他协调器通信，并使用底层的D2PC算法。• D2PC算法执行§3. 1中描述的算法。关于提交协议的所有信息都由D2PCAl-出租M在本地处理，但是发往/来自其他节点的消息由协调器层管理（和转发）。虽然组件之间的通信可以连接到D2PC算法中，但这两个功能是分开的，以使D2PC算法独立于各方使用的通信模型。例如，组件可以通过UDP套接字而不是TCP套接字进行通信，只要改变中间层。顶层和中间层是用Perl实现的（用于快速原型设计），而底层是用Jocaml编写的。Jocaml是Objective Caml（Ocaml）的扩展，Ocaml是一种支持面向对象和命令式范式的函数式语言，实现了Join的原语。Jocaml提供了三个主要的抽象：流程、通道、连接模式。进程代表通信和同步任务。最简单的过程是异步消息。复杂过程是通过将表达式与其他过程的并行合成相结合而获得的。通道是对应于连接名称的Jocaml抽象。有两种不同的通道：同步和异步。定义通道的语法如下let defname[！]（args）=P（args）这个定义创建了一个通道（命名为name）和一个接收器，它将在每次收到消息时执行受保护进程P当频道名称后面加上符号！时，频道是异步的否则它是同步的。A. Baragatti等人/理论计算机科学电子笔记180（2007）2135...letdefcreate thread（）=或国家！ H|放！（l，a，c）=commit 0（remove lock l，l，[lock]，c，union a h）或国家！H|abt！（）=释放h|失败了！（）作为回答，lock，put，state，abt;;图14. Jocaml中D2PC管理器的部分视图。同步名称必须返回一个值，即，P必须显式定义返回值。最后，联合模式被用来描述不同信道之间的同步。连接模式定义同时创建多个通道，并声明它们之间的同步：只有当所有通道上的消息都存在时，才可以执行相应的保护进程。这些特征在D2PC经理的定义中得到了充分利用。图14显示了与Jocaml中的D2PC管理器相对应的代码的部分视图，特别是处理协议开头的模式。层通过经由TCP（或Unix域）套接字异步地交换消息来进行通信，这通过允许模块以不同的语言（例如，Java而不是Perl）。不同层之间的通信协议总结如下（编号参见图13）。(1) 申请→协调员。 应用层向协调器发送消息以便启动提交协议，特别地，它可以向协调器发送一个 根据用户按下的按钮，显示以下两条消息：• ABORT-启动提交协议投票• PUT-l1;l2;. ln-启动提交协议投票“提交“。该消息包括联系方l1;l2;.;ln，其被转发到D 2 PC层。该列表将用于在提交协议开始这类消息的名称PUT起源于[3]中提出的D2PC的集中式版本（基于Join的非响应片段），其中消息意味着“放置”返回(2) 协调员→D2 PC。当协调器收到来自用户的投票（上述两个消息之一）或作为d 2 pc协议的一部分收到来自其他方的投票（协调器之间的方间消息）时，协调器将消息转发到d 2 pc层。更准确地说，协调器可以向D2PC层发送以下消息，以便启动提交协议或更新算法的状态• ABORT-启动提交协议投票• PUT-l1;l2;.; ln-启动提交协议投票“提交“。同步集合包含协调器l1;l2;...; ln. 此消息对应于应用程序生成的PUT• LOCK-l1;l2;.; ln-l1-a1-通知来自l1的提交投票，同步设置为l1;l2;...;ln. 端口l1和a1指的是发送方的端口锁定和中止36A. Baragatti等人/理论计算机科学电子笔记180（2007）21初始化新新新GUI（应用层）投票委员会（put）&D2PC（锁）D2PC ctd.（锁）&GUI通知（提交）承诺−l1;l2;l3−l3−a承诺3−承诺−l1;l2;l3−l1−a1−−l1;l2−l1−a1−l2;l3−l3−a3−PUT−l1;l2−PUT−l2;l3−−l1;l2;l3−l2−a2−PUT−l1;l2;l3−−l1;l2;l3−l2−a2−User2“定位人员”，1来自用户的“关闭气L3(D2PCcoord.）L2(D2PCcoord.）L1(D2PCcoord.）User3（Appl.GUI）User2（Appl.GUI）User1（Appl.GUI）图15. 协议的示例时序图。(3) D2 PC→协调员。 D2 PC算法生成以下消息来通知协调器它必须采取的操作（参见图4）：• FWLOCK-l1-l1;l2;.; ln-要求协调器将提交投票转发到具有同步集合l1;l2;.的协调器l1; ln.• FWCOMMIT-COMMIT-要求协调器通知用户已达成一致。• FWABT-ABORT-通知协调器当前的协商已经中止。• FWABT-a1- 要求协调器将中止消息转发到端口a1对应于协商中协调器的端口中止(4) 协调员→应用程序。协调器通知应用程序协商成功或失败：• ABORT-通知正在运行的协商已中止。• COMMIT- 通知正在运行的协商已提交。当应用程序收到上述两条消息之一时，用户界面中状态框的内容将相应更新图15中的序列图显示了不同层之间和参与者之间的交互示例。协调器层被省略以提高可读性.特别是，当参与者的应用层决定启动一个新的协议时，它会在本地为该协议创建一个新的D2PC管理器（初始化阶段）。GUI阶段对应于应用程序的逻辑。在示例中，用户1向用户2发送文本消息，用户2向用户3发送消息。(Note文本消息具有用于本地D2PC管理器的标识符的额外参数，图中未报告）。通过这种方式，应用程序获得了合作管理器的知识（消息被发送给谁，或者消息从谁那里最终，每个应用层将决定是提交还是中止，启动D2PC协议。在这个图表中，我们展示了A. Baragatti等人/理论计算机科学电子笔记180（2007）2137public class Uncategorized{...//异步方法的声明public void abt（）;private public browser（ port a，port c）;private browser（port h）;private browser c commit 0（lHost l，lHost l1，lHostl2，port c，lPort a）;...//a sample chord定义当state（port h）put（lHostl， port a，port c）{port localHost=l.element（0）;lHost l1 = l.Clone（）;l1.remove（localHost）;lHost l2= new lHost（localHost）; commit0（l1，l，l2，c，union（a，h））;}...}图16. D2PC类所有应用程序决定提交：首先User1按下COMMIT按钮，然后User2和最后User3做同样的事情（参见PUT消息的顺序）。请注意，每个应用程序都在本地启动协议，将PUT消息发送给管理器。PUT消息的参数对应于GUI阶段期间联系方的列表。管理器根据D2PC算法发送数据包消息。当D2PC的执行结束时，每个管理器将通知其应用层最终决定（在本例中为COMMIT4.4.Net组件缔约方也已经实现了面向对象的语言Polyphonic C#[1]。Polyphonic C#扩展了C#的异步方法（使用关键字“clock”声明）和同步模式（称为chords）（由关键字“when”定义）。对异步方法的调用保证几乎立即完成，即，呼叫者从不阻塞。一个和弦是由一个标题定义的（即，一组方法声明）和一个主体。所有的方法头中的所有参数都被调用了。考虑图16中的d2pc类，它的实例负责执行提交协议。公共异步方法put、lock和abort分别启动协议，接收来自partner的准备提交投票，并接收abort。 私有异步方法state和commit0表示管理器的内部状态。以下和弦当state（port h）&put（lHost l，port a，port c）.处理提交协议的激活。特别地，当状态（对管理器的初始状态进行编码）和放置（即，来自应用的提交投票）被调用。Polyphonic C#组件的类如图17所示。实用程序类Receiver和Receiver提供了向和发送消息的方法38A. Baragatti等人/理论计算机科学电子笔记180（2007）21参与者GUI发送者static sendMsg（.）c put（lHost l，port a，port c）锁（lHost l，port l1，port a）d2pc静态端口监听器（int端口，d2pc c）接收器图17. Polyphonic C#组件接收来自其他方的消息类User Interface处理与用户的交互，d2pc的实例执行提交协议。请注意，组件内部类之间的通信是通过方法调用而不是套接字通信来实现的4.5讨论在Jocaml中和Polyphonic C是：• 不确定性中止。原始的连接编码允许管理器在任何时候自动地发起提交协议投票中止，而它还没有接收到通过投票提交发起提交协议的PUT消息（中止决策的非确定性模拟）。这条规则保证了终止协议的任何实例，具有一旦管理器被创建就可以被触发的缺点，以这种方式禁止等待提交的可能性。相反，在Jocaml和Polyphonic C实现中，管理器仅在其接收到中止投票（例如，来自相关联的用户）时才开始针对中止的提交协议投票。只要协议中的每个参与者在有限时间后投票，这种实现选择不会损害D2PC的正确性和完整性。由于我们假设所有用户最终都会投票，因此这种修改并没有改变协议的属性。• 非线性模式匹配。 Jocaml和Polyphonic C都没有提供非线性模式匹配的机制，尽管在[ 10 ]中已经提出了具有线性模式匹配的Join演算的扩展。在D2PC的Join公式中，为了方便起见，在端口提交时使用了非线性模式匹配，端口提交表示管理器的内部状态。有两种情况，一种是有经理需要通知，另一种是所有已知的经理都已经通知。D2PC允许从其他经理发送通知和在我们的实现中在接受经理的投票之前，我们强制要求发送所有通知。显然，这是原始规范的一种特殊交织，因此它满足了协议的所有属性。在我们的编码中，这是通过使用辅助端口来实现的，以避免非线性模式匹配。A. Baragatti等人/理论计算机科学电子笔记180（2007）2139用户6User2用户5User3用户1用户2用户3用户4用户5用户6User1用户4用户5用户6用户4用户1用户2用户3用户1用户2用户3用户6用户5用户4图18.实验模式。• 集合上的运算。我们已经实现了在Jocaml的功能联盟，重新移动，等价和差异（列表表示）集.在Polyphonic C中，我们实现了lHost类，它提供了与一组主机地址相对应的操作。为了了解D2PC在网络上交换的总字节数和通知所有用户提交所需的最大时间延迟方面的开销，我们在一个简单的MANET配置上进行了一些涉及六个用户的测试。用户编号从1到6，移动自组网由两个通过蓝牙连接的节点（笔记本电脑）组成。 每个节点运行三个不同的用户（偶数用户和奇数用户运行在不同的节点上）。用户根据四种不同的模式交换消息（参见图18）：（i）线性模式，其中用户号i向用户i+1发送文本消息;（ii）团（完全图）模式，每个用户向所有其他用户发送和接收消息;（iii）不平衡的树状模式;（iv）星形模式，其中一个用户与所有其他用户交换消息. 当协议开始时，不同的模式影响每个参与者的初始知识。在我们所有的实验中，衡量提交协议性能的时间被计算为最后一次按下提交按钮（总是来自用户编号6）和第一次/最后一次在用户界面上重新刷新
