Arigatoni：一种全球计算覆盖网络模型的操作语义

理论计算机科学电子笔记171（2007）55-75www.elsevier.com/locate/entcs在Arigatoni的Michel Cosnarda Luigi Liquoria Raphael ChandaaINRIA，法国摘要Arigatoni是一个轻量级的覆盖网络，它在互联网上部署了全球计算范式。覆盖的行为单元上的通信由简单资源发现协议（RDP）执行。基本全球计算机单元（GC）可以通过首先注册到代理服务，然后通过相互请求和操作服务进行通信。殖民地和社区是模型中的主要实体。一个群体是一个简单的虚拟组织，由一个领导者和一些（可能是空的）个体组成。社区是一组原始的殖民地和全球计算机（把它想象成一锅没有领导者的殖民地和全球计算机我们提出了一个操作语义通过标记的过渡系统，描述了必要的主要操作在Arigatoni模型进行领导人谈判，加入/离开一个殖民地，连接两个殖民地和移动一个GC从一个殖民地到另一个。我们的形式化结果是足够的w.r.t.该算法执行对等体日志记录/去日志记录和群体聚集。保留字：重叠网络，Arigatoni，虚拟组织，P2P系统1引言通过P2P系统有效地使用计算网格需要关于广泛分布的资源的最新这是一个具有挑战性的问题，非常大的分布式系统，特别是考虑到不断变化的资源状态。发现动态资源必须在资源和用户的数量上是可扩展的，因此，尽可能地完全分散。它应该容忍间歇性的参与和动态变化的状态/可用性。Arigatoni模型适合于通过互联网部署全球计算通信范式，即。e.计算通过一个无缝的，地理上分布式的，开放式的网络有限的资源代理与部分知识和没有中央协调。该模型可以首先部署在内部网中，并通过在实际网络的顶部重叠覆盖网络来进一步从内部网部署到内部网。覆盖网络是在一个全局网络之上产生另一个全局网络的抽象。覆盖的例子是资源分布服务（分布式网络中资源共享的概念），搜索引擎（信息存储库的抽象）或可信移动代理系统（自主探索行为的概念）[5]。1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.11.03556M. Cosnard等人理论计算机科学电子笔记171（2007）55Arigatoni模型为覆盖网络本身的实际部署提供了必要的基础设施。此外，我们的工作抽象了覆盖网络正在使用哪种资源;实际上，这项工作可能对网格，或分布式文件/带共享，或更先进的场景（如移动和分布式面向对象计算）有用。Arigatoni通信模型是由一个明确的领导者管理的殖民地组织起来的。全局计算机只属于一个殖民地，对位于同一殖民地或另一殖民地的资源的请求穿过代理-2-代理协商，其安全性通过PKI机制得到保证。该模型适用于各种全球场景，从经典的P2P应用程序（如文件或频带共享）到更复杂的网格应用程序（如远程和分布式大型（和小型）计算），直到可能的未来迁移计算，即。e.将未完成的本地运行转移到另一个GC中，后一种情况在灾难性情况下是有用的，如火灾、恐怖袭击、地震等，在静脉的全球编程语言à laObliq或Telescript。Arigatoni模型中的单位是：• 一个全球计算机单元，GC，i。e.全球计算机范例的基本对等体;它通常是通过IP连接的小型设备，如PDA、膝上型计算机或PC，与所使用的介质（有线或无线）无关。• 全局代理单元GB是一个基本单元，用于注册和注销GC，接收来自客户GC的服务查询，联系潜在的服务GC，与后者协商给定的服务，信任客户和服务器，以及发送所有必要的信息以允许客户GC和服务GC通信。每个GB控制一个由协作的全球计算机组成的殖民地（用COL表示）。因此，菌落内的通信仅通过一个GB发起，而菌落间的通信通过GB-2-GB消息交换链发起。在这两种情况下，当客户端GC从适当的GB接收到对请求服务的确认（以及相关的信任证书）时，客户端将直接从服务GC享受服务，即。e.而不需要英国政府的进一步调解• 全局路由器单元，GR是一个简单的基本单元，专门用于使用适当的资源发现协议[3]发送和接收数据包，并将“有效载荷”转发到与该路由器连接的单元。每个GC和每个GB都有一个个人GR，它通过合适的API与之通信。路由器和对等体之间的连接通过合适的API来确保。群体和个体是模型中的主要实体。一个群体是一个简单的虚拟组织，由一个领导者和一些（可能是空的）个体组成。个体是全球计算机（把它想象成变形虫），或者（子）殖民地（把它想象成原生动物）。一个殖民地的正式定义是使用这个简单的BNF语法：COL：：={GB}|COL ® {GC}|简体中文M. Cosnard等人理论计算机科学电子笔记171（2007）5557{GB}是（小）菌落{GB1，GC1. GCm}是菌落亚菌落阿克斯{G B 1，GC1.. . GCm，{GB2，GCm+1.. . GCm+n是一个殖民地（它包含一个亚殖民地）{G B 1，GC1.. . GCm，GB2，GCm+1 。 . GCm+n}亚菌落亚菌落不是殖民地（2GB）¸ x`˛ ¸ x` ˛{G B 3，{GB1，GC1.. . GCm}，{GB2，GCm+1.. . GCm+n是一个殖民地（有两个亚殖民地）亚菌落¸ x`˛ ¸ x` ˛{{GB1，GC1.. . GCm}，{GB2，GCm+1.. . GCm+n不是一个殖民地（在顶层殖民地没有领导者），但它是一个社区图1. 一些殖民地殖民地的两个主要特征是：(i) 一个群体只有一个领导者GB和至少一个个体（GB本身）;(ii) 菌落包含个体（一些GC菌落的一些示例如图1所示。Community（用COM表示）是一组原始的殖民地和全局计算机（把它看作是一锅殖民地和没有领袖的GC的汤）。社区的正式定义使用BNF语法给出：联系我们|联系我们|联系我们图1显示了一个简单的社区示例。从抽象语法中可以看出，殖民地是一个社区，但反过来则不然。资源发现是构建覆盖计算机网络的关键问题之一个人（全球计算机）可以注册和注销殖民地。同样的道理也适用于亚殖民地，而亚殖民地又可以（不）注册到另一个殖民地。注册（取消）的主要困难是处理管理域：正如Cardelli Gordon关于移动环境的开创性论文[ 2 ]所“在互联网的早期，人们可以依靠IP地址提供的域名空间;知道一台计算机的IP地址很可能允许现在以某种方式与该计算机交谈。但现在情况已经不同了：防火墙将互联网划分为多个管理域，除了严格控制的路径外，这些管理域彼此隔离。系统管理员强制执行关于什么可以通过防火墙以及如何通过防火墙的政策。（一）登记方式。基 本 上有两种注册到殖民地的GB领导人，后者不受Arigatoni模型的强制执行：58M. Cosnard等人理论计算机科学电子笔记171（2007）55• 个人（GC或殖民地）向属于同一当前行政域的殖民地的GB领导人注册;• 通过个人（GC或殖民地）的远程隧道向属于不同行政域的殖民地的另一个GB领导人注册。 在这种情况下，我们说，个人事实上是在当前的管理域中以本地模式工作，而在另一个管理域以全局模式工作。除了这种远程注册之外，同一个人仍然可以向属于其居住的同一行政域的殖民地的GB领导人注册。因此，在其全局模式下，它将属于当前管理域的殖民地，而在其本地模式下（通过远程隧道），它将属于另一个管理域中的另一个殖民地。相反，个人可以根据以下简单规则取消注册d’étiquette• 只有当不存在向其所属的集群的领导者GB要求或请求的未决服务时，取消注册才是可能的：它必须等待领导者GB的应答或者等待请求已经被请求的服务的GC的直接连接，或者等待超时。殖民地只有在殖民地本身不会腐败的情况下才接受撤销登记;• (as（以上的推论）GB不能从其自己的殖民地取消注册，即。e.它不能自行放电。然而，出于容错的目的，GB可能是错误的。在这种情况下，GC将一个接一个地注销，殖民地将• 一旦GC（e. G.膝上型计算机）已经与属于任何管理域的群体断开连接，它可以迁移到属于任何其他管理域的另一个群体中;总之，该文件的原始贡献是：• 虚拟间歇协议（VIP）在标记转换系统方面的形式化;在我们谦虚的意见中，这是第一次尝试使用形式化方法和标记转换语义数学工具来捕获间歇协议的行为。这种方法的优点是依赖于健壮的数学基础，如语言和并发理论。因此，对覆盖网络相关协议的形式化和机械化证明是可行的。• 一个完整的域独立的模型w.r.t.在文献中的其他模型。换句话说，Arigatoni完全抽象了它的用途，我。e. 网格、文件/带共享、Web服务等• 对于给定网络拓扑的间歇参与的一些模拟结果。2在一个Nutshell给出了Arigatoni模型所有功能单元的完整描述 在[1]中，这一部分是概述。M. Cosnard等人理论计算机科学电子笔记171（2007）5559GCU/GRUGBU/GRUGBU/GRUGCU/GRUGCU/GRU网络IP路由器IP路由器网络GCU/GRUGBU/GRU互联网IP路由器GCU/GRU网络IP路由器网络GCU/GRUGBU/GRUGCU/GRUGCU/GRUGBU/GRUGCU/GRUGCU/GRU2.1全球计算机股图2. ArigatoNet在阿里加托尼模型中，全局计算机单元（GC）是一种廉价的计算机设备。计算机应该能够在独立本地模式下工作，以完成它可以在本地或在全局模式下完成的所有任务，首先在Arigatoni覆盖中注册自己，然后向模型诱导的覆盖网络发出全局请求。图2显示了Arigatoni模型。GC必须能够执行以下任务：• 发现，在GC物理到达一个新的殖民地时，GB，代表殖民地的领导人• 在管理集群的GB上注册/注销• 向其GB请求某些服务，并响应来自GB的某些请求;• 在从GB接收到对请求的肯定响应时，能够以P2P方式直接与服务GC连接，并接收/接收服务。2.2全球经纪人股全球经纪人股（GB）执行以下任务：• 发现另一个超级GB的地址，代表超级殖民地的超级领袖，GB的殖民地就嵌在那里我们假设每个GB都有相应的PKI证书。• 向管理超级菌落的领导者GB注册/取消注册适当的菌落• 在全局计算机的本地基础上注册/取消注册客户端和服务器GC根据定义，每个GC最多只能注册一个GB;• 确认客户端GC的服务请求;• 在GC的本地基地（本地殖民地）中发现满足GC60M. Cosnard等人理论计算机科学电子笔记171（2007）55• 将请求委托给管理另一个殖民地的另一个GB• 执行上述两个动作的组合;• 处理所有公钥基础设施的殖民地内和殖民地间政策;• 通知客户机GC（或委托GB）某些服务GC已接受来服务请求，或者只是通知请求失败殖民地中的每个GC都将其请求发送给作为殖民地领导者的GB存在关于服务发现所需资源的不同场景(i) 代理查找满足所请求的服务所需的所有资源在内部网中本地生成GC客户端的。然后，它将发送所有必要的信息，使GC客户端能够与GC服务器通信。此通知将使用RDP协议进行编码。然后，GC客户端将直接与GC服务器对话，后者将管理请求，就像在经典的P2P系统中一样;(ii) 经纪人没有在其本地内联网中找到所有资源。在这种情况下，它会将请求转发并委托给另一个代理。为此，它必须首先将整个殖民地注册到另一个超级殖民地;(iii) 可以根据GB将其管理的资源与来自委托GB的资源进行组合的能力来设想步骤1+ 2的组合;(iv) 在一个固定的超时时间之后，或者当所有的委托GB都无法满足委托请求时，代理将通知GC客户端拒绝服务。2.3全局路由器单元Arigatoni模型中的最后一个单元是全局路由器单元（GR）。GR实现了所有的低级网络例程，这些例程实际上可以访问IP网络。它是唯一有效运行RDP协议的单元。GR可以实现为一个小型守护进程，它与GC或GB运行在同一设备上，也可以实现为一个与GC或GB动态链接的共享库。总检察长办公室专门负责以下任务：• 在初始启动GC时，它有助于将单元注册到GB;• 它检查格式是否正确，并通过覆盖层将RDP数据包转发到目的地。RDP包对Arigatoni网络中的GC或GB的请求进行编码;• 在最初启动一个GB时，它会帮助该单元使用它知道或发现的其他几个GB2.4单元语义这三个形式单元的形式语义在[1]中首次给出：图3和图4显示了嵌入在GC和GB中的伪代码。我们用蓝色书写M. Cosnard等人理论计算机科学电子笔记171（2007）5561代码对于对等点发现和菌落的虚拟（UN）生长的语义不是必需的，并且我们用红色突出显示必需的代码不平行的whiletrue do//注册循环GBU= Discover（MyCard）case（GlobalMode，RegMode）is（true，false）：ServiceReg（MyCard，GBU，LOGIN）（false，true）：ServiceReg（MyCard，GBU，LOGOUT）否则：//不做endcaseendwhilewithwhiletrue do//Shell循环Data = ListenLocal（）响应= LocalServe（Data）case（Response，GlobalMode，RegMode）is（login，_，_）：//打开全局模式GlobalMode =true（logout，_，_）：//关闭全局模式GlobalMode =false（true，true）：//Ask to theGBUMetaData = PackScenario（Data）ServiceRequest（MyCard，GBU，MetaData）otherwise：LocalReply（Response）endcaseendwhilewithwhile RegMode do//全局GBU侦听MetaData = ListenGBU（）案例MetaData.CMD.SERVICE是SREG：//如果GBU接受我的注册，它会响应ifCanJoin（MetaData）then RegMode=trueendififCanLeave（MetaData）thenRegMode =falseendif子程序：//GBU正在请求一些资源if CanHelp（元数据）then ServiceResponse（MyCard，GBU，ACC）else ServiceResponse（MyCard，GBU，REJ）endifSRESP：// GBU re-如果它找到了一些资源，如果CanServe（元数据）那么Peers = GetPeers（MetaData）响应= GlobalServe（MyCard，Peers，MetaData）ServiceResponse（MyCard，GBU，DONE）LocalReply（Response）else LocalReply（fail）endifendcaseendwhilewithwhile RegMode do//全局GCU监听MetaData = ListenGCU（）ifVerify（MetaData）then Data = UnPackScenario（MetaData）Response = LocalServe（Data）如果响应==失败then ServiceResponse（MyCard，GBU，ERR）else ServiceResponse（MyCard，GBU，DONE）SendResult（MyCard，GCU，Response）endifelse ServiceResponse（MyCard，GBU，SPOOF）endif末端不平行的图3. GC伪码3虚拟组织的形式语义让 ... . } 表 示 一 个 殖 民 地 ， 而 不 一 定 是 一 个 管 理 域 （ 如 Cardelli-Gordonambients），让每个人都有自己的IP地址和安全证书。令{GB，. . }表示具有其领导者e的菌落。G.{GB，COL1，COL2，GC1，GC2，.. . }是一个带有两个亚菌落和两个GC的菌落。一个殖民地实际上是由它的GB领导人的IP地址。设一个社区由{... . }，e. G.{COL1，COL2，GC1，GC2}是一个有两个亚殖民地和两个GC的我们通过社区之间的归约关系“→“提出了一个操作语义克隆，连接两个克隆并将一个GC从一个克隆移动到另一个克隆。通常在进程代数中，约简由社区之间正如Michele Bugliesi在62M. Cosnard等人理论计算机科学电子笔记171（2007）55不平行的whiletrue do//注册循环GBU= Discover（MyCard）case（GlobalMode，RegMode）is（true，false）：ServiceReg（MyCard，GBU，LOGIN）（false，true）：ServiceReg（MyCard，GBU，LOGOUT）否则：//不做endcaseendwhilewithwhiletrue do//Shell循环Data = ListenLocal（）响应= LocalServe（Data）case（Response，GlobalMode，RegMode）is（login，_，_）：//打开全局模式GlobalMode =true（logout，_，_）：//关闭全局模式GlobalMode =false（fail，true，true）：//你请求你的MetaData=PackScenario（Data）ServiceRequest（MyCard，MyCard，MetaData）否则：LocalReply（Response）endcaseendwhilewithwhiletrue do// Intra-colony listening MetaData= ListenPeer（）PushHistory（MetaData）案例MetaData.CMD.SERVICE是SREG：//对等体正在请求（取消）注册更新（菌落，元数据）SubColony：//A Peer is asking for somerequestSubColony = SelectPeers（Colony，MetaData）ifSubColony =={}//Broadcast interthenServiceRequest（MyCard、GBU、MetaData）endifforeach Peer in SubColony do//BroadcastintraServiceRequest（MyCard，Peer，MetaData）endforeachSRESP：//GCU响应请求Sort PushPeers4Id（MetaData）endcase结束于whiletrue do// Spooling Peers4Idforeach（Id，Peers）in Peers4Iddoif （Id）then ServiceResponse（MyCard，{}，NOTIME）elseifSatisfy（Peers，History（Id））然后是服务响应（MyCard，GetBestPeers4Id（Id），完成）endif endifPopPeers4Id（Id）endforeachendwhile与while RegMode do// Inter-colony listeningMetaData = ListenGBU（）PushHistory（MetaData）case MetaData.OPE是SREG：//GBU... 至于南卡罗来纳州的殖民地内儿子：... 至于南卡罗来纳州的殖民地内SRESP：//领导GBU响应请求Sort PushPeers4Id（MetaData）endcaseendcaseendwhileendinparallel图4. GB伪码研讨会上，我们省略了在减少规则的所有必要方面有关的个人状态的变化，我们只专注于功能规则的协议描述间歇性参与的个人。下面列出了简化规则，并给出了简明的解释。(i) 一个GC加入同一个行政域的殖民地发现（GC）=GBsamedom（GB，GC）=truegmode（GC）=trueaccept（GB，GC）=trueregmode（GC）=false{{GB，. . . }，GC}→ {{GB，GC，. . . }}（加入GCU）• discover（GC）=在Arigatoni网络中的GC的物理/逻辑插入时，GB发现领导者GB单元• samedom（GB，GC）=true：代理和全局计算机都驻留在同一个管理域中;•accept（GB，GC）=true：代理接受其殖民地中的全局计算机•gmode（GC）=trueregmode（GC）=false：全局计算机处于全局&模式，但尚未注册。此规则的副作用是将注册模式设置为true。M. Cosnard等人理论计算机科学电子笔记171（2007）5563(ii) GC离开同一个行政域的殖民地pendingip（GC）=falsesamedom（GB，GC）=truegmode（GC）=falseaccept（GB，GC）=falseregmode（GC）=true{{GB，GC，. . . }}→ {{GB，. . . }，GC}（离开GCU）• pendingip（GC）=false：全局计算机没有待处理的服务提供给它的领导者;• samedom（GB，GC）=true：代理和全局计算机都驻留在同一个管理域中;• accept（GB，GC）=false：代理接受删除其集群中的全局计算机• gmode（GC）= false ®mode（GC）= true：全局计算机处于本地模式，但仍注册。此规则的副作用是将其注册模式设置为false。(iii) 一个亚殖民地加入同一行政区域殖民地发现（GB2）=GB1samedom（GB1，GB2）=truegmode（GB2）=trueaccept（GB1，GB2）=trueregmode（GB2）=false{{GB1，.. . }，{GB2，.. . }}→ {{GB1，{GB2，.. . }，.. . }}（JoinCol）• discover（GB2）=GB1：代理GB2在物理/逻辑插入Arigatoni网络时发现代理GB1• samedom（GB1，GB2）=true：两者都位于同一个管理域中• accept（GB1，GB2）=true：代理GB1接受其菌落中的子菌落• gmode（GB2）=true®mode（GB2）=false：代理GB2处于全局模式，但尚未注册。这条规则的副作用是设置其注册模式为真。(iv) 一个次殖民地离开一个殖民地在同一行政域pendingip（GB2）=falsesamedom（GB1，GB2）=truegmode（GB2）=falseaccept（GB1，GB2）=falseregmode（GB2）=true{{GB1，{GB2，. . . }，.. . }}→{{GB1，. . . }，{GB2，.. . }}（LeaveCol）• pendingip（GB2）=false：代理GB2没有待处理的服务提供给其领导者GB1;• samedom（GB1，GB2）=true：两者都位于同一个管理域中• accept（GB1，GB2）=false：代理GB1不接受其殖民地中的子殖民地• gmode（GB2）= false ®mode（GB2）= true：代理GB2处于本地模式，但仍然注册。此规则的副作用是将其注册模式设置为false。64M. Cosnard等人理论计算机科学电子笔记171（2007）55(v) 将两个殖民地连接在不同的行政区域gmode（GB1）=truenewgbu（GB1，GB2）=GB3gmode（GB2）=truesamedom（GB1，GB2）=falseregmode（GB1）=falseagree（GB1，GB2）= trueregmode（GB2）= false{{GB1，. . . }，{GB2，.. . }}→ {{GB3，{GB1，.. . }，{GB2，. . . }}}（LinkCol）• newgbu（GB1，GB2）=GB3：代表GB1创建一个新的代理，GB2;• samedom（GB1，GB2）=false：两者都位于同一个管理域中• agree（GB1，GB2）=true：两个代理之间签署协议;• gmode（GB1）=truegmode（GB2）=trueregmode（GB1）=falseregmode（GB2）=false：代理处于全局模式，但仍未注册。&&&此规则的副作用是将两个经纪人的注册模式设置为真的(vi) 解除两个殖民地在不同行政领域的联系pendingip（GB1）=falsependingip（GB2）=falsependingip（GB3）=falsegmode（GB1）=falsenewgbu（GB1，GB2）=GB3gmode（GB2）=falsesamedom（GB1，GB2）=falseregmode（GB1）=trueagree（GB1，GB2）=false regmode（GB2）=true（UnLinkCol）{{GB3，{GB1，.. . }，{GB2，. . . } → {{GB1，. . }，{GB2，. . . }}• newgbu（GB1，GB2）=GB3：代表GB1和GB2创建新的代理;• samedom（GB1，GB2）=true：两者都位于同一个管理域中• agree（GB1，GB2）=false：两个经纪人之间的协议是用- drawn;• pendingip（GB1）=falsependingip（GB2）=false&pendingip（GB3）=false：代理GB1，2，3没有待处理的服务;• gmode（GB1）=falsegmode（GB2）=falseregmode（GB1）=trueregmode（GB2）=true：代理处于本地模式，但仍然注册。&&&此规则的副作用是将其注册模式设置为false。(vii) 上下文规则和一致性我们为集合并和集合减添加了以下同余规则，以及结构等价规则，其中COM表示社区，COL表示殖民地，=表示集合理论相等。所有的符号都可以被索引。COM1→ COM2（CommCup）COM1- COM3→ COM2- COM3COM1=COM3COM4COM3COM4=COM3→COM2COM3→COM2\COM4（CommMinus）COM1=COM3COM3→COM4COM4=COM2COM1→COM2（结构当量）Rule（CommCup）是归约规则的通常上下文闭包，而规 则 （ CommMinus ） 指 出 ， 一 个 Reduction 可 以 在 其 右 侧 删 除 一 些 对M. Cosnard等人理论计算机科学电子笔记171（2007）5565Reduction本身的执行并不重要的个体。设→是→的自反传递闭包。66M. Cosnard等人理论计算机科学电子笔记171（2007）554加入/离开不同行政区域的殖民地敏锐的读者已经观察到，上面标记的转换系统禁止个体加入/离开另一个领导者居住在不同管理域的群体。为了保证由Arigatoni模型引入的虚拟组织的完整性和安全性，这是合理的。安全穿越管理域是模型必须考虑的一个重要安全问题。然而，一个个体得不到当地殖民地足够的帮助，或者最坏的情况是，它甚至被作为一个个体而被拒绝，这种情况可能是非常常见的。在这种情况下，非常希望该模型允许机制跨越管理域的边界，以便向驻留在另一个管理域中的另一个殖民地这可以通过两种方式完成：(i) 居住在管理域IP1中的个人认识居住在另一个管理域IP 2中的群体的一些 然后，通过一个显式的ssh，笔记本电脑可以登录到桌面，并向“mother colony”发送一个全局请求。因此，笔记本电脑在本地模式下工作，而台式机在全局模式下工作。最终结果将通过ssh隧道发送到笔记本电脑。这种隧道机制在游牧行为的常见实践中是众所周知的，并且在Arigatoni中不需要任何特别的重写规则虚拟组织，因为连接个人朋友是明确和私下进行(ii) 居住在管理域IP1中的个人不知道居住在另一个管理域IP2中的群体的居民，但是它知道群体的领导者的IP如果领导者同意，它可以通过从头开始创建远程个体的虚拟克隆并代表殖民地领导者在殖民地注册来安排ssh隧道如在在前一种情况下，膝上型计算机可以登录到台式机并向“母殖民地”发送全局因此，膝上型计算机在本地模式下工作，而克隆在全局模式下工作。最终结果将通过ssh隧道发送到笔记本电脑。这种机制在游牧行为的常见实践中是众所周知的，并且让人想起虚拟专用网络技术（VPN）[6]。为了实现这种类似VPN的行为，我们必须在图5所示的标记转换系统中添加四个特殊的重写规则。由于明显缺乏空间，这些规则没有评论，而是留给感兴趣的读者作为一个简单的练习。M. Cosnard等人理论计算机科学电子笔记171（2007）5567discover（GC1）=GBagree（GB，GC1）=truesamedom（GB，GC1）=falsegmode（GC1）=falsenewgcu（GB，GC1）=GC2regmode（GC1）=falsesamedom（GB，GC2）=truegmode（GC2）=trueaccept（GB，GC2）=trueregmode（GC2）=false{{GB，. . . }，GC1}→ {{GB，GC2，.. . }，GC1}（JoinTunnelGCU）agree（GB，GC1）=falsesamedom（GB，GC1）=falsependingip（GC2）=falsenewgcu（GB，GC1）=GC2gmode（GC1，GC2）=falsesamedom（GB，GC2）=trueregmode（GC1）=falseaccept（GB，GC2）=false regmode（GC2）=true{{GB，GC2，. . . }，GC1}→ {{GB，. . }，GC1}（LeaveTunnelGCU）discover（GB2）=GB1agree（GB1，GB2）=truesamedom（GB1，GB2）=falsegmode（GB3）=truenewgbu（GB1，GB2）=GB3regmode（GB3）=falsesamedom（GB1，GB3）=truegmode（GB2）=falseaccept（GB1，GB3）=trueregmode（GB2）=false{{GB1，.. . }，{GB2，.. . }}→ {{GB1，{GB3}，. . . }，{GB2，.. . }}（JoinTunnelCol）agree （ GB1 ， GB2 ）=falsesamedom （ GB ， GB2 ） =falsependingip（GB3）=falsenewgbu（GB1，GB2）=GB3gmode（GB2，GB3）=falsesamedom（GB1，GB3）=trueregmode （ GB2 ）=falseaccept（GB1，GB3）=falseregmode（GB3）=true{{GB1，{GB3}，. . . }，{GB2，.. . }}→{{GB1，. . . }，{GB2，.. . }}（LeaveTunnelCol）图5. 通过VPNpendingip （ GC ） =falsegmode （ GC ）=truesamedom （ GB ， GC ） =trueregmode（ GC ） =truefairness （ GB ， GC ）≤reconfigurationnotifiring（GB，GC）{{GB，GC，. . . }}→ {{GB，. . . }，GC}（FireGCU）pendingip（GB2）=false gmode（GB2）=true samedom（GB1，GB2）= true regmode（GB2）= true fairness（GB1，GB2）≤same通 知 解雇（GB1，GB2）{{GB1，{GB2，.. . }，.. . }}→ {{GB1，. . }，{GB2，. . . }}（FireCol）图6. 解雇搭便车者的额外减免规则68M. Cosnard等人理论计算机科学电子笔记171（2007）555解雇搭便车者同样，敏锐的读者已经观察到，最初的标记转换系统允许搭便车者成为一个群体的成员。在经济学和政治学中，搭便车者是指消费超过其公平份额的资源，或承担低于公平份额的生产成本的行为者。搭便车问题是如何防止搭便车的发生，或者至少限制其负面影响的问题。由于“公平”的概念M. Cosnard等人理论计算机科学电子笔记171（2007）5569使用共同财产资源P2P网络中的自组织节点，即所谓的搭便车者，只利用其他节点的资源而不提供任何回报，极大地破坏了P2P网络的公平性图6给出了两个规则，它们考虑了个人所提供的服务数量与所需服务数量之间的比率如果一个群体的领导者发现，公平性太小（对于给定的公平性，它可以任意决定解雇那个人），不另行通知在这里，函数pendingip还检查个体是否没有待处理的服务给免费者，或者一些承诺的服务的超时已经过期，后一种情况意味着免费搭车者承诺了一些服务，但最终没有提供任何服务（不可信）。函数notifying向搭便车者发送一条消息，通知它它是从殖民地定义的6示例在[1]中，提出了地震监测的网格场景在本节中，我们简要回顾了场景，我们提出，通过标记的过渡系统约简，给定的虚拟组织的演变的6.1（Re）设定场景（来自[1]）台湾地震数据公司的总工程师约翰在地震数据采集船上，必须决定下一次数据采集活动。为此，他想处理100万亿次的地震数据，这些数据已记录在位于该公司海岸数据库的海量数据记录仪上，以便进行处理和分析。他已经编写了处理程序的建模和可视化的地震立方体使用一些并行库，如e。G.MPI/PVM：他的程序可以分布在不同的机器上，这些机器将计算整个微积分的一部分然而，计算量如此之大，以至于SeismicDataCorp公司不得不租用一台超级计算机（GCSCU）和一组PC（GCCLU）。John还将通过位于台湾的ISP（GCISPTW）要求带宽，以消除与大量数据传输相关的任何瓶颈之后，应使用位于美国休斯顿的虚拟现实中心VRC（GCVCRCPU）由专家团队分析处理后的数据，并将下一次数据收集活动（GCVRCSPEC）的建议发送给John。因此，人们希望发生以下情况• John用笔记本电脑（GCJohn）登录到台湾某个殖民地的Arigatoni覆盖网络，并发送了一个相当复杂的服务请求，以便使用他自己的代码处理通常，殖民地的GB领导人将接收和处理请求;• 如果GB执行的资源发现成功，则i. e.找到超级计算机、集群和ISP，然后以很高的速度传输数据并进行处理;70M. Cosnard等人理论计算机科学电子笔记171（2007）55ΔGBU/GRUGBU ISPGBU台湾NNeetwtworkrkISPNNeetwtworkrk超级计算机GBU/GRUININTERNETTNNeetwtworkrkNNeetwtworkrkPCluster地震数据VRC休斯敦GCU/GRUGIP请求/响应hn台湾Jo超高速ISP图7. 地震监测网格• John将命令包含地震数据的GCSDTW将合适的数据块发送到超级计算机和GB指定的集群，以执行一些计算;• 约翰将分配给超级计算机单元收集所有中间结果的任务，以便计算最终结果（即。e.它将扮演乐队指挥的角色）;• 处理后的数据然后从超级计算机发送，通过高速ISP送到休斯顿中心进行观察和分析• 最后，专家小组的建议必须发送到约翰的笔记本电脑上。图7中以图形方式呈现了该场景。6.2形式化场景初始社区（原始Soup）将由以下元素组成：ΔCOMSoup={{ GBSDTW}， GCSDTW，{ GBISPTW}，