没有合适的资源?快使用搜索试试~ 我知道了~
基于连接符着色的Reo连接器的同步和上下文依赖
理论计算机科学电子笔记154(2006)101-119www.elsevier.com/locate/entcs连接器着色I:同步和上下文依赖戴夫·克拉克1和大卫·科斯塔1,2和法哈德·阿巴卜1CWI,阿姆斯特丹,荷兰摘要Reo是一种基于电路连接器的协调模型,通过数据流、同步和互斥、状态和上下文相关行为的相互作用来协调组件。本文提出了一种基于连接符着色的方案,通过求解Reo连接符的同步约束和排斥约束来确定Reo连接符是否为连接符。在给定边界条件(I/O请求)的特定状态下对Reo连接器进行着色,以确定数据流的路由选择。我们的计划比以前的模型的优势在于,它是更简单的实现,它的模型Reo连接器更接近他们设想的语义比现有的正式模型。保留字:连接器着色语义,协调语言,Reo,Reo连接器。1引言协调模型和语言[1]已经成为解决并发、分布式、移动和异构组件组合问题的基本工具,并降低了最终系统的内在复杂性。在这种情况下,Reo[2]已经被引入作为使用通道的软件组件组合的外生协调模型。Reo引入了组件连接器,它充当粘合代码,不仅可以连接,而且还可以协调基于组件的系统中的组件。组件与其匿名连接的连接器交互,并且不知道其他组件。从连接器的角度来看1Email:{dave,costa,far ha d}@cw i. nl2 由葡萄牙联邦现金信托基金13762 - 2003号赠款支助1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.12.035102D. Clarke等理论计算机科学电子笔记154(2006)101这意味着它必须协调其每个连接组件的并发交互。Reo使用一组可扩展的通道作为基本连接器,设计人员可以从这些通道构建复杂的连接器。作为一种规范语言,Reo支持多种架构模型[2]。为了作为连接器的实现语言,Reo需要一个正式的计算模型。这个模型应该(i)尽可能多地保留Reo作为一种规范语言所提供的自由,(ii)促进连接器在大规模分布式环境中的实现本文提出了一种基于连接器着色的语义模型,用于解决Reo连接器中确定数据流路由所需的上下文相关同步和互斥约束。该模型旨在促进分布式计算环境中Reo连接器的数据流计算(和实现)。本文仅考虑其行为对数据值不敏感的连接器,并且不包括Reo这些问题将在后续讨论中解决。贡献:本文提出的模型在许多方面改进了现有的Reo模型。首先,它在比以前的Reo模型更细的粒度级别上区分连接器行为的替代方案[4,3],通过考虑连接器边界节点处的未决I/O操作(存在)的上下文来确定其实际行为替代方案的集合。结果更接近于Reo行为的非形式化描述其次,在我们的模型中的主要复合算子有一些形式的属性,即,结合性,交换性和幂等性,这使得它非常适合于分布式实现。不太正式的实施方案,需要历史计算和回溯,以解决各种周期的同步段的Reo连接器相比,我们的模型需要较少的互斥在分布式实现,不需要回溯,并允许竞争各方使用对方论文结构:第2节是Reo连接器的综述我们在第3节中介绍了连接器着色,并在第4节中将其扩展到处理上下文依赖。第5节给出了分布式实现方法的概要。在第6节和第7节中,我们讨论了相关的和未来的工作,并提出我们的结论。2Reo连接器在本节中,我们总结了本文中用于描述Reo中组件连接器的基本定义和术语。一个完整的帐户,D. Clarke等理论计算机科学电子笔记154(2006)101103Reo的详细描述,见ArbabReo中的重点是连接器,它充当外部协调器来编排它们在组合系统中互连的组件通道构成了Reo中唯一的原始连接器,是具有两个不同端的点对点通信介质。 Reo使用了一个广义的通道概念。除了常见的同步和异步通道类型、有界或无界缓冲器、FIFO和其他排序方案之外,Reo还允许一组开放的通道,每个通道都有自己的行为,有时是奇异的行为。 例如,Reo中的一个通道不需要同时有一个输入端(接受输入)和一个输出端(产生输出);它可以有两个输入端或两个输出端。图1显示了一些示例通道,其语义出现在第3节中。同步SyncDrainSyncSpoutLossySync异步引流AsyncSpoutFIFO1Fig. 1. Reo中的一些基本通道类型更复杂的连接器可以通过连接器组合由更简单的连接器构造出来。在Reo中,通道通过连接其末端形成节点来组成。一个节点可以包含任意数量的信道端。我们根据节点的共同端的类型将节点分为三种不同的类型:输入节点只包含输入通道端;输出节点只包含输出通道端;混合节点包含两种通道端。组件仅在输入和输出节点上执行I/O操作。只有当所有与节点重合的(输入)通道末端接受数据项时,对输入节点的写入操作才成功,在这种情况下,数据项被写入与节点重合的每个输入末端。因此,输入节点充当复制器。一个输出节点上的take操作只有当至少一个输出通道结束在该节点上重合时才成功,否则会产生一个合适的数据项;如果有多个重合的通道结束产生合适的数据,则会不确定地选择一个,排除所有其他通道。因此,输出节点充当合并器。混合节点的行为就像一个独立的图二. Replicator和Merger分别为了简化建模,我们将合并和复制行为104D. Clarke等理论计算机科学电子笔记154(2006)101一的1一个一个一个一个Reo节点中固有的显式,并且在不失一般性的情况下,使用两个额外的原始连接器对它们进行建模:复制器和合并器(图2)。图3(a)中描述的混合节点A可以用图3(b)中所示的合并器和复制器来表示。因此,本文中的所有节点将由至多一个输入通道端和至多一个输出通道端组成。一(a)(b)第(1)款图3.第三章。(a)Reo节点(b)被合并和复制器取代的节点术语上下文指的是连接器边界上的挂起I/O请求,也就是说,在特定时刻使用连接器的上下文。当通道(因此连接器)的行为随着上下文的变化而显著变化时,通道(因此连接器)被认为表现出上下文相关的行为我们使用短语同步约束来表示Reo通道、复制器和合并器对数据流施加的(上下文相关的)同步和排除约束我们将路由定义为一些同步约束的解决方案。它决定了数据应该在哪里流动,不应该在哪里流动。如何实际执行流程的详细信息不属于路由的一部分。本文提出了一种基于连接符着色方案的同步约束求解方法。上下文相关的同步约束,解决了使用扩展连接器着色,可以传播上下文信息的通道端,以指示他们的行为。3基本连接器着色Reo连接器的语义被定义为其组成通道和节点的语义的组合。我们通过一个例子来说明Reo图4中的连接器是由五个Sync、两个LossySync和一个SyncDrain组成的专用路由器。该连接器的直观行为是,通过其输入节点A获得的数据被传递到以下节点之一:D. Clarke等理论计算机科学电子笔记154(2006)101105一BEFGC D见图4。 专用路由器连接器其输出节点F或G。 如果F和G都愿意接受数据,则节点E充当合并器,并 不 确 定 地 选 择 连 接 器 的 哪 一 侧 将 成 功 传 递 数 据 。 节 点 E 中 的SyncDrain和两个Sync协作以确保数据在B处准确地进行数据流,从而确保数据在F和G处准确地进行数据流。描述通过独占路由器的可能数据流的一种非正式的图形方式是在数据流的地方着色,如图5所示。这种着色的想法是我们模型的基础。请注意,我们从数据流的方向进行抽象,因为通道决定了这一点。图五.可能的数据流行为。 实线标记连接器中数据同步传输的部分。在未标记的部件中,不显示数据。3.1着色我们的模型是基于用颜色标记数据流或其不存在的想法。每种颜色都是对信道和节点所施加的同步约束的解决方案。颜色表示颜色的集合。一个合理的最小颜色集是Ccolour={,},其中颜色“ " 标 记 连 接 器 中 数据 流 的 位 置 , 颜 色 ” “ 标 记 数 据 流 的 缺 失 。Reo语义规定数据永远不会在节点上存储或丢失[2]。因此,连接到节点的一端的数据流与另一端的数据流相同端数据要么从一端流到另一端,要么没有106D. Clarke等理论计算机科学电子笔记154(2006)101=一点也不。因此,两端将具有相同的颜色,因此我们只需为节点着色。着色节点决定了其连接端的颜色,这反过来又决定了连接器的颜色,从而决定了通过整个连接器的数据流。以与其组成部分的颜色一致的方式对连接器的所有节点进行着色,可以生成对通过连接器的数据流的有效描述。通道根据其末端的颜色确定数据流以下定义将着色的概念形式化设Node是可数的一组节点名称。定义3.1(着色)着色c:N→ Ccolour forN<$Node是一个函数,它为连接符的每个节点分配一种颜色。Q通道、节点和连接器通常具有多种可能的颜色,以模拟它们在不同上下文中的行为方式。通道(或连接器)的可能着色的集合由其着色表表示定义3.2(着色表)节点N<$Node上的着色表T是域N的着色集合。Q着色连接器涉及组成其成分的着色,以便它们在其公共节点的颜色上达成一致为了捕捉这个概念,我们定义了二元运算符,定义3.3两个表T1和T2的连接,记为T1·T2,定义如下:T1·T2。{c1} c2|c1∈ T1,c2∈ T2,n∈ dom(c1)<$dom(c2)<$c1(n)= c2(n)}.在这里,f是函数图上的集合论并集。 结果是由于边条件的函数。连接操作满足了下面的一些有用的性质,其中1={0}是空着色的着色表,0={0}是空着色表。这些都很容易证明。命题3.4给定着色表T,T1,T2,T3,则(i) T1·(T2·T3)<$(T1·T2)·T3(结合性)(ii) T1· T2<$ T2· T1(交换性)(iii) T1·T1<$T1(幂等性)(iv) T·11· T T(单位)(v)T·00·T0(零)这些性质的结果是,D. Clarke等理论计算机科学电子笔记154(2006)101107==冗余计算的信息,如当两个不同的并发计算的颜色到达同一部分的连接器。3.2基元Reo连接器的着色表实际上描述了连接器在特定配置下的可能颜色对应于基于该配置的可能的下一步。 因此,我们选择作为原语:通道,合并器和复制器,以及I/O操作。定义3. 5(Primitive)素数是一个简单的元组(nj1, . . ,njk)c,1K其中,对于0l≤k,nl∈ Node,jl∈{i,o},k≥ 1是<基元,c是它的名字,这样一个节点n最多出现为ni和no在(nj1, . . ,njk)c.1K带着色的基元是一对带着色表的基元T在基元的节点上。Q标签i和o表示连接到节点n的端部的方向。例如,(a i,b o)Sync表示Sync,其第一端是连接到节点a的输入端,并且其第二端是连接到nodeb的输出端。 可用于该素数的着色具有与domain{a,b}的着色。标签i和o有助于确保连接符是良构的(定义3.6)。我们经常省略这样的标签,默认连接符的格式良好。I/O操作:对于每个I/O请求,使用原始着色来表示它是否将被执行或延迟。 我们模拟了I/O请求为原语(nj)·,其缺失为(nj),其中j∈ {i,o}。这些基元的着色表是T。{ {n →}}和T.{{n<$→},{n <$→}},以图形方式描绘为而且,很好着色表T和T·模拟了组件和连接器的交互方式。当组件在节点上没有请求I/O操作时,T将T·捕获组件发出数据流请求时的可能性:数据将流或连接器不允许它这样做复制器和合并器:复制器和合并器的行为由Reo节点的语义决定。它们的颜色表见图6。复制器连接器(ai,bo,co)Rep只允许数据通过其所有端同步地复制,或者根本不允许数据通过其所有端同步地复制。当数据流时,数据从a复制到b和c。合并器连接器(ai,bi,co)Mer允许数据从a同步到c或从b同步到c,而排除另一端的数据流如果两种选择都是可能的,则选择其中一种108D. Clarke等理论计算机科学电子笔记154(2006)101CCCa aB C B Ca b a b a b(a)(b)第(1)款图六、(a)复制器和(b)合并器的着色表确定性。渠道:图。7呈现了用于选择通道的着色表我们包括FIFO1的空状态和满状态的条目。由于每个通道具有连接到节点的两端,因此每个通道着色有两种颜色(可以是相同的)信道类型着色台信道类型着色台见图7。 通道及其着色表完全同步的通道(如Sync、SyncDrain和SyncSpout)具有这样的属性:数据流在其两端同步流动数据通过Sync从一端流向另一端,然后流入SyncDrain的两端,最后从SyncSpout的两端流出,如图中的箭头所示LossySync允许数据通过通道一直传输,或仅在其输入端传输(在这种情况下,数据丢失),或不传输数据。(This并不是全部我们将在第4节中重新讨论这个渠道。)异步通道(AsyncDrain和AsyncSpout)一次只允许一端的数据流,或者根本不允许数据流。数据流方向类似于同步方向。空FIFO1可以在其输入端接受数据。一个完整的FIFO1可以从其输出端输出数据。这些通道的另一端不允许数据流。3.3连接器连接器是一个由基元组成的集合,满足一些格式良好的条件。因此,连接器的着色表是D. Clarke等理论计算机科学电子笔记154(2006)101109=根据其成分的颜色表计算定义3.6(连接器)连接器C是元组N,B,E,T,其中• N是出现在 E中的节点的集合;• B N是边界节点的集合• E是一组原始连接器,并且• T是 N上的着色表,使得(i) n∈ B当且仅当 n在 E中只出现一次;(ii) n∈ N\B当且仅当n在E中作为n o和作为ni出现一次。Q带有着色表的基元可以直接被认为是连接符。连接器定义3.7设C1=<$N1,B1,E1,T1<$andC2=<$N2,B2,E2,T2<$是连通子使得(N1\B1)<$(N2\B2)=<$,并且对于每个n∈B1<$B2,ni出现在E1中而no出现在E2中,反之亦然. C1和C2的连接,记作C1<$C2,是:C1-C2.<$N1<$N2,(B1<$B2)\(B1<$B2),E1<$E2,T1·T2<$.Q3.4例如我们说明了计算的过程中的着色表的连接器从其原语。为了简化介绍,我们省略了一些细节,勤奋的读者可以很容易地填写。请考虑:n1n2n3n4.将通道表示为C1、C2和C3。 我们计算C1<$C2<$C3,其中:C1={(n1,n2)Sync},T1:{{n1<$→,n2<$→},{n1<$→ ,n2<$→}}同步C2 =n {(n2,n3)AsyncDrain},T2:{{n2<$→,n3<$→},{n2<$→ ,n3<$→},{n2<$→ ,n3<$→ }}C3 =n {(n4,n3)Sync},T3:{{n4 <$→,n3 <$→},{n4 <$→ ,n3 <$→}}同步.T1·T2 ={{n1<$→,n2<$→ ,n3<$→},{n1<$→,n2<$→ ,n3<$→},{n1<$→,n2 <$→,n3 <$→}}。 继续,(T1·T2)·T3={{n1<$→,n2<$→,n3<$→,n4<$→},{n1 <$→,n2 <$→ ,n3 <$→ ,n4 <$→ },{n1 <$→ ,n2 <$→ ,n3 <$→ ,n4 <$→}。我们可以用图形描述C1<$C2<$C3的着色表:n1n2n3n4n1n2n3n4n1n2n3n4110D. Clarke等理论计算机科学电子笔记154(2006)101通过将I/O请求添加到刚刚计算的连接器的边界节点,我们可以确定它将如何路由数据。下面是两种可能性,当有一个写在左边,但没有在右边:n1n2n3n4n1n2n3n4颜色表中的第一个条目描述了成功的数据流。第二个条目描述了完全没有数据流。在第4节中,我们扩展了我们的着色方案。我们把目前的着色方案称为2-着色,把扩展的着色方案称为3-着色。4上下文相关连接器着色在本节中,我们解决上下文相关行为的问题。我们证明,2-着色方案应用到一个连接器,涉及LossySync未能给出预期的数据流行为。我们认为,发生这种情况是因为上下文信息不传播,使通道选择自己正确的上下文相关的行为。以前的Reo连接器的语义模型[3,5]仍然停留在较粗糙的抽象级别,无法解决这个问题。LossySync具有以下上下文相关行为。如果写入在其输入端挂起,而take在其输出端挂起,则其行为与Sync相同-写入和take同步成功,并且数据通过通道进行同步。另一方面,如果不存在挂起的take,则写入成功,但数据丢失。当我们在LossySync的输入端组成一个LossySync、一个空FIFO1和一个I/O请求时,2色方案的问题就会暴露出来,如下所示:abc.该连接器有以下两种可选的2色:a b c a b c第一个颜色表示I/O操作成功,数据通过a传输,LossySync充当Sync,通过b将数据发送到FIFO1。这是此配置中的预期行为。第二种颜色表示数据在节点a上传输,但在节点b上没有传输,这表明数据在LossySync中丢失。然而,空FIFO1是输入使能的,这意味着它应该总是能够接受数据。 事实上,它不应该成功接收数据的唯一原因是如果连接器给了它一个不这样做的理由,比如不向它发送任何数据。人们可以将这种情况解释为违反了D. Clarke等理论计算机科学电子笔记154(2006)101111LossySync通道,因为数据可以在其输出端接受的信息没有适当地传播到它。上下文相关原语的行为取决于其两端是否存在I/O请求。然而,对于混合节点,没有I/O请求信息,因此上下文是什么并不明显。解决这个问题的关键是确定在解决同步约束的同时可以一致地传播哪些上下文信息。我们的方法不是传播I/O请求的存在,而是关注它们的不存在,或者更一般地说,关注延迟数据流的任何原因,例如不满意的同步约束,或者甚至以与所考虑的节点处的数据流不兼容的方式满足它们。我们现在提出的三色方案,使用颜色来传播4.1三种颜色:Reo为了解决刚才描述的问题,我们修改了我们的颜色集。由于我们希望追踪“延迟的原因”,我们用两种颜色代替无数据流颜色,其中还包括一个箭 头 , 指 示 原 因 的 方 向 。因 此 , 我 们 现 在 使 用 颜 色 ,Ccolour={,,}。所有的颜色都要重新上色。为了减少表的大小和算法的成本,我们还引入了一个方便的规则,称为Rollip规则(Def. 4.1)。IO操作:一个I/O操作原语有如下的着色表:第二个条目表示I/O操作请求被延迟,因为连接器给出了阻止它的理由。第三和第四个条目表示没有I/O操作请求,因此没有数据流是可能的。此外,第三个条目指出,没有I/O可以用来证明延迟是合理的。第四个条目表示连接器中已经存在延迟原因的情况这个表中缺少的一个可能的情况,比如箭头指向另一个方向的第二个情况,是没有意义的。它会读作:有一个I/O请求是延迟的原因因此,这一情况被省略。像第四种情况--有理由拖延,但不使用它--经常出现,并增加了着色表的大小。这些条目可以使用以下规则从其他条目派生定义4.1(翻转规则)带有虚线和指向外的箭头的边界节点的颜色,可以用带有指向内的箭头的虚线来代替。112D. Clarke等理论计算机科学电子笔记154(2006)101这条规则背后的基本原理是,有两个理由证明拖延是合理的:一个是足够的。I/O原语的着色表可以用下面的替换;可使用Rollip规则来恢复剩余的条目-从第三个条目生成第四个条目(上面)。复制者和合并者:我们更新合并者和复制者的颜色表。勤奋的读者可能会证明,在每一种情况下,将大小加倍,这条规则都能解释所有其他合理的可能性。复制器的新着色表是:最后三个条目表示没有数据可以传输的情况。在每一种情况下,来自一端的延迟原因足以导致整个复制因子的延迟。延迟的原因被传播到另一端。合并的新颜色表是:表中的前两个条目涉及合并所做的选择一个输入分支的数据流是延迟另一个输入分支中的数据流的充分原因。第三个条目对应于输出端不存在take:在合并器中不可能有数据流,并且延迟的原因由于在两个输入端中的任一个处没有数据可用性,最终条目对应于无数据流。延迟的原因再次被传播。请注意,两个着色表都不包括所有箭头都指向外部的条目。这就意味着,原因根本就不存在。通道:通道的新着色表如图8所示。着色例如,表示颜色这意味着延迟的原因从通道的一端传播到另一端我们在这个表格中突出了几个感兴趣的点,只关注延迟的原因,让读者思考其余的在Sync、SyncDrain或SyncSpout的一端出现故障,足以阻止数据流。原因被传播到另一端。一个空的FIFO1缓冲器不能使数据流到它的输出端,这是一个延迟的原因双重,D. Clarke等理论计算机科学电子笔记154(2006)101113信道类型着色台信道类型着色台见图8。 3-通道着色台满FIFO1缓冲器有理由延迟其输入端。用于LossySync的表的第二个条目(第2行,第1列)指出,只有当延迟的原因通过其输出端传播时,它才会丢失数据, 这相当于说信道不能传输数据。对于两个异步通道(AsyncDrain和AsyncSpout),在一端接受数据如果两端都有延迟的原因,则不发送数据。请注意,可能需要在前两种可能性之间做出非确定性选择。4.2例如在这个例子中,我们引入了一个新的原语,优先级合并器,并使用它来建模优先级路由器。优先级合并器的行为与合并器类似,允许数据从至多一个输入端向其输出端的分流。不同之处在于,每当数据在其两个输入端都可用时,例如当两端都有写入挂起时,通道就会优先考虑一个特定端。优先权合并的图示和颜色表为:现在我们来构造一个优先级路由器。这就像一个独占路由器,除了当两个take都挂起时,不是做出不确定的选择,而是由优先级合并原语决定选择。图9给出了优先级路由器,以及在配置中唯一可能的3色,其中I/O请求在其所有端都处于挂起状态简单回顾一下本节开头介绍的LossySync-FIFO1连接器的情况我们可以看到,对应的3-着色优先合并着色台114D. Clarke等理论计算机科学电子笔记154(2006)101一BC!见图9。 优先级路由器和着色利用上下文依赖性。不希望的替代方案是不可能的,因为颜色在节点B上不匹配:这些示例说明了如何使用3色设置中的I/O上下文的传播来解决优先级和LossySync通道上的上下文依赖性约束。然而,请注意,优先级不是全局决定的。连接器的不同部分所做的决定可能会使优先级变得无关紧要,甚至颠倒了决定--这完全取决于连接器。5走向分布式实现在本节中,我们将讨论如何将连接器着色用作Reo连接器分布式实现的基础。我们首先介绍一些的要求,这样的实现,然后简要概述了算法。最后,我们评估算法的要求作为标准。5.1推行选举事务处Reo的分布式实现必须满足以下要求:无全局视图在地理上分布式的环境中,Reo连接器的不同部分可能驻留在远程主机上。连接器状态的全局视图可能导致单点故障漏洞,并且维护一致全局视图所需的延迟可能会抑制物理分布式系统中固有的并行性。如果没有全局视图,连接器的组成部分对连接器只有有限的了解,并且必须将请求委托给连接器的其他部分,以便获得传输数据所需的信息D. Clarke等理论计算机科学电子笔记154(2006)101115通信基础设施和拓扑结构在Reo中,通道包含所有与通信相关的活动。由于通道为通信提供了唯一的基础设施,因此只有由通道互连(连接器拓扑)定义的路径才能用于发送确定Reo连接器的数据流所需Reo通道和节点对整个连接器上的数据流施加同步和排除约束。数据以原子方式通过连接器的“同步”部分传输。但是,通常需要整个连接器及其边界的状态来确定数据如何传输。一种确定数据流的方法是乐观地沿着信道发送数据,并且当不能满足同步约束时回滚任何改变。除了在每个信道上需要回滚能力(这在实践中可能不可行)之外,这种方法通常可能导致试图找到合适的数据流而浪费太多的资源这里优选的替代方案是预先计算可能的数据流的路由,然后,如果需要的话,非确定性地选择一个。在分布式环境中,多方可以同时与连接器交互。这意味着确定连接器数据流的多个计算可能处于活动状态,从而导致不同计算竞争连接器部分的如果不正确处理这些情况,这些并发数据流计算可能会面临竞争条件、活锁、死锁或简单地浪费资源。5.2一个算法我们提出了一个理想化的轮廓如何着色表可以在分布式设置中使用。该算法简单,依赖于现有的技术。因此,它可以用作评估优化和其他变化的正确性的基础。我们故意对锁定等问题保持模糊。我们正在进行的执行工作正在解决这些问题,今后的出版物将报告这些问题。该算法可以在连接器内的任何地方启动,例如通过I/O请求或节点,或者通常通过多个这样的方。(i) 计算着色表并分发给所有各方:在此步骤中,所有各方计算连接器当前状态的着色表,并确保每一方都有该表的副本。这属于在分布式网络中达成共识的问题[6]。在并行编程设置中,期望的算法116D. Clarke等理论计算机科学电子笔记154(2006)101称为全还原。 如果本地表是T1,.,T n,reduce计算T1·T2···Tn;all对应于将此信息发送给所有各方。 在实践中,依赖于操作符“统计”的属性,可以同时执行这两个步骤。(ii) 选择要使用的路线:计算的着色表可以包含0,1或多个着色。如果表中没有元素,则不会发生通信。参与方可能会延迟、超时、重试,并且新的参与方可能会加入-更改连接器的配置。如果表格中有一个元素,则选择该元素。如果存在许多可能性,那么原则上,当事人需要谈判选择哪条路线。这可以在阶段(i)中计算,只需对表中的条目进行排序并选择第一个。表中应不确定地放置数据。(iii) 发送数据:每个选定的数据源(写入/FIFO1缓冲器)可以在获得最终着色表后立即发送其数据。一个图元需要做出的所有选择都是由所选的颜色决定5.3评价该算法适用于每一方对其邻居一无所知的情况,除了如何找到它们(通过连接器的拓扑结构)。尽管连接器的拓扑结构可能会限制在计算着色表时可以利用多少并发性,但不同的各方可以并发计算。在任何数据流之前,计算着色表作为同步约束的解决方案。因此,我们认为,这些标准是满足的。5.4地位一个几乎功能齐全,但非分布式版本的Reo已经实现了基于目前的配色方案。我们的经验是,表不会变得很大,并且可以很快地计算,这表明这种方法确实是可行的。分布式实施正在进行中。6相关工作Reo能够使用很少的原始通道来定义具有复杂行为的连接器[2,4,5]。Reo的前身,即MoCha [7]和Manifold [8],没有像Reo那样施加同步约束,因此实现起来更简单,但表达能力较差对于选举事务办公室来说,存在着一些非正式和正式的模式。Reo的第一个操作描述[2]描述了存在和D. Clarke等理论计算机科学电子笔记154(2006)101117以上下文相关的方式在信道端不存在请求。然而,一个基于连接器提供和接受的价值观的操作模型被证明太难推理和实现。基于共归纳演算[5]和约束自动机[3]的语义模型为连接符及其表达能力的推理以及对其属性的机械验证铺平了道路。约束自动机模型的一个关键方面是自动机中的转换被标记为在给定步骤中同步成功的节点的集合,排除所有其他节点。基于连接器的配置计算这个集合正是连接器着色所实现的我们的模型具有更简单的新颖性,专注于关键的困难:它捕获了上下文相关的行为,其他语义模型没有。网络代数[9]为研究网络及其行为提供了一个通用的框架.我们希望我们的工作能够在这一框架内重新措辞,以便更好地与现有的各种工作进行比较。Bruni等人 [10]最近的工作提出了Community连接器的语义模型这显然类似于我们的2-着色方案,尽管我们在连接器中有两个循环和一个更大的原语集。据我们所知,这些语言和形式主义并不具有Reo中存在的通道所覆盖的表达范围,例如LossySync及其相当微妙的行为,也不需要或表达上下文依赖性,正如我们在本文中所解决的。另一方面,Milner例如,我们可以将两端连接到节点a和b的LossySync的2-着色行为建模为:.LossySync(a,b)=δ(Flow(a)×Flow(b)+Flow(a)):LossySync(a,b)对同一个LossySync的3色方案进行建模需要的不仅仅是简单地使用延迟算子(δ)。行动需要扩大还包括无数据流颜色,以便适当地传播它们编码的约束。LossySync的一种可能的编码如下,其使用NoFlow(b)和NoFlow(b)分别表示原因的给出和要求:.LossySync(a,b)=(Flow(a)×Flow(b)+流量(a)×无流量(b)+NoFlow(a)×(NoFlow(b)+NoFlow(b):LossySync(a,b)3 我们感谢一位精明的裁判提出这一意见。118D. Clarke等理论计算机科学电子笔记154(2006)101这个想法值得进一步研究。我们相信,我们的3-着色方案是新的,它可以形成协调模型的基础上,强制同步(和排斥)的约束的方式,取决于组件与协调层的相互作用的方式。7结论和今后的工作我们提出了一个模型的Reo连接器的基础上着色的连接器与可能的数据流的想法,以解决其(上下文相关的)同步和排除约束。一个更复杂的着色概念使模型能够捕获上下文相关的行为,这比早期的尝试更接近于Reo语义的非正式描述我们的模型易于使用,其“连接”操作满足有用的代数属性,使其成为Reo分布式实现的合适基础。该实现具有以对冗余鲁棒的方式并行计算数据流可能性的自由,因为可以组合多个部分计算。因此,我们的工作为Reo的实现和更精确的语义模型奠定了基础[12]。目前的工作有一些限制,我们打算在未来的工作中解决。首先,它没有解决Reo的所有这里存在两个困难:(1)不清楚如何实现隐藏以正确地保留Reo连接器的期望的可观察行为,特别是在存在具有上下文相关行为的通道的情况下;以及(2) 不清楚如何有效地处理数据敏感信道。其次,该模型产生不正确的语义连接器包含某些,但尚未定性,循环。有时候,模型会说数据会流动,即使没有源提供任何数据。在其他时候,它错误地给出了拖延的理由。在同步语言的上下文中也遇到了类似的问题[13]。我们希望,它们的解决办法将很容易适应我们的情况。引用[1] G. A. Papadopoulos , F. Arbab , Coordination models and languages , in : M.Zelkowitz(Ed.),《大系统工程》,《计算机进展》第46卷,学术出版社,1998年,第100页。329-400[2] F. Arbab,Reo:一个基于通道的组件组合协调模型,Math.Struct.in Comp.Science14(3)(2004)329D. Clarke等理论计算机科学电子笔记154(2006)101119[3] F.阿巴布角Baier,J. Rutten,M. Sirjani,Modeling component connectors in Reo by constraintautomata,in:Proceedings of FOCLASA 2003,a satellite event of CONCUR 2003,Vol. 97 ofENTCS,Elsevier Science,2004,pp. 25比46[4] F. Arbab , Abstract Behavior Types : A Foundation Model for Components and TheirComposition,Science of Computer Programming 55(2005)3[5] F. Arbab,J. J. Rutten,A coinductive calculus of component connections,in:Recent Trendsin Algebras Development Techniques : 16th International Workshop , Vol. 2755 of LNCS ,Springer-Verlag GmbH,2003,pp. 34比55[6] N. A. Lynch,分布式算法,Morgan Kaufman出版社,Inc.,一九九六年。[7] F. Arbab,F. S. de Boer,J. G. Scholten,M. M. Bonsangue,MoCha:基于移动通道的中间件,在:COMPSAC 667-673[8] M. M. Bonsangue,F. Arbab,J. W. de Bakker,J. J. M. M. Rutten,A. Scutella,G.萨瓦塔罗, 控制驱动协调语言流形的转换系统语义,Theor。Comput. Sci. 240(1)(2000)3[9] G. Stefa n escu,NetworkAlge b ra,Springer,2000.[10] R.布鲁尼岛兰尼斯群岛Monanari,无状态连接器的完整公理,在:计算机科学中的代数和余代数,卷。3629,Springer-Verlag GmbH,2005,pp.98比113[11] R.米尔纳,微积分的同步和同步。Theor. Comput. Sci. 25(1983)267[12] D.科斯塔角,澳-地Clarke,Intensional constraint automata(abstract),in Proceedings ofCALCO-jnr[13] G. Berry,The foundations of Esterel,in:Proof,Language and Interaction:Essays in Honourof Robin Milner,MIT Press,2000.
下载后可阅读完整内容,剩余1页未读,立即下载
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- BSC关键绩效财务与客户指标详解
- 绘制企业战略地图:从财务到客户价值的六步法
- BSC关键绩效指标详解:财务与运营效率评估
- 手持移动数据终端:常见问题与WIFI设置指南
- 平衡计分卡(BSC):绩效管理与战略实施工具
- ESP8266智能家居控制系统设计与实现
- ESP8266在智能家居中的应用——网络家电控制系统
- BSC:平衡计分卡在绩效管理与信息技术中的应用
- 手持移动数据终端:常见问题与解决办法
- BSC模板:四大领域关键绩效指标详解(财务、客户、运营与成长)
- BSC:从绩效考核到计算机网络的关键概念
- BSC模板:四大维度关键绩效指标详解与预算达成分析
- 平衡计分卡(BSC):绩效考核与战略实施工具
- K-means聚类算法详解及其优缺点
- 平衡计分卡(BSC):从绩效考核到战略实施
- BSC:平衡计分卡与计算机网络中的应用
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)