论文部分内容阅读
随着计算机技术和网络通信技术的高速发展,以并发性、分布性、实时性、异构性和互操作性等主要特征的并发分布式系统已成为计算机技术的主流方向。并发现象以其固有的复杂性,对计算机科学家提出了挑战。与顺序计算不同,我们对并行与并发计算实质的认识尚处于初级阶段。进程代数主要是用来描述并发计算的数学模型,它研究并发现象,即多个计算主体(进程)同时活动,通过交换信息(通讯)进行协作,以共同完成预期任务的特定计算现象。对并发理论的研究,进程间的等价是需要关注的重点。两个进程在什么时候具有相似的行为可以用等价关系来描述他们。最近,在一些用来解决并发系统问题的算法构造中,随机被证明是一种很用的工具。传统上,对形式化建模并发系统的进程演算是不进行定量分析的,结果,对于一个并发系统会以多大的概率来发生某个动作就无法提供有用的信息。而从应用的角度来说,有必要进行定量分析,因为在本质上并发系统的许多方面是与随机相关的。本课题把进程的定量信息限制在概率信息上,在研究带有概率信息的进程时,路径等价是把概率看成是一个动作,这是不可取得,因为这意味着只有在路径上的所有动作包括概率完全一致情况下,进程才是路径等价的。所以,过分的依赖于概率信息,导致路径等价的概念存在着很大的缺陷。我们认为,在进程中出现的概率不应该被看成是个动作,而应该是进程发生随机事件的可能性。从而,我们想使用一个关于进程间近似程度的概念来替代路径等价。主要内容及创新点包括:1.综合以前的结果,提出一种新的metric的定义,并把它和路径等价相关联,同时证明了概率进程演算中的大部分算子在该metric下是封闭的。2.根据metric的定义,利用线性规划对偶性,把它归约到一个transshipment问题,并在此基础上,设计实现了一个工具。该工具可以接受两个进程表达式,计算出它们之间的相似度(距离)。3.在metric的基础上,给出了安全协议匿名度的定义,结合密码学家就餐问题(DCP),说明了我们设计的概念;利用已开发的自动工具,给出了该DCP及其一些变种的匿名性分析。