没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记142(2006)143-160www.elsevier.com/locate/entcs具有QoS的Gianluigi Ferrari1和 AlbertoLluch-LafuenteDipartimento diInformaticaUniversit`adiPisa摘要我们引入了一个简单的图形逻辑,支持应用程序的服务质量(QoS)属性的规范。我们的想法是,我们不仅对表示两个站点是否连接感兴趣,而且我们希望表达连接的QoS级别。 公式的求值 在图逻辑中,是表示公式的QoS等级的适当代数结构(c-半环)的值,而不仅仅是表示公式是否成立的布尔值。我们提出了一些例子,并简要讨论了我们的逻辑的表现力和复杂性。保留字:图逻辑,服务质量,半环,分布式系统。1引言图和图转换系统[19]是涉及并发、分布和移动性等问题的系统的合适形式这种系统的图形性质也出现在其他建模形式中,包括通信过程的代数[24],其中隐式通信结构可以被视为图。这些系统的属性主要涉及诸如时间行为和结构属性等方面,这些方面可以通过逻辑来表达,这些逻辑被用作形式验证方法的基础,如模型检查[12],这些方法在实践中已被证明是令人惊讶的有效[11]。*这项工作得到了欧洲研究培训网络SEGRAVIS和欧洲FET项目PROFUNDIS的支持。1电子邮件地址:giangi@di.unipi.it2电子邮件地址:lafuente@di.unipi.it1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2004.10.030144G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143当 考 虑 广 域 网 应 用 时 , 另 一 个 问 题 是 至 关 重 要 的 , 即 服 务 质 量(QoS)。QoS是指非功能方面,如网络带宽,时间响应或安全程度。一个明显的例子是服务覆盖网络[18](SON)。近年来,SON的概念作为一种灵活的机制来管理具有一定服务质量保证的网络服务的创建和部署中的复杂性,已经获得了极大的关注。SON从网间复杂性(诸如跨不同自治系统的分组路由)中抽象,并且将网络服务视为通过虚拟或应用级链路连接:覆盖网络。应用级链路对应于端到端因特网连接,并且与QoS参数相关联此外,服务功能与其服务水平协议(SLA)合同一起描述SON抽象的主要好处是对具有一定QoS保证的逻辑端到端服务基础设施进行建模。基于SON的应用开发需要进化的软件设计方法。标准方法通过带标签的有向图来描述SON架构,其中边的标签表示QoS保证并且节点的标签是SLA约束。许多研究工作采用图论模型来描述SON上的服务交付。看到[22]例如。然而,据我们所知,很少有人开发有效的验证技术来支持SON上应用程序的正式验证。一个具有挑战性的问题是提供以集成方式支持SON的行为和QoS属性的验证的正式机制本文为实现这一目标迈出了第一步在这里,我们阐述了一个逻辑框架,允许表达和原因的QoS属性的图。相关工作。我们的方法建立在以前的工作上,将时间逻辑扩展到非布尔域[23],以及对图的空间逻辑(GL)[8,15]的研究。图逻辑允许表达图的属性。Courcelle(例如见[14])对它们进行了详尽的研究,他的工作主要是基于图上的一元二阶逻辑(MS)及其片段。空间逻辑用于推理模型的结构,例如堆[26],树[9],进程演算[7,6]和图[8,15]。这种方法的共同概念是,如果存在模型组合的概念(如进程演算中的并行组合),则可以在相应的逻辑中推理通常的方法是通过复合运算符|其中φ|可分解为两个子模型的模型可以满足这一要求,G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143145一个满足φ,另一个满足φ。在图中,合成与MS中使用的边集上的二阶量化密切相关。事实上,GL的无定点片段的表达能力已被证明包含在MS中[15]。另一方面,完整的逻辑能够表达MS中不太可能表示的属性[15]。GL是否包含MS是一时态逻辑支持对系统在时间上的行为进行推理例如,人们可以问某个事件是否从未发生过,或者某个事件是否经常发生时态逻辑通常以布尔方式在变迁系统上解释,即。公式的求值是真或假。然而,一些现有的方法在更一般的域上解释时态逻辑,如布尔代数[10]或概率[16]。还有大量的关于系统分析和验证的工作,重点是概率和时间。我们引用CSL [1]的工作,这是一种结合这两个方面的逻辑与这些工作相反,我们并不专注于时间或概率等具体问题,而是考虑通过适当的代数结构来抽象表示QoS更确切地说,我们自己对定量时态逻辑领域的贡献在[23]中描述,我们提出了时态逻辑,如在约束半环上定义的μ-演算,这是QoS的一种形式约束半环(C-半环)是由一个定义域和两个满足某些性质的加法和乘法运算组成的代数结构其基本思想是,前者用于选择价值,后者用于组合价值。已经提出了不同种类的半环来建模成本,例如代数路径问题中的闭半环[27]或用于不同应用的(max,+)代数[21]。C-半环是一种特殊的半环,它足以捕获实际中使用的大多数重要QoS属性。它们最初被提出作为描述和编程软约束问题的合适结构[4],包括安全协议的分析[3]。该方法的基本思想是利用半环的加法运算投射约束,利用乘法运算组合约束。贡献本文介绍并分析了定义在c-半环上的简单图逻辑的性质。特别地,我们扩展了[15]的空间逻辑这种逻辑的选择主要是出于最近对空间逻辑的兴趣。然而,我们提出的大多数想法也可以应用于其他图形逻辑我们引入了将c-半环值与ver-半环值相关联的函数146G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143图的点和边逻辑常数和连接词被c-半环常数和函数取代结果,在扩展逻辑中公式的评估是c-半环的值,表示公式的QoS保证,而不仅仅是表示公式是否成立的布尔值。例如,我们可以在图中表示最优路径的QoS,而不是在图中表示某条路径的本文的主要技术贡献是逻辑的定义我们展示了如何通过一个运行的例子来表达属性:箭头分布式目录协议[17],它确保了对分布式系统中移动服务的我们的逻辑的复杂性和表现力属性进行了讨论,在一个非正式的方式。结构第2节通过一个例子介绍了我们的动机。描述图、c-半环及其性质的技术背景包含在第3节中。第四节给出了我们的逻辑的语法和语义以及一个例子。下一节概述了我们的方法的潜在应用。最后,我们总结了本文的未来研究方向。2Arrow分布式目录协议箭头分布式目录协议[17]是一个解决方案,以确保独占访问分布式系统中的移动对象。该分布式系统被给定为无向图G,其中顶点和边分别表示节点和(可靠)通信链路。成本通常与链接的方式,并假设一个最佳路由的机制。该协议使用G的最小生成树T。每个节点都有一个箭头,粗略地说,箭头指示对象所在的方向如果一个节点拥有箭头指向它自己的对象,我们说箭头和节点都是终端。由箭头导出的有向图称为L。粗略地说,该协议通过传播请求和更新箭头来工作,以便在任何时候箭头都指向拥有该对象或等待该对象的更准确地说,协议的工作原理如下:最初L被设置为使得每条路径都指向拥有对象的节点。当节点u想要获取对象时,它向a(u)发送请求消息find(u),箭头的目标从u开始,并将a(u)设置为u,即它成为终端节点。当箭头不指向自身的节点u从节点v接收到find(w)消息时,它将消息转发到节点a(u)并将a(u)设置为v。另一方面,如果a(u)=u(对象不一定在u处,但将在G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143147v0 一v4一v2一v3一一v1HOv5一v4一v3一v5如果没有接收到),则如前一种情况一样更新箭头,但是这次请求不被转发而是被排队。如果一个节点拥有这个对象,并且它的请求队列不为空,它会将这个对象发送到它的队列中的(唯一的)节点u,并向v发送一个move(u)消息。这条信息最好能通过G.协议的正式定义可以在[17]中找到。因此,该协议在SON上工作,SON提供不同的服务:通过最小生成树的链路发送请求和交付对象。每个服务都有一个相关的QoS。例如,每个传播链路可能具有延迟,而对象的递送可能具有价格。aa图1.一、目录的两种状态:初始状态(左)和在v3处理来自v4的请求之后(右)。图1说明了协议的两种状态。 节点v1,..,V5和对象O由顶点表示。箭头由标有a的边表示。从对象到节点的h标记边表示该节点具有object.为了简单起见,没有描绘协议的其他边缘,如表示对象的递送的那些边缘左边的状态是初始状态:节点v1拥有对象,箭头所指示的所有路径都指向它。图中右边的状态是三个步骤的结果:1)节点v4通过其箭头发送对对象的请求; 2)v3通过正确地更新箭头来处理它,即箭头现在指向V4而不是V2;以及3)节点V4接收请求并更新其箭头。该协议已被证明有一些属性。第一个[17,定理5]如下所述:属性1在目录的每个状态下,从任何节点由非终结符箭头诱导的最大路径都是唯一的,并且总是指向对象的所有者或请求它的节点(waiter)。这一特性涉及空间和时间方面。它要求在协议的每个状态中都存在某种路径,但它没有说明v0 一v2一v1HO148G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143QoS属性。注意,该算法在SON上工作,其中每个服务可以以特定的QoS来提供因此,我们可能对QoS的推理感兴趣,例如,在指定这样的路径的成本3预赛3.1C半环我们的逻辑定义在c-半环的域 我们首先给出定义,并将其背后的直觉推迟到下一行展示一些例子。形式上,一个c-半环是一个元组A,+,×,0,1,使得:• A是集合;• 0和1是A的元素;·+:2A→A定义为A的最小值的最小(p<0>0如下3:{a}=a,n=0,A=1,且(Ai)={Ai},Ai<$A,i≥0;• ×:A×A→A是在+上分配的二元结合交换运算,单位元素为1,吸收元素为0事实上,+是在元素集合上定义的,自动假定它是结合的,交换的和幂等的。此外,可以证明它具有0作为单位元素和1作为吸收元素[4]。 其他地区 本文中,我们假设×也定义在有限序列上,并使用符号在post fix notation中。大多数在实践中使用的c-半环满足这一点。为了增强可读性,运算+被称为加法运算,而×被称为乘法运算。注意,我们使用粗体+和符号×,以避免与实数上的加法和乘法运算混淆(+和·)。实例和QoS应用。C-半环是许多QoS属性的形式结构举例来说• 布尔c-半环<${true,false},<$p,<$p,false,true<$p可以用来对网络和服务可用性建模。• 最优化c-s环<$R+,min,+,+∞,0∞与热带c-s环N+,min,+,+∞,0适用于较宽范围的速率、速率或传播延迟。3当+与两个元素一起应用时,我们使用+作为一个二进制变量,以便在内部固定符号,而在所有其他情况下,我们使用前缀符号。G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143149• 带宽可以用max/min c-半环来形式化,该半环由y∈R+,maxx,min,0,+∞∞给出。• 性能可用概率c-半环表示[0, 1],max,·, 0, 1]或模糊值[0, 1],max,min, 0, 1]。• 基于集合的半环(2N,N,其中N是一个集合)可以用来表示能力和访问权限。• 安全度通过c-半环[0,1,.,n],max,min,0,n,其中n是最大安全级别(未知),0是最小安全级别(公开)[3]。C-半环与格c-半环的加法运算导出一个偏序如下:a≤Sb i <$a + b = b。例如,在优化c-半环中,≤S对应于算术关系≥.我们可以证明≤S确实是一个偏序,+,×在≤S上是单调的,0和1分别是≤ S的最小和最大元素,并且<$A,≤S<$A是一个完备格[4]。在c-半环的某些例子中,乘法运算是幂等的。这意味着,除其他事项外,+分布在×和<$A,≤S<$是一个分配格[4]。逻辑和模糊c-半环就是一个例子,因为逻辑析取是幂等的,即p=p。相反,优化和概率c-半环的乘法运算,即实数的加法和乘法不是幂等的。在大多数情况下,就像所有给出的例子一样,<$A,≤S<$是分配的。C-半环中的否定C-半环一般没有求补或求反算子。例如,考虑经典的德·摩根否定,即:双射算子-.:A→A,. 对于所有a∈A(in解),有-a∈A和--(a) =a,且-{AJ}={-a|a∈AJ}。对于所有AJA(DeMorgan)且a≤b惠-b≤-a(反单调性),其中和。是最低的上限和最大的格的下界算子<$A,≤S<$. 不可能为热带c-半环定义一个德摩根否定。假设相反,设n为−1。通过反单调性−(n+ 1)<1,但这仅在n= +∞时才可能,这意味着−1 = +∞。由于−0 = ∞,−不是双射。然而,其他的c-半环(fuzzy,boolean,max/min)可以配备一个否定,在大多数情况下导致布尔代数。150G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143C-半环的合成基于C-半环的方法在处理多个QoS标准的问题时具有独特的优势事实上,证明了c-半环的笛卡尔积、指数和幂构造都是c-半环。因此,相同的概念和算法可以一次又一次地应用C-半环的霍尔幂域是一个特别有趣的问题,因为它可以使我们形式化多准则优化问题。C-半环的笛卡尔积不足以解决这类问题。问题在于,在笛卡尔积中,原始c-半环的值是独立组合解决方案是使用各种优化c-半环的笛卡尔积的霍尔幂域,如[ 5 ]中所解释的。直观地说,霍尔幂域适用于非支配值的集合。3.2图表。[8]中的图是由合适的代数[13]中的项描述的,但我们更喜欢使用受Cour-celle [14]使用的关系结构启发的表示。设X和E分别是节点和边的有限集合。进一步设C是一个c-半环,K是将每条边与c-半环的定义域的一个值相关联的函数E→A的另外,设F是包含所有c-半环函数Ai→A,i≥0的论域.集合F还包含作为零进函数的常量名称。一个图是一个元组X<$E,边,C,K,I<$,其中X<$X,E<$E,K<$K而edge:E→X×X是一个函数,它将一个边e与它的源相和目标顶点。 函数I:(K<$F)→(E→A)<$i≥0(Ai→A)为解释,即分别映射成本和c-半环函数名与实际成本和c-半环函数。集合X和E当然是不相交的。在本文的其余部分,我们只考虑有限图,即X和E是有限的图,我们将用G(X,C,K,I)表示所有具有集节点X、c-半环C、函数集K和解释I的图的集合,或者如果X、C、K和I从上下文中是清楚的,则仅用G表示图G的一个分解是一个有序的图对,它们具有相同的节点、c-半环、代价函数和解释,但具有不相交的边集,这些边集一起形成原始边集。更精确地说,G=<$X<$E,edge,C,K,I<$的分解是一个(有序)图对G1=<$X<$E1,edge1,C,K,I<$,G2=<$X<$E,edge2,C,K,I<$,使得E1E2=E边1边2=边。图G的所有分解的集合将被表示为Θ(G)。不难看出,Θ(G)的大小为2 |E|.G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)1431513.3Example.箭头分布式协议的每个状态由图G=X集合E包括箭头、对象发送服务、对象所有权和队列的边。C-半环C可以包括不同的QoS方面。第一个是节点的恒等式,可以用基于集合的c-半环C0= 2X,,,,X来建模。然后我们需要对边缘进行建模。假设N={a,h,s,q}是所有边缘类型的集合,其中a,h,s和q代表箭头,所有权、对象发送和队列。然后我们定义一个基于集合的c-半环C1=<$2N,<$,N<$。我们可能有传播链路有一定的延迟,我们用优化c-半环C2表示。发送对象可能需要付出代价,用热带c-半环C3表示。因此,C被定义为PH(C0×C1×C2×C3),即C0、C1、C2和C3的笛卡尔乘积的霍尔幂域。K的成本函数旨在将这样的QoS属性与边和节点相关联。注意,如果一条边或弧没有基本属性(类型、延迟或奖励),函数必须将top元素与该属性相关联。例如,我们需要一个函数成本来关联箭头和发送边与它们的QoS。箭头有类型和延迟,但没有价格或节点名称。因此,cost:E→A与每个箭头边关联一个值{(X,a,d,0)},对于某个实数d。为了简化,我们假设有一个成本函数来表征每种类型的弧。更确切地说,我们认为有函数a,q,s和o。例如,如果边e的类型为a,则a(e)返回1否则为0。4C-半环上的图逻辑一旦固定了我们的QoS概念,我们就提出了我们的逻辑。 我们首先描述语法和语义,提到与[ 15 ]的图的空间逻辑的一些差异。然后,我们展示了一些如何表达我们的例子的一些QoS属性152G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)1434.1语法.令VX是节点变量的集合,VR是递归变量的集合。图逻辑的公式由以下文法中的φ生成φ::=零 | k(k) | k(n,n)|φ|φ|φ<$φ空间算子φ+φ|φ×φ|f(φ, . . ,φ)c-s-emiring算子Σx.φ |x.φ量化r(γ) |(µr(x).φ)|(νr(x).φ)零点其中x∈ X,x∈VX,n∈ X <$VX,k∈ K,f∈ F,r∈VR。 在φ的最后三项中,φ和x是向量,我们分别要求|R|为|ξ|、|为|ξ|为|X|和r(n)作为单调函数的操作数或在偶数个反单调函数下出现。|and r (ξ) to occur as operand of a monotone function or under an evennumber of antimonotonic functions.在对我们的逻辑的语义给出形式定义之前(这将在下一节中进行),我们先对不同的句法要素给出一个直观的认识利用nil,我们刻画了没有边的图,k(n)和k(n,n)是用于表示节点和边的成本 φ1|φ2我们在所有图的分解(G1,G2)乘以φ1在G1中的求值和φ2在G1中的求值。对所有这些值应用加法运算。空间运算符||是关于+和×的对偶。节点量化计算每个节点x的φ,然后使用+或×。 最后,c-半环运算有一个简单的解释,fixpoints具有通常的含义。我们强调了与[15]的空间逻辑的一些差异。代替布尔常量和连接词,我们有c-半环常量、算子和函数。 边存在性用函数k来丰富,该函数k分配这是一个很好的选择。Costfunc tionscanaliedo n odedo n ode s e donoded o n o d edo n od e d o n o d e d o n量化器符号由相应的量化器代替,,和不可导的运营商,如显式地介绍,因为我们不能假设存在一个否定运营商,提供了通常的导子。我们的逻辑不包括名称相等,因为它可以通过c-半环函数来完成 它将节点名称视为QoS属性,并包含用于表示和比较名称的c-半环函数。我们忽略了标签的显式表示,更倾向于将边标签建模为QoS属性(就像我们在示例中对边类型所做的那样)。因此,我们不包括标签量化。G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143153Σ(Ⅲ)4.2语义我们将公式解释为从图的集合G到c-半环A的域的映射。设σ:VX→X表示将节点变量映射到节点4的名称和标签环境,设ρ是将递归变量映射到函数G →A的通常命题环境。由于符号的滥用,我们让环境应用于实际的名称和映射从而得到恒等式,我们使用后缀表示法来解释它们的应用。公式的解释如下:<$nil)σ;ρ(G)=E=ερ(G)=(<$σ∈X)×I(k)(xσ)ρ(G)=(E={e})×(edge(e)=(<$1σ,<$2σ))×I(k)(e)¢φ1|φ2)σ;ρ(G)=(G1,G2)∈Θ(G){φ1)σ;ρ(G1)×φ2)σ;ρ(G2)}<$φ1<$φ2)σ;ρ(G)=(G1,G2)∈Θ(G){<$φ1)σ;ρ(G1)+<$φ2)σ;ρ(G2)}φ1+φ2)σ;ρ(G)=φ1)σ;ρ(G)+φ2)σ;ρ(G)φ1×φ2)σ;ρ(G)=φ1)σ;ρ(G)×φ2)σ;ρ(G)f(φ1,.,φ n))σ;ρ(G)= I(f)(φ1)σ;ρ(G),.,<$φ n)σ;ρ(G))<$κx.φ)σ;ρ(G)=κx∈X<$φ)σ;ρ(G)<$r(G))σ;ρ(G)=rρ(G σ)ρ(G)= lfp(λs.λy. <$φ)σ[y/x],ρ[s/r])(<$σ)(G)ρ(G)= gfp(λs.λy. φ)σ[y/x],ρ[s/r])(φ σ)(G),Σ其中κ∈ {, }。 右边的所有项都在C上解释。例如,如果<$σ是X的元素,则<$σ∈X返回1,否则返回0。可以证明Xi →(G →A)型的点序全函数的集合Ri是完备格,或者更一般地说是c-半环。它也可以表明,与上述句法限制功能,λy。φ)σ[y/x],ρ[s/r]在≤S上是单调的. [28]这是一个很好的定义。此外,如果函数λs.λy.φσ[y/x],ρ[s/r]关于H连续,H,可以应用定点迭代。请注意,有些公式的值仅为0或1。在某种程度上,它们允许我们包括布尔推理。例如,如果图没有边,nil就是1,否则就是0。另一方面,像k(k)或k(k1,k2)这样的4VX,X必须不相交。5 回忆c-半环形成完备格[4]。154G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143(2)返回与对应节点和边相关联的成本(如果它们存在于图中)。更精确地说,如果边的集合不是在σ1σ和σ2σ之间的边,则k(σ1,σ2)为0。否则,它通过函数k计算与图的唯一边相关联的成本。组成φ1|φ2解释如下。一个看每一个可能的图分解成两个图G1和G2。G1中的φ1和G2中的φ2的求值使用×组合。然后使用加法运算将我们从所有分解中得到的一组值举一个简单的例子,假设我们想在从节点x到节点y的图的边中找到最优QoS。假设边的QoS由函数k给出。我们需要的公式是k(x,y)|1 .一、注意k(x,y)(G1)× 1(G2)是0,如果G1是空的或有两条以上的边. 因此很容易看出,k(x,y)|1是来自x的所有边的QoS的相加到Y。为了说明另一种形式的组合的使用,假设我们想要将图的QoS度量为图的所有边的QoS的组合,图表。为此,我们写出公式(nil+(nil|nil)+k(x,y))||0的情况。请注意,如果将分解应用于空图(nil)或具有多条边(nil)的图,则分解的左侧部分的值为1|零)。如果图由一个边组成,则该项评估为该边的QoS。因此,(nil+(nil|nil)+k(x,y))||0是图的所有边的QoS的乘积。其余公式背后的直觉应该是清楚的:c-半环运算和函数有一个直接的解释,量化将加法或乘法运算应用于公式的求值,对于x被图的节点的每次替换最小和最大点fixpoint使用多个递归变量,并具有通常的含义。除了我们将公式解释为c-半环的值之外,与[8]的空间逻辑的主要语义区别在于,这里的量化是在图的节点集合X上完成的,而不是在节点名称X的无限集合上完成的。这并不影响GL中的可判定性,因为人们确实可以看到有限的节点集[15]。这不符合我们的逻辑因为我们允许像x.k(x)这样的公式,它可能需要检查所有节点。另一个不同之处在于,在原始逻辑中,分解是在所有分解上量化的,而不仅仅是像我们这样保留节点和标签集的分解。很容易看出,在原始逻辑中,这并没有什么区别,因为人们无法区分不连通的节点和不在图中的相反,我们的逻辑允许这样做,因为我们发现做出这样的区分是有趣的。G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143155Example.现在让我们简单地说明如何表示我们的激励示例的属性1,即由非终结符箭头诱导的最大唯一路径要么通向对象的所有者,要么通向请求它的节点。该属性是纯布尔的,可以使用[8]的空间逻辑来表达它。虽然不需要使用递归,但我们将使用它来使用尽可能多的逻辑成分。我们首先展示如何声明两个节点之间存在一条箭头路径Σpath(x,y)µr(x,y). (x = y)+z。a(x,z)|r(z,y)。这个公式背后的直觉是:如果x恰好是y(x=y),则在图中存在从x到y的路径,或者图可以分解为两个子图,例如在一个子图中,我们从x到z是一条路径。在另一个子图中,存在从z到y的路径(z. a(x,z)|r(z,y))。在我们的例子中,我们感兴趣的路径结束于终端节点,即。一个没有自我意识的人。但在此之前,我们为一个模型定义了一个焦点,说明一个d没有任何其他边:out0(y)n(x.a(y,x)|1)=0的情况。 注意x.a(y,x)|1在具有从节点向外的箭头的图中是1y. 因此,我们要求该表达式的值为0。现在我们可以用t(x)来表征终端节点,|out 0(x),即只有一个传出自箭头的节点。我们想要表达的路径类型必须是唯一的,也就是说,从路径的每个节点传出的转换数必须是1(除了最后一个节点)。因此,我们有:ΣUMP(x,y)µr(x,y). (x=y)×t(y)+z. a(x,z)|(out 0(x)× r(z,y)),其中UMP代表唯一最大路径。最后,我们可以声明,对于每个节点,这样的路径都存在,并以拥有对象或等待对象的节点结束:Σ财产1美元x.y. (ump(x,y)×(所有者(y)+服务员(y))|第一章换句话说,对于每个节点x,都有一个节点y,这样我们就有了从x到y的唯一的终端箭头路径,它是拥有对象的节点(所有者(y))或不是所有者的终端节点(等待者(y))。缩写:owner(y)是t(y,y)×o(y,o),waiter(y)是t(y,y)×(所有者(y)=0)。我们现在扩展属性1以包括QoS方面。我们现在可以推断路径的QoS属性,而不是路径的存在Σcostp(x,y)<$µr(x,y). (x = y)+z。(a(x,z)×156G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143cost(x,z))|r(z,y)G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143157注意,相对于路径唯一改变的是引入成本函数cost(x,z)。其余的都一样。事实上,该公式结合了布尔方面来表征路径和QoS方面。该公式应该直观地解释如下:如果x和y是相同的节点,则从x到y的最优路径是0,或者是从x到节点z的边的成本与从z到y的最优路径的成本的组合。注意,通过分解来表达最优路径是可能的,因为我们使用c-半环,即因为乘法运算分布在加法运算上。现在,我们可以将这个公式与定义的公式结合起来,以描述正确的路径。从而得到表示唯一最大箭头路径的QoS的公式:costump(x,y)costump(x,y)×costp(x,y)回想一下,属性1需要一个路径来指向对象所有者或服务员。因此,我们可以考虑与获取对象相关联的QoS属性现在我们可以写出以下公式:costump(x,y)×(cost(y,x)× sending(y,x))|第一章4.3计算语义。我们非正式地讨论评估我们的公式的问题首先,在考虑复杂性问题时,我们像往常一样从c-半环运算的复杂性中抽象出来[20],因为这取决于实际的c-半环实例。举个例子,一个定义域无限的c-半环的幂集结果是一个c-半环,其中定义域的元素可能在有限集合中。存储和操作这些元素可能是不可行的。我们首先考虑逻辑的无定点片段。计算nil、k(n)和k(n,n)可以在恒定时间内完成。最复杂的计算之一与合成有关。事实上,加法和乘法组合需要枚举图的所有分解,从中可以得到在图的边数上是指数级的。节点量化需要枚举有限集合X。因此,很容易看出这个逻辑片段是可判定的。我们的逻辑包含了图[8]的空间逻辑的一个片段,其中模型检查问题已被证明是PSPACE完全的[15]。因此,我们的逻辑是在PSPACE中,并且我们推测,如果我们从c-半环的复杂性中抽象出来,那么我们的逻辑的无定点片段的模型检查是PSPACE完全的我们的方法的主要缺点是关于完整的逻辑,因为定点迭代可能是不可行的。例如,这个替代公式158G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143计算两个节点之间的最优箭头路径的QoSΣcostp '(x,y)<$µ r(x,y). (x = y)+z。(a(x,z)×cost(x,z))|1)× r(z,y)很容易看出,如果我们给定一个有圈的图,两个节点x,y使得y不能从x到达,一个优化c-半环则求值costp'(x,y)可能需要无限次迭代才能返回+∞,即c-半环的底部。然而,注意,这在原始公式costp中不是问题,因为递归变量在那里作为复合的操作数出现。因此,定点迭代必须在有限步之后结束;初始图是有限的,每次迭代都删除一个弧。限制递归的使用,使得递归出现在组合内部,其中另一端仅在空图中计算为0,这将保证定点迭代终止。这种句法限制是否意味着表达能力的重大损失,这是一个悬而未决的问题我们仍然没有找到一个可以用定点公式表示的属性,其中递归不作为复合的操作数出现,不能用满足限制的公式表示直觉上,在递归公式中不止一次考虑一条边5进一步的应用。基于约束的路由[29]是我们逻辑的一个有趣的应用领域该问题通常是寻找满足某些约束的最优路由,其中优化和约束准则都涉及QoS特性。例如,人们对优化带宽和价格感兴趣,同时要求总延迟小于或等于某个值。关于这些问题的调查,我们参考[29]。这些问题中的各种问题将一些QoS属性优先于其他QoS属性。例如,最短-最宽路径的目标是在具有最佳带宽的在这种情况下,隐式QoS结构可能不会形成c-半环。这就是最短-最宽路径问题。这个问题的解决方案是在第一步中忽略优先级,并使用Hoare Power Domain优化所有QoS属性公式的求值将是一组非支配元组,可以根据优先级从其中基于约束的单播路由优化的表达式有一个朴素的解决方案。设path(x,y)是表征从节点x到节点y的路径的图的公式,设cost是表示图中所有弧的成本的乘积的公式,并且设c是路径上的全局QoS约束,即,路径允许的最大QoS级别注意G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143159不等式可以看作是F中c-半环函数的一部分。所需公式为:(path(x,y)×cost×cost ≥c)|1该公式提出了一种表达图约束优化问题的一般模式• 定义一个刻画有效图的公式p• 定义一个公式q,将QoS级别分配给图(不一定是所有边成本的乘积)。• 定义一个公式r来约束图的QoS(不一定是图的QoS水平的全局约束• 所需公式为(p × q × r)|1 .一、虽然此模式允许以相当直观的方式表达此类问题,但结果公式的实际计算可能非常低效,主要是由于公式中的冗余和组合的嵌套观察模式背后的直觉是,枚举图的所有子图,并选择满足所需属性和约束的最佳子图。 在某种程度上,这是一种蛮力规范。在某些情况下,可以避免冗余例如,结合了路径表征和成本表达,C-半环的分配性质,以有效的方式使用递归6结论.我们扩展了一个具有QoS属性的图的空间逻辑,其形式结构是一个c-半环。我们的逻辑公式的评估不仅仅是一个布尔值,而是c-半环的域的值,表示与图相关联的QoS水平。我们已经展示了我们的逻辑如何用于表达图的常见QoS属性,如最优约束路由或最小生成树,集中在分布式协议的示例中,使用相当直观的设计模式。不幸的是,由此产生的公式可能导致计算效率低下在目前的工作中,我们正试图建立公式为常见的QoS问题,避免这样的问题。我们也在研究我们逻辑的复杂性和表现力。主要问题是定点的计算。一般来说,不动点迭代不能保证在有限步数内终止句法限制可以确保终止,但确定由于限制而导致的表达性损失是否显著是一个悬而未决的问题。我们还计划精确地分析我们的逻辑的潜在应用,160G. 费拉里,A.Lluch-Lafuente/Electronic Notes in Theoretical Computer Science 142(2006)143SON系统的领域,并将我们的概念扩展到包括QoS,时间和空间方面的逻辑。这是一个有趣的途径,可以让我们在图转换系统(粗略地说,状态是图的转换系统)中推理QoS表达和验证图转换系统的布尔属性的方法已经存在,例如。[25,2]并可以作为我们的目的的灵感。引用[1] Baier,C.,B. Havekort,H.赫尔曼斯和J. -P. Katoen,通过瞬态分析进行连续时间马尔可夫链的模型检查,在:计算机辅助验证,LNCS1855,2000,pp.358-372.[2] Bald an,P. 、杨A. COR A D IN I,B. Küonigan d B. K?nig,Verifyingabehaveorlogicfororrraphtransformation systems,in:CoMeta[3] Bella,G.和S.Bistarelli,分析安全协议的软约束程序设计,逻辑程序设计的理论与实践。[4] Bistarelli,S.,联合Montanari和F. Rossi,基于半环的约束满足和优化,ACM杂志44(1997),pp.201-236[5] Bistarelli,S.,联合Montanari和F. Rossi,Soft constraint logic programming andgeneralized shortest path problems,Journal of Heuristics8(2002),pp. 25比41[6] 凯尔湖和L. Cardelli,A spatial logic for concurrency(Part II),in:Proceedings of the13th International Conference on Concurrency Theory(2002),pp. 209-225[7] 凯尔湖和L. Cardelli,一个并发的空间逻辑(第一部分),Inf.Comput。 186(2003),pp. 194-235。[8] 卡尔代利湖,Gardner和G. 一种用于查询图的空间逻辑,在:P.W.等人,编辑,ICALP597-610[9] 卡 尔 代 利 湖 ,
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- C++多态实现机制详解:虚函数与早期绑定
- Java多线程与异常处理详解
- 校园导游系统:无向图实现最短路径探索
- SQL2005彻底删除指南:避免重装失败
- GTD时间管理法:提升效率与组织生活的关键
- Python进制转换全攻略:从10进制到16进制
- 商丘物流业区位优势探究:发展战略与机遇
- C语言实训:简单计算器程序设计
- Oracle SQL命令大全:用户管理、权限操作与查询
- Struts2配置详解与示例
- C#编程规范与最佳实践
- C语言面试常见问题解析
- 超声波测距技术详解:电路与程序设计
- 反激开关电源设计:UC3844与TL431优化稳压
- Cisco路由器配置全攻略
- SQLServer 2005 CTE递归教程:创建员工层级结构
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功