概率進(jìn)程演算的互模擬分析.pdf

1、隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)通信技術(shù)的高速發(fā)展，以并發(fā)性、分布性、實(shí)時(shí)性、片構(gòu)性和互操作性等主要特征的并發(fā)分布式系統(tǒng)已成為計(jì)算機(jī)技術(shù)的主流力向。并發(fā)現(xiàn)象以其同有的復(fù)雜性，對(duì)計(jì)算機(jī)科學(xué)家提出了挑戰(zhàn)。與順序計(jì)算不同，我們對(duì)并行與并發(fā)計(jì)算實(shí)質(zhì)的認(rèn)識(shí)尚處于初級(jí)階段。進(jìn)程代數(shù)主要足用米描述并發(fā)計(jì)算的數(shù)學(xué)模型，它研究并發(fā)現(xiàn)象，即多個(gè)計(jì)算主體(進(jìn)程)同時(shí)活動(dòng)，通過交換信息(通訊)進(jìn)行協(xié)作，以共同完成預(yù)期任務(wù)的特定計(jì)算現(xiàn)象。對(duì)并發(fā)理論的研究，進(jìn)程間的等價(jià)是需要

2、關(guān)注的重點(diǎn)。兩個(gè)進(jìn)程在什么叫候具有相似的行為可以用等價(jià)關(guān)系描述他們。最近，在一些用來解決并發(fā)系統(tǒng)問題的算法構(gòu)造中，隨機(jī)被證明是一種很用的工具。傳統(tǒng)上，對(duì)形式化建模并發(fā)系統(tǒng)的進(jìn)程演算是不進(jìn)行定量分析的，結(jié)果，對(duì)于一個(gè)并發(fā)系統(tǒng)會(huì)以多大的概率來發(fā)生某個(gè)動(dòng)作就無法提供有用的信息。而從應(yīng)用的角度來說，有必要進(jìn)行定量分析，因?yàn)樵诒举|(zhì)上并發(fā)系統(tǒng)的許多方面是與隨機(jī)相關(guān)的。 本文把進(jìn)程的定量信息限制在概率信息上，在研究帶有概率信息的進(jìn)程時(shí)，路徑等

3、價(jià)是把概率看成是一個(gè)動(dòng)作，這是不可取得，因?yàn)檫@意味著只有在路徑上的所有動(dòng)作包括概率完全一致情況下，進(jìn)程才是路徑等價(jià)的。所以，過分的依賴于概率信息，導(dǎo)致路徑等價(jià)的概念存在著很大的缺陷。我們認(rèn)為，在進(jìn)程中山現(xiàn)的概率不應(yīng)該被看成是個(gè)動(dòng)作，而應(yīng)該是進(jìn)程發(fā)生隨機(jī)事什的可能性。從而，我們想使用一個(gè)關(guān)于進(jìn)程間近似程度的概念來替代路徑等價(jià)。主要內(nèi)容及創(chuàng)新點(diǎn)包括：①綜合以前的結(jié)果，提山一種新的metric的定義，并把它和路徑等價(jià)相關(guān)聯(lián)，同叫證明了概率進(jìn)程