没有合适的资源?快使用搜索试试~ 我知道了~
非单调软并发中的SLA协商
理论计算机科学电子笔记236(2009)147-162www.elsevier.com/locate/entcs一种用于SLA协商的非单调软并发Stefano Bistarellia,c,1 Francesco Santinib,c,2aDiartimentodiScienze,Universita`“G. dbIMT Lucca-高级研究学院,意大利卢卡cIstituto di Informatica e Telematica-CNR,意大利比萨摘要我们提出了一个扩展的软并发约束语言,允许约束存储的非单调为了实现这一点,我们引入了一些新的操作:retract(c)将当前存储减少c,updateX(c)事务性地放松存储中处理集合X中变量的所有约束,然后添加约束c;nask(c)测试c是否不被存储所蕴涵。我们将此框架作为资源管理(例如Web服务和网络资源分配),其需要给定的服务质量(QoS)。所有各方的QoS要求应该通过协商过程,在定义为服务水平协议的正式协议上收敛,该协议指定必须执行的合同C-半环是我们用来建模QoS度量的代数结构关键词:软约束逻辑规划,非单调性,服务质量,服务水平协议1动机许多现实生活中的问题需要计算机制,这是非单调的性质。例如,考虑客户端需要预留一些资源的日常场景,并且服务提供商必须分配那些资源,同时提供期望的服务质量(QoS)。谈判[14]是一个过程, 一组代理人在他们自己之间进行通信,并试图就某个问题达成双方都能接受的协议。 实现这一目标的手段包括放弃让步和撤回建议。当代理是自主的并且在运行时尝试合作/协调时,自动协商代表了一个复杂的过程[14]。请注意,这个过程必须是动态的,因为客户端和提供者可以在执行过程中更改他们的需求1电子邮件:bista@sci.unich.it和stefano. iit.cnr.it2电子邮件:f. imtlucca.it和francesco. iit.cnr.it1571-0661/© 2009 Elsevier B. V.根据CC BY-NC-ND许可证开放访问。doi:10.1016/j.entcs.2009.03.020148S. Bistarelli,F.Santini/Electronic Notes in Theoretical Computer Science 236(2009)147×为了对自动协商进行建模和管理,本文提出了非单调软并发约束(nmsccp)语言,它扩展了软并发约束编程(sccp)[3,7],以支持约束库的非单调演化。在经典的sccp中,告诉和询问代理可以配备一个偏好(或一致性)阈值,用于确定它们的成功、失败或暂停:只有当存储对于阈值来说是“足够一致的”。 由于约束只能累积(通过tell操作),因此该一致性级别只能从初始空存储开始单调递减:用于组合的函数 的约束,即半环的,是密集的[6]。 为了更进一步,我们支持- 提出一些新的动作,为用户提供显式的非单调操作,这些操作可用于从存储中收回约束(即,更新和收回),以及特定的询问操作(即,nask),仅在当前存储启用时启用不需要给定的约束。nmsccp语言与经典的sccp有两个主要区别:i)存储的一致性水平可以通过收回约束(即,它不是单调的),和ii)由于悬挂物的非单调性,一些故障在悬挂中转换。根据i),我们已经扩展了动作的语义,以包括存储一致性的上界(例如,因为它可以通过收回来增加),以便也修剪在给定步骤处获得的“太好”的计算。通过这种方式,现在我们能够对可接受性的区间进行建模,而在sccp中,只有对“不够好”的计算进行检查,即降低太多的一致性相对于下限阈值。这导致ii):在sccp中,如果结果存储相对于阈值(即给定的半环值或软约束)不够一致,则代理失败;在nmsccp中,同一代理简单地挂起等待当前存储的可能一致性增加,这启用了挂起的动作。我们将这些扩展应用于模型服务水平协议(SLA)[2,15]及其谈判:软约束表示代理对交易资源的需求,并且存储的一致性值表示对当前协议的反馈。换句话说,所有的要求在多大程度上是一致的,或者说,满足了多大程度的总体满意度。动作上的阈值用于检查偏好值的这个区间,并且具有不是普通的“是或否”(即,真或假,如在明确的约束中)的反馈值显然更有信息性。使用软约束(例如 此外,成本模型非常适用于特定问题,因为它是所选半环的参数,并且其语义直接嵌入需求定义本身(即约束)和对Agent建模的语言(例如,告诉和收回动作的阈值)。本文的其余部分组织如下。节中2、概述了背景资料。秒3.非单调语言的特点,其运算S. Bistarelli,F.Santini/Electronic Notes in Theoretical Computer Science 236(2009)147149≤≤≤∈≤ ⟨ ≤ ⟩≤×≤≤××∈⟨ ×⟩语义以及如何管理一致性间隔。节中4我们展示了如何使用语言来表示偏好驱动的谈判。最后,SEC。5显示了相关的作品和SEC。6最后指出了未来的研究方向。非单调扩展的相关工作。这项工作的灵感来自[9]和[11]:在[11]中,作者提出了一个并发约束编程(ccp)的非单调框架[20],并结合其语义。我们的nask和更新操作(参见第3)是[11]中描述的那些的软版本,而atell,仅当它与商店一致,可以用经典的(有价值的) 关于SCCP 像我们的nask这样的否定询问也在[19]中描述。 细粒度删除约束的想法(第二节中的撤回)。3)来自于[9],它描述了CCP的一个不同的非单调框架。它的主要目的是不增加任何额外的非确定性(除了选择操作),通过跟踪在同一并行计算中的约束之间的依赖关系,否则的非单调进化可能会产生不同的结果,如果执行不同的调度策略。然而,在我们的语言中,我们决定允许这种非确定性,因为我们相信在开放系统中的协商交互期间体验这种行为更自然。在[13]中给出了ccp中约束存储的非单调演化的其他例子, 通常称为线性并发约束规划。2背景吸收半环一个吸收半环[5] S可以表示为A,+,0,1元组使得:i)A是一个集合,0,1A; ii)+是交换的,结合的,0是它的单位元; iii)是结合的,分布在+上,1是它的单位元,0是它的吸收元。此外,+是幂等的,1是它的吸收元,并且是交换的。让我们考虑A上的关系S,使得aSbi ≠ a+b=b。然后可以证明(见[6]):i)S是偏序; ii)+和在S上是单调的 ; iii)0是它的最小值,1是它的最大值; iv)A,S是完全格,对所有a,bA,a+b=lub(a,b)(其中lub是最小上界)。 非正式地,关系S给了我们一种比较半环值和约束的方法。 事实上,当我们有一个Sb(或者当半环从上下文中可以清楚地看出时,简单地说是一个b)时,我们会说b比a好。在[5]中,作者在半环结构中加入了除的概念,即除,作为×的弱逆运算。一个吸收半环S是可逆的,如果对所有元素a,b∈A使得a≤b,存在一个元素c∈A使得b×c=a[5].如果S是吸收可逆的,则S是留数可逆的,如果集合{x ∈ A|b× x =a}对所有元素a,b ∈ A有一个极大值,使得a ≤ b [5]. 此外,如果S是吸收的,那么它是剩余的,如果集合{x ∈ A|b×x≤a}对所有元素a,b ∈ A有一个极大值,记作a∈b.由于符号的滥用,解中的最大元素被表示为一个矩阵b。150S. Bistarelli,F.Santini/Electronic Notes in Theoretical Computer Science 236(2009)147g÷×C(参见[3,7])。C→→⟨ ×⟩{}→→÷⊗g÷gC×C→CgtJ\{},写作 t j是约束s. t。 =[ := ]中。信息y,\{}∈×÷C C × C →C这个选择并不含糊:如果一个吸收半环是可逆的和剩余的,那么它也是可逆的剩余,和两个定义产生相同的值。为了利用这些性质,在[5]中指出,如果我们有一个吸收的和完全的半环3,那么它是剩余的。由于这个原因,由于所有经典的软约束实例(即经典CSP,模糊CSP,概率CSP和加权CSP)是完整的,因此剩余的,半环划分的概念可以应用于所有这些。 因此,对于所有这些半环,将该操作用作的下一段)。软约束系统。软约束[6,3]可以被看作是一个约束,其中其变量的每个实例都有一个相关的偏好。给定S=A,+,0,1和有限域D上的有序变量集V,软约束是一个函数,给定变量的赋值η:V D使用这个符号=η A是可以从S,D和V开始构建的所有可能约束的集合。中的任何函数都涉及V中的所有变量,但我们强制它只依赖于它们的有限子集的赋值因此,例如,变量x和y上的二元约束cx,y是函数cx,y:(V D)A,但它仅取决于变量x,y V的赋值(约束的支持或作用域)。注意cη [v:=d1]表示cηJ,其中ηJ是用赋值v:=d1修改的η。还要注意,对于cη,我们得到的结果是一个半环值,即cη=a。给定集合,组合函数:被定义为(c1c2)η=c1η c2η(也参见[6,3,7])。 在定义了半环上的运算之后,约束除法函数:被定义为(c1c2)η=c1η c2η[5]。非正式地,执行两个约束之间的或C上的偏序≤S可以通过定义c1±c2≠c1η≤c2η在约束之间容易地扩展。考虑集合C和偏序±。然后定义一个蕴涵关系S. t.(C)× C。 对于每个C∈H(C)和c∈ C,我们有C∈ HC±C给定一个约束c∈ C和一个变量v∈V,c在Vvc(Vv)cc ηdDcη vd投影意味着从支持中消除一些变量。这是通过将剩余变量上的每个元组与半环元素相关联,所述半环元素 是由原始约束与所有扩展相关联的元素的总和3如果S是吸收半环,则S是完备的,如果它对于无穷和是闭的,并且分配律对于无穷个数的被加数也成立。S. Bistarelli,F.Santini/Electronic Notes in Theoretical Computer Science 236(2009)147151定义为() =[ :=]。±×C这个元组的所有变量。为了处理语言的隐藏算子,通过使用类似于圆柱代数中使用的概念,对于每个x∈V,隐藏函数[3,7]xc ηdi∈Dcη x di为了对参数传递进行建模,对于每个x,y∈V,对角约束[3,7]为定义为dxy∈ C s.t., dxyη[x:=a,y:=b] =1,如果a=b且dxyη[x:=a,y:=b] =0如果一个b. 考虑半环S=<$A,+, ×,0,1<$A,变元整环,D,变量的有序集合V和相应的结构C,则SC=[1][2][3][4][5][6][ 7 ][8][9][10][11][12][13][14][15][16][17][18][19]3语言在这一节中,我们将介绍新的业务及其原因。 我们用这种新的语言介绍他们。然后,我们将展示整个语言及其操作语义和一些简单的例子来说明代理计算的演变。收缩(c)操作是我们的非单调扩展的基础,sccp语言,因为它允许从当前存储σ中删除约束c。值得注意的是,我们的撤回可以被认为是存储的“放松”,而不仅仅是严格删除代表约束的标记,因为在软约束中,我们没有令牌的概念。因此,如果c(收缩的参数)满足σ c,那么它可以被移除,即使c与之前添加到σ的任何其他约束不同。用一个比喻来描述动作的顺序,想象一下用勺子把液体倒入碗里,然后从碗里倒出来。碗中的内容物代表存储,而勺子中的液体代表我们想要添加和从存储中收回的软约束;当两种液体混合时,我们失去了所添加的软约束的身份,这可能会通过提高碗中液体的水平来恶化存储的条件。当我们想放松商店时,我们会删除一些用勺子的液体,这对应于去除的约束:由于碗的水平降低,稠度增加。这个更新X(c)原语受到[11]中工作的启发。它是一种这个操作相对于我们的retract是可变粒度的,对于许多应用程序(如我们的SLA协商),非常方便的是有一个关注一个(或一些)变量的松弛操作:原因可能需要完全更新关于参数(例如,第二节中示例的带宽4)。40<$和1<$res分别表示将0和1关联到所有定义域值赋值的约束;一般来说,a<$函数返回半环值a。[5]注意在sccp中,代数性不是必需的,因为的代数性质严格依赖于半环的性质[7]。152S. Bistarelli,F.Santini/Electronic Notes in Theoretical Computer Science 236(2009)147¬¬ϕ1联系我们{\fn黑体\fs22\bord1\shad0\3aHBE\4aH00\fscx67\fscy66\2cHFFFFFF\3cH808080}ϕ1的1的1φ1φ1P::=F.AF::= p(Y)::A|F.FA::= 成功|tell(c)> A |retract(c)> A|更新X(c)> A |E |A A |A.A. |p(Y)E::= ask(c)> A |nask(c)> A |E + EFig. 1. nmsccp语言的语法。nask(c)操作([9,16]中有明确的例子)仅在当前存储不需要c时才启用;它是ask的负版本,因为它检测到不存在的信息。请注意,一般来说,ask(c)与nask(c)不同,因此有必要引入一个全新的原语。例如,考虑存储x10:当操作nask(x5)成功时,ask(x5)将阻塞计算。还考虑c的概念(即约束的否定)对于基于半环的偏好并不总是有意义的,除了例如布尔半环(即0, 1, 0,1)。 当使用加权半环时,很难定义c[3,6]。这个操作提高了语言的表达能力,因为它允许检查还不能从存储中导出的事实(添加它们可能是有价值的),或者不再可导出的事实(检查一些约束是否已被删除),或者我们不希望被存储暗示的事实给定一个软约束系统,定义在Sec. 2和任何相关约束c,nmsccp中代理的语法在图1中给出。 P是程序类,F是过程声明(或子句)的序列的类,A是代理的类,c是约束的范围,X是变量的集合,Y是变量的元组除了新的操作之外,关于sccp的另一个最重要的变化是语法表示法中的操作前缀符号>,它可以被认为是一个一般的“检查”类型的转换→ 2(例如,参照图 1,我们可以写ask(c)→2A),其中i是一个占位符,可以代表或者是半环元素ai,或者是约束φi,即φi= ai/φi。在第一种情况下(即ai),我们需要将存储的一致性总结为一个普通值,并将 φi),我们需要在悬挂物和φi约束之间进行逐点比较,即两个约束之间的比较[7]。我们比较这些值/约束的方式取决于它们在转换符号中的级别:1(或φ1)将被用作切割级别,以修剪此时不够好的计算(即下限),而2(或φ2)用于修剪太好的计算 中给出了>的四个可能实例化图2,即→ a2,→ φ2,→ a2 → φ2 (这些检查的转换将在SEC中得到更好的解释。3.1)。 和经典的sccp一样,半环值a1和a2表示两个切割水平,它们将存储的一致性总结为一个普通值。 另一方面,约束φ1和φ2表示finer检查由于商店和这些约束之间的逐点比较, 进行。因此,我们现在可以在计算过程中对可接受性区间进行S. Bistarelli,F.Santini/Electronic Notes in Theoretical Computer Science 236(2009)147153φ关于我们{\displaystyle{\frac {C} ∈ C→⊆×⟨ →⟩⊆的1..φ1而在经典SCCP中,这是不可能的:SCCP是单调的,因为存储的一致性水平只能在代理的执行期间降低,所以只有修剪那些使该水平降低太多的计算才有意义。另一方面,在nmsccp中,有可能从存储中删除约束,因此可以再次增加级别(这导致缺少失败代理)。出于这个原因,我们要求检查的重要性,也存储的一致性水平将不会超过一个给定的阈值。拥有偏好的区间,而不仅仅是下限,在谈判中非常重要,因为它可以提高请求和结果的表达能力。例如,将偏好视为给定资源的成本:区间的较低阈值将防止我们为该资源支付过多费用(即高成本意味着低偏好),而上限阈值则模拟合同中的一个条款,该条款迫使我们至少支付最低价格。SCCP中经典的询问和告知操作(其中仅存在下限)也可以在NMS CCP中获得:例如, 当k/te l(c)→1<$A时,3.1操作语义为了给我们的语言一个操作语义,我们需要描述一个适当的转换系统Γ,T,其中Γ是一组可能的配置,Tr是终端配置的集合和Γ Γ是配置之间的二元关系。配置的集合是Γ =A,σ,其中σ而终端配置的集合则是T=成功,σ。nmsccp语言的转换规则在图中定义3 .第三章。>是一个通用的检查转换,由语言的几个动作使用。因此,为了简化图中的规则,3我们定义一个函数σk>:σ→{true,false}(其中σ∈ C),用图中的>(C1-C4)的四个可能的实例之一参数化。2),如果满足>的特定实例定义的条件,则返回true,否则返回false。图2中括号之间的条件表明,区间的下限显然不可能C1:>=→a2k(σ)>=t rueif.σσ/>Sa2C3:>=→a2k(σ)>=t rueif.σσ/>Sa2的1(witha1> a2)σ⇓∅SA1φ1(withφ1mm/>a2)σ/иφ1C2:>=→φ2k(σ)>=true ifσ/<$φ2σσ/=→φ2k(σ)>=true ifσ/<$φ2σ/иφ(带1/> φ2刻度)∅S11(with(φ1/φ2)否则,在相同的条件下,p∈K(σ)>=false图二、为四个检查转换中的每一个定义检查函数154S. Bistarelli,F.Santini/Electronic Notes in Theoretical Computer Science 236(2009)147()()(return();∅⇓⇓∅J⊗⊗注意,在图2中,我们使用Sa1而不是≥Sa1,因为我们可能处理部分订单。 类似的考虑也可以用于i而不是±。图2中的一些区间(C1,C2和C3)通过考虑软约束满足问题(SCSP)[ 3 ]的解决方案产生的值中的最小上限来检查,该问题定义为P=C,con,(C是约束和con的集合,即。问题变量的子集这就是所谓的最佳水平blevel P Sol P Sol P Ccon注意supp(blevel(P))= . 我们还说:如果blevel(P)= α,则P是α -相容的;如果存在α>S0使得P是α-相容的,则P是相容的;如果不相容,则P是不相容的.在图2中,C1检查问题的α-一致性是否在1和2之间。换句话说,C1表明我们至少需要一个与1一样好的解,目前的商店,但没有解决方案比一个2更好;因此,我们确信,一些解决方案满足我们的需要,这些解决方案都不是“太好”。这些检查的语义可以很容易地改变,以便对偏好区间的不同要求进行建模,例如,以保证存储中的所有解决方案(而不是至少一个)都具有包含在给定区间中的偏好R1k(σtell(c)>A,σ<$−→R2σck(σ)>ask(c)>A,σR3<$A,σ<$−→ <$AJ,σJ<$<$A<$B,σ<$−→<$AJ<$B,σJ<$⟨B ǁA, σ ⟩ −→ ⟨B ǁAJ,σJ ⟩告诉问第1章R6σ/ck(σ)>nask(c)>A,σR7σ±cσJ=σg<$c<$k(σJ)><$收缩(c)>A,σ<$− →<$A,σJ<$R8σJ=(σ(V\X))ck(σJ)>updateX(c)>A,σ纳斯克缩回更新R4A,σ − →成功,σJ<$A<$B,σ<$− →<$B,σJ<$2002年R9<$A[x/y],σ<$−→ <$B,σJ<$,y新鲜Hide⟨∃x.A, σ ⟩ −→ ⟨B,σJ ⟩J<$B<$A,σ<$− → <$B,σJ<$R5<$Ej,σ<$− → <$Aj,σJ<$j∈[1,n]农代R10<$A,σ<$− →<$B,σ<$p(Y),σp(Y)::A ∈ FP呼叫ni=1 Ei,σ− →Aj,σ j图三. nmsccp的转换系统。这里是图3中的转换规则的描述。在泰尔规则(R1)中,如果存储器σ c满足图2的特定>转移的条件,那么代理人在存储器σc上进化为新的代理人A。因此,约束c被添加到存储σ。 在(可能的)下一步骤存储上检查条件:即 k(σJ)>。为了应用Ask规则(R2),我们需要检查当前存储σ是否需要约束c,并且如果当前存储相对于由S_p_c_transition_w定义的较低和较高p_er阈值是一致的:即,如果k(σ)>是⟨ΣS. Bistarelli,F.Santini/Electronic Notes in Theoretical Computer Science 236(2009)147155ǁǁ±g∈≤÷g∈∈\真的非确定性和非确定性:复合运算符+和re-repeat表示非确定性和并行性。当两个代理都成功时,并行代理(规则R3和R4)将成功。这个操作符是根据交错来建模的(就像在经典的ccp中一样):每次,代理A B只能执行A和B的初始启用动作之一(R3);如果所有组成代理都成功,则并行代理将成功(R4)。不确定性规则R5选择一个守卫成功的代理,显然会产生全局不确定性。当一个语句不能从当前状态中导出时,需要Nask规则来推断它的缺失:R6中的语义表明,当一致性间隔满足当前存储时,该规则被启用(对于ask),并且c是不需要商店:即。σ/±c。Retract:使用R7,我们能够使用Sec中定义的约束除法函数从存储σ中“移除”约束c。二、根据R7,我们要求悬挂物包含约束c,即σ c。 注意,在[5]中,除法总是被定义的,但是对于nmsccp语言,我们决定只有当存储足够大到允许移除c时才能移除数量c,也就是说,我们希望只有当a ≤ Sb时才有可能移除ab。例如,考虑图4中的c1,c2和c3加权约束:变量x的域是N,所采用的半环是经典的加权半环<$R+,min,+,+∞,0 <$。由于c2±c1(c1函数对于每个x N都完全由c2支配,因此c1更好),可以执行c 2 g c 1,但由于x=1(例如),c3(x)=2比c1(x)= 4更好,因此不可能执行c 3 c 1:因此由于R7的定义,2 4和半环除法2 4不能执行。显然,也可以像使用令牌一样完全删除约束:定理3.1(完全移除)给定一个软约束系统C,其中半环S通过再分解是可逆的 , 因 此 g_k_c可 以 被 定 义 为d , 那 么 nmsccp 主 体 σ_k_l ( c_i ) > retract(c_i)> A,σ_k_k是等价的(即 最后的存储是相同的)到A,σk,对于每个约束ci,存储σk和>(如果启用)。作为证明的一个草图,代理人给定任意两个元素a,b∈S,a×b <$b=a总是成立.由于约束算子(X和G)是由它们的相关半环算子(X和G)导出的,所以同样的性质也成立.更新规则(R8)[11]的语义类似于命令式编程语言中的赋值操作:给定一个更新X(c),对于每个x X,它删除了x所涉及的每个约束对x的影响,最后一个新的约束c被添加到存储中。删除有关所有x的信息X,我们的项目(见第二节)。2)当前存储在VX上,其中V是集合的所有变量的问题和X是一个参数的规则(投影意味着消除一些变量)。如果X=V,则该操作在添加c之前找到由商店定义的问题的b级。最后,一致性水平156S. Bistarelli,F.Santini/Electronic Notes in Theoretical Computer Science 236(2009)147Σ⇓\{}∈±c1:({x} →N)→R+S.T. c1(x)=x+3c2:({x} →N)→R+S.T. c2(x)= 2x +8c3:({x} → N)→ R+S.T. c3(x)= 2xc4:({x} → N)→ R+S.T. c4(x)=x+5c5:({x}→N)→R+s. t. c5(x)=<$3c6:({y}→N)→R+s.t. c6(y)=y+1图四、 六个加权软约束(注意c2= c1<$c4)。在所获得的存储上进行检查,即, k(σJ)>。请注意,所有的removal和约束添加都是事务性的,因为它们在同一个规则中执行。此外,请注意,update的删除语义与retract的删除语义非常不同:update操作总是可以应用,而retract只能在σc时应用。 此外,执行更新不同于顺序地执行一个(或一些)收回,然后告诉:收回以“清除”的方式放松存储σ(Vx)= diDcη[x:= di],其中D是x的定义域). 因此,如果另一个变量y也支持c,则c在某种程度上仍然约束y,更新操作。 作为一个更新之间的不同语义的例子,以及一个retract-tell序列,年龄ntt tt ell(c5)→0ract(c5)→0tell(c2),<$0ttt(在权ed半环1<$$>0中)的结果是s∞torc5g<$c5<$c2∞=c2,而更新{x}(c2),<$0更新导致存储<$3更新c2(即, c5c2),其中<$3=c5(V∞(见图4)。\{x})隐藏变量:R9中存在量化器的语义与[18]中描述的相似,使用了新添加变量的新鲜度概念。去商店过程调用:过程调用的语义(R10)已经在[7]中定义:对角约束的概念(如第10节中定义的)。2)用于模型参数传递。考虑到图中提出的过渡系统 3,我们为每个代理A定义了一组最终存储器,该存储器收集A可以执行的成功计算的结果(即, 可观测s):SA={σ∈var(A)|A,1<$无故障。nmsccp代理计算只能成功或可以挂起等待 这表示相对于sccp的进一步区别,其中,当尝试执行(有值或无值)询问/告知时,如果存储一致性低于转换箭头上标记的阈值,则这被认为是失败(参见[7]):在SCCP中,存储一致性只能单调地降低,因此在后续步骤中永远不能达到更好的水平。在nmsccp中,另一个代理可以并行执行S. Bistarelli,F.Santini/Electronic Notes in Theoretical Computer Science 236(2009)147157⊗C联系我们⊗g÷⇓\n收回(或更新),并因此可以提高存储的一致性级别,然后启用空闲操作。偏好表示和操作代表性和计算问题是复杂的,深入讨论[10]。然而,无论用于表示约束偏好的语言是否有限,都可以提供一些不同的考虑。作为具有有限表示的软约束(的特定子集)的实际示例,考虑加权半环并考虑一类约束,其软偏好(或成本)由约束中涉及的变量的多项式表达式表示在这种情况下,将约束添加到存储意味着获得新的多项式形式,该多项式形式是新的偏好和表示当前存储的多项式的总和;撤回约束意味着仅从存储中减去多项式形式 假设我们有三个约束条件c1(x,y)= x2−3 x +4 y,c2(x)= 3 x +2和c3(y)= 3 y −2:如果初始存储包含c1(x,y),tell(c2)给出(c1<$c2)= x2−3x+4 y+3 x + 2=x2+4 y+2,然后返回(c3)将导致存储偏好(c1<$c2g<$c3)=x2+4y+2−(3y−2)=x2+ y。为了计算更新{y}(c4)的结果,我们需要在V y上投影(参见第2节)。2)在加上c4之前:因此,如果商店偏好是x2+y,我们必须通过指定y = 0来找到这个多项式的最小值,并最终获得 结 果 为 x2c4=x2+x+5(见图4)。注意,在加权半环中,最大化偏好意味着最小化多项式。否则,如果软约束没有有限表示,我们可以将存储建模为约束和动作的有序列表。例如,如果代理按时间顺序执行了tell(c1)、tell(c2)retract(c3)和updateX(c4),则存储将是c1c2c3(V X)c4(其组成是左关联的)。因此,在每个步骤中,可以计算实际存储,以验证约束和一致性区间之间的蕴涵因此,操作顺序很重要:定理3.2(动作排序)给定一个软约束系统,其中半环S通过剩余可逆,改变主体内部的tell和retract动作排序会改变最终存储。事实上,如果我们假设S的×是幂等的,我们就有nmsccp代理并 且 通 过 改 变 动 作 的 顺 序 , 它 可 以 从 tell ( ci ) >tell ( ci ) >retract(ci)>A,σkA,ci中区分出来对于每个约束ci,存储σk和>(如果启用)。 为了证明它,我们考虑对每个半环元素a ∈ S,我们有(a×a)<$a=1(因为a×a= a,如果×是幂等的),但是(a<$a)×a=a。这是由于[ 5 ]中所示的×的幂等性和λ的性质。 即使x不是幂等的,定理3.2也成立:例如(见图4中的约束),tell(c2)>retract(c4)> success,c1成功地终止于存储c1<$c2g<$c4<$c2x+6,而tell(c4)>tell(c2)> success,c1<$c1在第一次收缩时挂起,因为σ ± c的前提条件158S. Bistarelli,F.Santini/Electronic Notes in Theoretical Computer Science 236(2009)147⟩ ≡ ⟨ ⟩×⟨ → →→⟨⟩偏好10.514 5 6789x(资源)图五.模糊一致性R7在图中3为假(这里,c1±c4为假)。这种表示(也就是保持操作序列)不同于Saraswat [18]或[8]中给出的经典表示,因为在这些作品中,撤回仅从存储中删除标记的一个实例:tell(c1)tell(c1)retract(c1)A,1<$ A,c1,even ifisidem点ote注nt. 因此,操作的顺序是没有用,商店只能被看作是一组令牌。4服务水平协议的谈判nmsccp语言最有意义的应用之一是对谈判正式协议(即SLA)的通用实体进行建模[2,15]。主要任务包括通过满足所有代理的QoS需求来完成所有代理的请求。考虑图5中的模糊协商(模糊半环:[0, 1],max,min, 0, 1),提供者和客户端都可以将它们的请求添加到存储器σ(分别为tell(cp)和tell(cc)):粗线表示组合后σ的一致性(即min),以及该SCSP的blevel(参见第2节)。3.1)是最大值,其中两个请求相交(即在0。5)。我们提出了四个简短的例子,建议可能的谈判方案。我们假设有两个不同的公司(例如提供商P1和P2),他们希望将他们的服务合并到一种管道中,以便向他们的客户提供单一的结构化服务:例如P1完成P2的功能。这个例子模拟了[2]中提出的服务的跨域管理。变量x表示在服务提供期间他们可以承受的全局故障数量,而偏好模型则表示管理它们并从中恢复所需的小时数(或数百欧元的金钱成本转换箭头上的偏好间隔模拟了这样一个事实,即P1和P2都明确希望花费一些时间来管理故障(图2中的上限),但没有那么多时间(图2中的下限)。我们将使用图4中给出的加权半环和软约束。为了简单起见,即使示例基于单个标准(即小时数),它们也可以扩展到多标准情况,其中偏好表示为一个不可比标准的元组例4.1[告知和协商]P1和P2都想提出他们的策略供应商软约束客户端软件约束CcCPCcCPS. Bistarelli,F.Santini/Electronic Notes in Theoretical Computer Science 236(2009)147159∞10∞¯∞⊗ ≡⇓⊗g÷≡⇓∅⟩|| ⟨→→⟩≡∞C6⟩⊗ ⇓\{}联系我们⊗≡→4¯(分别由c4和c3表示)向另一方提供服务,并就服务达成共同协议(即SLA)。它们的代理描述是:P1tell(c4)→0当k(s p 1)→ 2连续s n时,tel l(s p2)→0||当k(sp2)∞1时,successfulfillerP2,在存储器中执行,支持为空(即0)。变量sp1和sp2仅用于同步,因此在以下考虑中将被忽略(例如,在Ex.4.2)。最后的存储(两个问题的合并)是σ=(c4c3)2x+x+5,由于σ P2的最后一个偏好区间(介于1和4之间)中不包含P1 = 5,P2不包含实际原因是P1的故障管理系统即使没有故障发生(即x=0)也至少需要5小时(即c4=x+请注意,P2的最后一个间隔要求至少花费1小时来检查故障。例4.2[Retract]一段时间后(仍考虑Ex. 4.1),假设P1想要放松存储,因为它的策略被改变了:这个改变可以从交互式控制台执行,或者通过在语言中嵌入定时机制来执行,如[4]中所解释的。 移除是通过收回c1来完成的,这意味着,P1已经改进了其故障管理系统. 请注意,c1以前从未被添加到商店中,因此这种收回表现为放松;部分删除,这不能用令牌执行(参见第2节)。(5)显然重要在谈判过程中。 P1-1 (c4)→0SY NCHROP1→2return(c1)→201∞10 10成功告诉(c3)SY NCHROP24成功P2在0中执行。最后的存储是σ=c4c3c1 2x + 2,由于σ= 2,P1和P2现在都成功了(它包含在两个区间中)。例4.3[Nask]在协商场景中,nask操作有多种用途。因为它检查信息的缺失(见第3),例如,它可以用于检查自己的策略是否仍然由商店隐含,或者如果它已经放松太多:例如,P1收缩收缩(c1)→0SY NCHROP1 →0成功案例||C3(C4)→ 0nask(c4)→0tell(c4)→0∞P2→0成功∞¯∞∞<$SY NCHRO<$CHROP2(在0中评估)。一旦P2添加了它的策略(即c4),P1就可以放松它(通过删除c1);P1通过nask感知到这种放松,并再次添加c4。 原因是P1明确需要一个不优于的全局花费小时数由c4定义的一个,然后必须由商店承担:例如,其恢复系统仅在至少该时间内工作。在这里,两个主体的偏好区间并不重要,因为它等于整个R+。例4.4[更新]该更新可用于实质性更改该政策: 例如,假设P1≠ tell(c1)→ 0更新{x}(c6)→0成功,0。此年龄nt在商店中成功?0c1(Vx)的∞,其中c1(Vx)∞=#3和#3C6y+4(即,描述最终存储的多项式)。 因此,第一个基于失败次数的策略(即,c1)被更新,使得x被c6)仅取决于系统重新引导的y次数存储的一致性级别(即小时数)现在仅取决于SCSP的y变量。请注意,最终存储的f3component是从“旧的”c1派生的,这意味着某些固定的160S. Bistarelli,F.Santini/Electronic Notes in Theoretical Computer Science 236(2009)147±⊗也包括在这一新政策中。5相关工作在所谓的线性cc规划[17]和下面的工作[1,9,11,16]中,对明确约束的非单调性进行了广泛的研究。 关于相关的SLA协商模型,[12]中介绍的进程演算关注于控制和协调分布式进程交互,同时尊重表示为c-半环值的QoS参数;然而,该模型不涵盖协商。在[2]和[15]中,作者在较低的抽象层次上定义了SLA,并且它们的描述与协商分离(而软约束系统涵盖了这两种情况)。由于两种语言都用于SLA协商,因此nmsccp最直接的比较是[8]中的工作,其中软约束与名称传递演算相结合(即使本文中的所有示例都是使用明确约束开发的)。然而,在我们的语言中存在一些重要的差异:i)在nmsccp中,我们没有约束令牌的概念,并且可以移除存储所包含的每个c(即,σc),即使c在句法上与之前添加的所有c不同(如Ex. 4.2)。例如,即使从包含c1和c2的存储中删除c1c2组合也不能在[8]中执行,因为它是派生约束。因此,我们的撤回更像是一个然后,ii)通过nmsccp,我们可以在各方之间达成最终协议,也知道“如何一致”(或“如何昂贵”)所声称的需求得到满足。这是通过检查存储的首选项级别和调节操作的一致性间隔来实现的(图2)。通过这种方式,每个代理人都可以指定其对最终协议的期望偏好。这是关于[ 8 ]的相关改进,其中最终存储器收集所有一致的解决方案,没有任何区别,即。 a ch解,满足σi=αi,对于每一个αi>S0。最后,我们引入了更新操作(扩展了crispupdate in [11]),这是一个可变粒度的松弛,以及nask(
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- IPQ4019 QSDK开源代码资源包发布
- 高频组电赛必备:掌握数字频率合成模块要点
- ThinkPHP开发的仿微博系统功能解析
- 掌握Objective-C并发编程:NSOperation与NSOperationQueue精讲
- Navicat160 Premium 安装教程与说明
- SpringBoot+Vue开发的休闲娱乐票务代理平台
- 数据库课程设计:实现与优化方法探讨
- 电赛高频模块攻略:掌握移相网络的关键技术
- PHP简易简历系统教程与源码分享
- Java聊天室程序设计:实现用户互动与服务器监控
- Bootstrap后台管理页面模板(纯前端实现)
- 校园订餐系统项目源码解析:深入Spring框架核心原理
- 探索Spring核心原理的JavaWeb校园管理系统源码
- ios苹果APP从开发到上架的完整流程指南
- 深入理解Spring核心原理与源码解析
- 掌握Python函数与模块使用技巧
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功