概率构形理论

理论计算机科学电子笔记174（2007）95-108www.elsevier.com/locate/entcs概率构形理论亚历山德罗·蒂贝里1罗马大学计算机科学系，摘要我们引入了一个新的框架来描述计算，这是并发和概率。这个框架是[4]的配置理论的自然扩展，并且允许表达关于并发计算的因果和概率方面的通过使用偏序集序列的概率扩展，以公理化的方式描述计算这些序列的结构规则的计划被引入，并被证明是健全的，而完整性可以通过添加一个规则，这是不处理在目前的工作。我们还介绍了一个新的概率扩展的配置结构，我们使用的概率序列的模型保留字：概率语义学，并发，配置结构，并行演算1引言在并发和分布式设置中，随机化起着重要的作用。这是民间传说的知识，有一些问题，如果没有随机位的来源，根本无法解决，而当有一个随机性的来源时，它们几乎变得容易（例如见[6，10，3]）。除了提供解决这些问题的重要工具之外，随机性对于分布式系统的各个方面的建模似乎非常有用事实上，分布式系统的许多典型特征，如硬件故障、消息到达、服务请求等因此，毫不奇怪，在过去的几年里，并发社区对计算的概率方面表现出越来越大的兴趣，产生了从经典过程演算的扩展（例如[9]）到将概率与并发系统的因果模型（[5，1，2]）相结合的作品。我们提出了一种新的方法来公理化并发和概率过程的性质，使用[4]的偏序集序列的扩展。计算状态用序列来描述，序列的组成部分是偏序事件集的序列序列由1 电子邮件地址：tiberi@di.uniroma1.it1571-0661 © 2007 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2006.11.04196A. Tiberi/Electronic Notes in Theoretical Computer Science 174（2007）95ρ一个单态矩阵，它描述了任何匹配左半部分的计算如何必须扩展到匹配右半部分的至少一个偏序集的计算。 这些序列也配备了一个概率向量，它将概率与出现在序列右侧的每个偏序集相关联。粗略地说，这个概率是计算的任何状态匹配l.h.s.最终会演变成一种与它的r.h. s相匹配的状态。我们还提出了一种新的构型结构的概率扩展[7]，我们将其用作由这些序列生成的理论的模型这些结构本质上是[4]的单调结构（在那篇论文中称为保守的），我们在其上添加了一个底层有限马尔可夫链，它允许我们推理一个配置C最终变成另一个配置D的概率。在第2节中，我们引入概率偏序集的概念，在第3节中，我们制定了我们的配置结构的扩展，精确地定义了一个结构何时满足一个偏序集，并提供了一些例子，序列和概率配置结构。在第4节中，[4]中给出的规则被适当地修改以考虑概率，并且它们被证明是合理的。在最后一节中，我们简要地讨论了一些可能的未来工作。2概率偏序集序列在[4]中引入了偏序集的概念。非正式地说，一个偏序集是由两个偏序集序列通过一个单态射矩阵连接在一起组成的。直觉上，这样的一个偏序集描述了一些计算性质（由偏序集右边的偏序集给出），这些性质对于任何匹配偏序集左边的计算都必须成立。我们将这一概念扩展到概率计算，允许由序列描述的属性以一定的概率保持。在给出任何形式的定义和提供关于这些新序列的意义的更多的直觉之前，我们引入一些基本上遵循[4]的符号。 我们用Γ，Δ... 来表示偏序集序列A，B... 对于单偏序集和a，b. 他们的元素。 序列Γ和Δ的连接记作Γ， Δ。monos 的 矩阵表示为ρ，σ. .给定两个大小分别为m×n和r×n的矩阵ρ和σ，我们将（m+r）×n矩阵写为ρ;σ，它是通过将ρ放在σ之上而得到的，而如果σ的大小为m×r，我们将m×（n+r）矩阵写为ρ，σ，它是通过将ρ放在σ之前而得到的。关于这种结构的正式定义，我们请读者参阅[4]。给定两个偏序集序列Γ =A1，. Am和Δ =B1，…Bn我们写ρ：Γ → Δ来表示一个m × n的monos矩阵，使得ρij：Ai→ Bj。 我们也用δ来表示元素δi∈ [0，1]的向量。给定两个这样的向量δ和δJ，我们将它们连接得到的向量记为δ·δJ 我们现在可以定义什么是概率偏序集定义2.1概率偏序集<$Γ <$δ其中，有两个是由两个不同的元素组成的。一个偏序集序列Γ和Δ，一个monos矩阵ρ：Γ → Δ和一个向量δ使得如果Δ = Δ1，.，Δ n则δ = δ1.δn和δi∈ [0，1].A. Tiberi/Electronic Notes in Theoretical Computer Science 174（2007）9597ρ在解释的概念和我们解释这些序列的模型被给出之后，读者可能会更好地理解这个定义。然而，在进一步进行之前，我们发现建立一些关于这些后果的意义给定一个πΓπ δ Δ，它的左手边Γ描述，根据事件之间的因果关系，计算状态。 事件是Γ中偏序集的元素，它们之间的因果关系用偏序表示。每个Γi应该被认为是由Γ描述的计算状态的一个属性因此，每一个Γi都以某种方式与其他Γ i结合。相反，序列Δ描述了所有“性质”Γ i都成立的任何计算C最终必须满足的性质特别地，我们要求C将达到满足至少一个Δ i的状态D（因此每个Δ i都应该被认为是与其他Δ i分离的）。我们还要求从C到达D的概率至少为δi。这最后一个约束本质上是什么使得偏序集和概率偏序集之间的差异在第3节中将给出序列的具体例子。3概率配置结构在这一节中，我们介绍解释概率序列的模型。我们首先回顾一下配置结构的定义[7]：定义3.1一个构形结构是一个对（E，C），其中E是一个集合，其元素称为事件，C是E的一个子集族，称为构形。给定一个构形结构（E，C）和一个构形C∈ C，我们用Sub（C）表示C的包含在C中的构形的集合。 偏序≤C可以通过定义≤C以自然的方式与每个配置相关联={（a，b）|n∈Sub（C），b∈D =a∈D}。 在[4]一个特殊的配置类中结构，称为单调。这些结构需要具有以下特性：• 有限性：如果一个事件属于C中的一个构形，那么它也属于C的一个有限子构形。• 无重合性：如果两个不同的事件a，b属于一个配置C，则存在D∈Sub（C），其中恰好包含{a，b}中的一个事件。• C的非空• 下闭有界交：<$C∈ C，<$D，F∈Sub（C），且对所有a∈D<$F，如果b≤Da，则b∈F。如[4]所示，单调结构保持由子配置诱导的偏序，即如果D∈Sub（C）且a≤Db则a≤Cb，因此对于这些结构，包含可以被视为偏序集之间的单态。在本文的其余部分，我们假设所有结构都是单调的，我们还需要连续的。连通性：对所有非空C∈ C，存在a∈C使得C\ {a} ∈ C。连通性意味着根性：空构形属于C。如果我们也98A. Tiberi/Electronic Notes in Theoretical Computer Science 174（2007）95要求在有界并下的闭包（即如果C，D<$D J，则C<$D是一个配置），那么如果我们考虑一个配置C和它的一个子配置D，使得C\D ={e1，.，en}，存在至少一个事件序列eπ（1）. eπ（n）这样，i≤k{eπ（i）}是一个构形，对所有的k≤n，π是一个置换在[n]上。这最后一个要求对我们的理论来说不是严格必要的，但它使有些定义技术性较低，因此我们强制执行。但是，我们强调这不是必要的。给定一个配置结构C，我们称一个事件e在一个配置C∈ Cife∈/Candnd∈D∈ Cs.t. D=C{e}。我们不知道E（C）的内容，在C处启用所有事件。非正式地说，一个概率配置结构是一个配置结构，它富含一些组件，允许从它的任何子配置开始推理达到配置C的概率。 首先，我们给所有事件都加上一个标签，然后假设集合L的标签是有限的。接下来，我们为每个配置附加一个概率函数，在E.最后，我们将这个结构与有限马尔可夫链相关联（例如参见[8]），我们将其视为一个有向加权图，其边用L的元素标记。然后我们的结构被映射到这个图上，每一个节点都是一个节点，如果S（C）是一个节点，映射时，集合E（C）映射到S（C）的输出边上。 我们要求这种映射保留标签、概率和“转换”。换句话说，我们将这种映射强制为一种结构之间的同态，该结构被视为一个（可能是无限的）图，其节点是配置和边使能事件，而图表示相关的马尔可夫链。这是精确的，以下定义。我们首先定义什么是有限标记马尔可夫链。 在下面的例子中，我们将标签集固定为L。定义3.2有限标记马尔可夫链M是一个有向图G=（S，A）以及一个权函数w：A→[0，1]和一个标记函数LM：A→ L。从节点si到节点sj的边由sij表示，并且权重函数受到以下约束：对于所有si∈S，Σsij∈Aw（sij）= 1。我们称之为S态的元素。定义3.3概率配置结构是一个6元组（E、C、P、L、C、M、h）哪里(i) （E，C）是一个结构(ii) P： C →（E →[0，1]）是一个函数，它为每个配置C分配一个Σ函数PC使得e∈E（C）PC（e）= 1(iii) LC：E→L是一个标号函数A. Tiberi/Electronic Notes in Theoretical Computer Science 174（2007）95992/31/2B1/3一B1/2a B一图1.与例3.4的结构相关联的马尔可夫链。最后一个事件标记为a的配置映射到状态A，所有其他事件映射到状态B。(iv) M是有限标号马尔可夫链(v) h是一个函数，它将C的组态映射到M的状态上，并将在每个组态下启用的事件的不相交并映射到M的弧上。 我们写 hC（e）表示h（e），其中e∈E（C）。我们还要求，如果h（C）=si，则E∈E（C）s.t.Pc（e）>0，则存在弧sijs.t.：• hC（e）=sij• w（sij）=PC（e）• LM（sij）=LC（e）• h（C{e}）=sj例3.4考虑其事件是两个可数无限集合A ={a1，a2，. }且B ={b1，b2，... }，其中A中的事件用a标记，B中的事件用b标记。设这些结构的构形是所有集合C（包括空集）s. t。 如果|C|= n，则C ={c1，c2，. ，cn}其中ci∈ {ai，bi}。此外，对于这样的配置，令使能事件的集合（其中，使能事件的集合为a，b，e{an + 1，b，n + 1 }）为p，c（an + 1）= 2 / 3，b，n，d，e{an+ 1，b，n +1}）。如果在Ciscn=an中的定义为PC（bn+1）=1/3，则PC（an+1）=PC（bn+1）=1/2否则，请执行以下操作。通过将这个结构以明显的方式映射到图1所示的马尔可夫链上，我们得到了一个概率配置结构。一旦我们在马尔可夫链上映射了一个配置结构，我们就可以定义从它的一个子配置C开始到达配置D的概率。我们记得转移矩阵P可以与任何有限马尔可夫链相关联。这个矩阵的一个元素pij是在一步中从状态si到达状态sj的概率（边sij的权重）我们还记得，从状态si开始经过n步到达状态si的概率被定义为向量u（n）的第j个条目，其中u（n）=uPnu是一个向量，除了第i个元素等于1外，其余都是零分量，Pn是P的n次方。定义3.5设Cp=（E，C，P，LC，M，h）是一个概率构形结构，设C，D是两个构形，使得C ∈ Sub（D），|D\C|= n. 如果100A. Tiberi/Electronic Notes in Theoretical Computer Science 174（2007）95JC和DC和Dh（C）=si和h（D）=sj，则从C开始到达映射到D的相同状态sj上的配置的概率被定义为Pr（C→h（D））=u（n）其中，u（n）=uPn，P是M的转移矩阵，并且u除了其第i项等于1之外处处为零注意，根据上面的定义，概率Pr（C→C）总是等于1。这个定义考虑了映射在底层马尔可夫链的相同状态上的等价配置实际上，对于我们头脑中的满意度概念来说，这太抽象了，因为我们想精确地计算从一个配置C到一个配置D的概率。为了达到这个目的，我们需要引入一些其他的定义。定义3.6从构形C到构形D的路径πC，D是pairwisedisteeennsπ=e1e2· · ·ensuchatei∈/C，C的等式i≤kei=对于k∈[n]，Dk∈C，且Dn=D.C称为π的源，D称为目的地。从C到D的所有路径的集合记为<$C，D。 我们写πc，π d来表示一条路径，它的源是C，目的地没有指定。我们也写|π|表示π的长度。 然后我们可以定义路径πC，D= e1.的概率。 埃凯阿斯Pr（πC ， D）= w（hC（e1））·Pr（πC<${e1}，D）其中πC<${e1}，D = e2. EK。如果D是一个没有启用事件的配置（并且因此，在马尔可夫链中，它由仅具有一个权重为1）的进入边的节点表示我们可以延伸一条死路πC，D= e1. ek的长度为k，到路径πJ长度为k+c，允许D以概率1执行c个不可见事件因此，对于所有没有启用事件的配置D，如果h（D）=si，我们扩展hD，使得hD（D）=sii和PD（D）= 1。一个概率构形结构需要一个概率函数在一组具有任意固定长度n的路径上，这些路径共享同一个源C，但只有在我们将长度小于n的死路πC，D延长到路πJ长度为n通过添加一系列合适的不可见事件来实现。注3.7设集合k ∈C，k定义为包含所有长度为k，其源为C，且所有长度小于k的死路πC，πN都扩展到长度为k的路。法院认为：(i) <$π∈<$C，kPr（π）≥0(ii) <$π∈<$C，kPr（π） ≤1Σ(iii) Pr[ΠC，k]=π∈ΠC，kPr（π）= 1我们省略了证明，因为这是例行公事。读者应该注意到，在3.5中定义的概率Pr（C→h（D））是概率Pr[C → h（D）]的上限A. Tiberi/Electronic Notes in Theoretical Computer Science 174（2007）95101ρik−→D这个性质可以用来证明一个配置结构不满足一个马尔可夫链，只看马尔可夫链，而不考虑路径。我们现在可以定义一个概率配置结构何时满足一个概率，abilistic poset sequent.我们称一个n×1单倍矩阵π：Γ→C为一个解释在C.下面的定义类似于[4]中给出的定义，但它也考虑了概率。定义3.8一个概率构形结构（E，C，P，LC，M，h）被称为满足一个概率分布函数Pr[C，D] δ Δ，当对于任意C∈ C和解释π：Γ→C，存在D∈ C，一个分量Δk和一个单q：Δk→D使得C∈Sub（D），对于所有i，下图交换且Pr[C，D]≥δkρΓi−→Δk⏐ ⏐πiC⊆并不是说，我们的共同点是，上图是偏序集之间的单态映射。只要强制所有mono都保留标签的附加约束，就可以将事件标签和满意度的概念扩展到事件被标记的环境中。下面我们将使用带标签的序列。在本节的剩余部分，我们开发了一个简单的例子，让读者了解这些序列可以用于什么3.1例如考虑这样一个场景，其中有一个共享资源，进程可以在该资源上进行一些计算，但只有在它们获得了对该资源的锁之后。序列可以用来公理化计算的正确性（例如，对共享资源的独占访问），并且，正如我们将要看到的，还可以强制进程在某种程度上是公平的：事实上，通过使用合适的序列，我们可以规定进程在对资源进行了一些计算之后以一定的概率释放资源本身 对于以下序列，使用三个标签，L={l，u，c}。 他们站用于：锁定、解锁、计算。第一个理想的属性是，在一个进程可以对一个资源进行任何计算之前，它应该在这个资源上获得一个锁。由于这是一个本质上关于计算过去的属性，我们要求它以概率1成立。下面的示例说明了这一要求：我们还希望将锁强制为独占的。不幸的是，偏序集序列不太擅长表达这样的性质，但是如果我们把自己限制在一个概率为1的情况下不会达到任何配置的设置，下面的表达式可以完成这项工作：只要我们禁止任何配置以概率1进化到其他配置中，这个锁就表示了所需的属性，因为在这种情况下，这个锁强制解锁动作发生在两个锁之一Q102A. Tiberi/Electronic Notes in Theoretical Computer Science 174（2007）9511/3L1/10LCCl图2.这个偏序集由两个偏序集组成：其中一个l.h.s包含一个标记为c的元素，另一个包含两个元素b，d，分别标记为l和c，以及b d。 矩阵ρ由一个单声道组成，它将a映射到d上（如图中的弧所示）ul图3.这个偏序集包含三个偏序集，一个在l.h.s中，两个（用逗号分隔）在r.h. s中， 这一次ρ是两个单声道的矢量，一个描绘在图的上部，一个描绘在图的下部。这个函数表示，每当资源被锁定两次时，其中一个锁必须被释放。这两个属性基本上很少使用概率。现在我们描述另外两个概率起重要作用的性质。我们想强制执行，当一个进程获得一个锁时，它有一个正概率（等于1/ 10）在它锁定的资源上进行C图4.这个锁与第一个锁类似，但这里我们把概率设为1/ 10，因此任何获得锁的计算最终都将扩展到使用资源的计算，概率至少为1/ 10。我们需要的最后一个属性是，一旦一个进程获得了一个锁，它就不会永远持有它。特别地，我们要求一旦它至少使用了一次资源，它就有一个正的概率（即1/ 3）释放它的锁。这一点可以用以下公式来表示：c c uL l图5.与前一个一样，这个矩阵包含两个偏序集和一个单声道矩阵。在右边的偏序集中，有一个解锁动作，因果依赖于启用计算的锁。1 .一、1uL lLL ，lA. Tiberi/Electronic Notes in Theoretical Computer Science 174（2007）95103KKk，jk，jKKk，1k+1k+1k+1KKKk，jk，h现在我们描述一个概率构形结构，它的构形满足所有这些序列。这个结构是用来描述一个并发计算，其中两个进程共享一个资源。让我们假设有一组无限的事件E，划分为七个集合，Li，Ci，Ui，其中i= 1， 2，以及空闲的集合I={w1，w2···}，事件 集合L1={l1，l1. }包含第一个进程的锁事件，即1 2第二组和其他组也是如此我们固定标签集合L={l，u，c，w}并且将标签1关联到集合Li中的所有事件，并且对于其他集合也是类似的到每个锁动作li，我们关联一组计算Ci∈Ci，其元素，用ci表示. 为了描述我们的结构的配置，我们发现它配置-在E上引入一个偏序：我们假设lij在C中时，我们定义PC（ui）= 0。8和PC（ci）=0。2.k k，j+1我们现在可以将图6中的马尔可夫链与这个结构联系起来。通过查看给状态的标签，应该可以理解配置如何映射到这个链的状态上：Cb中的配置与具有相同标签的状态相关联，而Cl中的配置与状态Cl1或Cl2相关联，这取决于哪个进程执行了Cc中的构型映射到剩余的状态上。现在让考虑一个配置C，其左侧存在一个解释映射

下载后可阅读完整内容，剩余1页未读，立即下载