大规模随机进程代数模型的死锁检测和性能分析

随机进程代数已经成功地用来对计算机和通信等系统进行协议验证与性能评估,但这种应用受到状态空间爆炸问题的严重制约. 本项目研究主要是以随机进程代数PEPA为例,发展相关理论和技术来处理大规模随机进程代数模型的死锁检测和性能分析所遇到的状态空间爆炸问题. 在死锁检测方面, 我们根据模型的逻辑架构来确定状态空间的结构特性并利用这些特性去判断有没有死锁. 在性能分析方面,我们将结合Fluid逼近方法来降低随机模拟过程中系统从初始状态运行到平衡态的预热时间, 以此来改进随机进程代数的模拟算法. 同时, 我们还将建立相关理论特别是大偏差理论用来分析随机模拟算法. 本项目还将对PEPA模型的Fluid逼近所引出的非线性微分方程进行研究, 着重去解决方程解的关于时间的收敛性的一个公开问题. 这些研究将进一步拓展随机进程代数的应用, 并为这些应用奠定理论基础.

本项目的研究工作已经圆满结束，我们较全面较好地完成了本项目研究全部技术指标和预定任务。项目组成员共发表25篇学术论文，其中SCI收录17篇，EI收录17篇。项目主持人发表6篇SCI论文，提交2项发明专利申请，获得2项软件著作权。项目研究所获得主要成果分为三个部分：. 一、我们对随机进程代数模型的死锁检测提出了一种较新的方法： 利用并发系统的逻辑架构和状态空间的结构特性来检测死锁，对于具有大量相同类型的实体的模型，死锁检测效果尤为显著。能够较好地缓解空间爆炸问题。特别是，在某些情形本方法甚至能够说明哪种系统结构会以何种方式导致死锁。. 二、我们提出了随机进程代数模型的一个较新的模拟算法：有效融合了随机模拟方法和Fluid逼近方法的优点，充分利用了Fluid逼近能迅速求解出近似平衡态的特点，省去了系统从初始状态到平衡状态的预热过程的模拟，提高了模拟算法的收敛速度和降低计算资源的消耗，又能全面而精准地获取系统的性能参数。对当前并发系统的性能模拟和评估起到很好的改进作用。. 三、我们获得了关于随机进程代数PEPA模型的Fluid逼近的一系列理论成果：（1）我们提出了PEPA模型的Fluid逼近的生成算法，这种算法课用来自动生成Fluid逼近的微分方程组。（2）我们提出了从随机进程代数模型的Fluid逼近中提取性能的方法；（3）我们得到一类PEPA模型的Fluid逼近所导出的方程的解的存在唯一性、有界性、非负性等基本性质，同时证明了解关于时间的收敛性. 相当广泛地解决了一类PEPA模型的Fluid逼近所导出的微分方程的解的收敛性的公开问题；(4)我们为PEPA模型建立了大偏差理论；（5）我们开展了PEPA模型的Fluid逼近的应用研究，特别是在提取通信系统性能方面的应用；我们还开展了性能建模与分析领域的其他一些相关研究（主要是信息安全领域的性能分析）。. 本项目研究所获得的这些成果不仅拓展了随机进程代数在死锁检测和性能分析方面的进一步应用，并且为这些应用奠定相关理论基础。