計(jì)算機(jī)科學(xué)導(dǎo)論 實(shí)驗(yàn)四

第第頁(yè)計(jì)算機(jī)科學(xué)導(dǎo)論實(shí)驗(yàn)四：系統(tǒng)（“淝水之戰(zhàn)”）實(shí)驗(yàn)報(bào)告1408班第4組小組成員：房子祺、何慧卉、李永明、吳崇祎、王溫博實(shí)驗(yàn)?zāi)康睦斫庀到y(tǒng)的模塊化，抽象化概念，能夠使用多種模塊完成一個(gè)獨(dú)立抽象系統(tǒng)的構(gòu)建，完成指定目標(biāo)；理解分布式系統(tǒng)與獨(dú)立系統(tǒng)的關(guān)系，嘗試約定一種協(xié)議保證分布式系統(tǒng)的容錯(cuò)性。第一階段構(gòu)建部隊(duì)子系統(tǒng)對(duì)系統(tǒng)構(gòu)建要求進(jìn)行分析，構(gòu)建出唯一正確的系統(tǒng)結(jié)構(gòu)：要求做法操作類(lèi)型有唯一的標(biāo)示可以將你的部隊(duì)子系統(tǒng)與其他人的部隊(duì)子系統(tǒng)進(jìn)行區(qū)分將人物屬性加入部隊(duì)模塊拖動(dòng)你能與其他人的部隊(duì)子系統(tǒng)進(jìn)行通信將釋放信鴿接口加入部隊(duì)模塊你能與其他人的部隊(duì)子系統(tǒng)進(jìn)行決策將開(kāi)始攻擊和拒絕攻擊接口加入部隊(duì)模塊你進(jìn)行決策時(shí)，應(yīng)該依據(jù)部隊(duì)的狀態(tài)進(jìn)行調(diào)整，即整備狀態(tài)與就緒狀態(tài)將整備狀態(tài)和就緒狀態(tài)屬性加入部隊(duì)模塊部隊(duì)狀態(tài)是反映你的部隊(duì)能否進(jìn)行戰(zhàn)斗的直接建議指標(biāo)，它受到糧草數(shù)量，士兵數(shù)量，天氣狀況的共同影響將糧食、兵力、天氣模塊連線到部隊(duì)模塊連線糧草數(shù)量，士兵數(shù)量，天氣狀態(tài)會(huì)在每一天到來(lái)時(shí)發(fā)生隨機(jī)的變化（比如補(bǔ)給或消耗）將日期發(fā)生器和隨機(jī)數(shù)生成器模塊分別連線到糧食、兵力、天氣模塊你應(yīng)該指明部隊(duì)這三個(gè)外在變量變化滿(mǎn)足什么樣的條件時(shí)，部隊(duì)狀態(tài)如何被調(diào)整點(diǎn)擊部隊(duì)模塊，設(shè)置控制邏輯點(diǎn)擊設(shè)置參數(shù)關(guān)于操作類(lèi)型的說(shuō)明：對(duì)于各個(gè)模塊，只能進(jìn)行拖動(dòng)和連線操作；其中屬性只能被拖入模塊當(dāng)中。對(duì)于模塊的內(nèi)部邏輯，則通過(guò)點(diǎn)擊模塊進(jìn)行設(shè)置。對(duì)模塊化的理解：外部簡(jiǎn)略，內(nèi)部實(shí)現(xiàn)。將不同各項(xiàng)功能模塊化，可以使整個(gè)系統(tǒng)顯得結(jié)構(gòu)清楚，使系統(tǒng)的構(gòu)建更為清晰、簡(jiǎn)單。構(gòu)建成功效果圖：第二階段進(jìn)行分布式戰(zhàn)役分析題目：勝利條件（分布式系統(tǒng)的容錯(cuò)性）一致性條件：所有忠臣將軍作出相同的決策。有效性條件：少數(shù)忠臣將軍應(yīng)服從多數(shù)忠臣將軍的狀態(tài)進(jìn)行決策，數(shù)量相同時(shí)進(jìn)行任意決策。終止性條件：所有忠臣將軍都做出了決策。當(dāng)忠臣部隊(duì)中為就緒狀態(tài)的數(shù)量為2時(shí)，只需保證忠臣的決策一致：方法1.約定一致做出攻擊決策；（算法1）方法2.加入奸臣的狀態(tài)。若有不少于2名忠臣看到他的狀態(tài)為就緒，則認(rèn)為他的狀態(tài)為就緒（指向他的箭頭至少有2個(gè)綠色），否則認(rèn)為他的狀態(tài)是等待。若全體就緒人數(shù)達(dá)到3人，則攻擊。（算法2、3）關(guān)鍵：讓4名忠臣對(duì)戰(zhàn)場(chǎng)情況得出不錯(cuò)誤且一致的認(rèn)識(shí)（不必識(shí)別出奸臣）（算法3）進(jìn)行調(diào)研：是否存在保證忠臣勝利的算法？經(jīng)過(guò)調(diào)研，發(fā)現(xiàn)與之相似的問(wèn)題——拜占庭將軍問(wèn)題（Byzantinefailures）。已證明此問(wèn)題中，如果有m個(gè)叛國(guó)將軍，將軍總數(shù)不少于3m+1個(gè)時(shí)，存在算法能使口頭消息傳遞達(dá)到一致，滿(mǎn)足勝利條件。與“淝水之戰(zhàn)”的不同之處：不要求有效性條件淝水之戰(zhàn)中有1個(gè)奸臣，共5名將軍，5≥3×1+1=4，故一定存在保證忠臣勝利的算法。我們的探究過(guò)程為了設(shè)計(jì)出保證忠臣勝利的算法，需思考下述問(wèn)題：奸臣有哪些操作可能導(dǎo)致忠臣做出錯(cuò)誤決策？忠臣在看到的情況為(3,2)時(shí)，比較容易出現(xiàn)決策錯(cuò)誤。忠臣狀態(tài)為(3,1)時(shí)，奸臣可有如下操作，使：看到(4,1)的忠臣數(shù)看到(3,2)的忠臣數(shù)04圖形特征：箭尾(3,1)的人數(shù)≥4，

可立即決策13如何與忠臣狀態(tài)(2,2)的情況區(qū)分？22會(huì)有2個(gè)及以上忠臣立即決策（有被奸臣指錯(cuò)自己的），剩余忠臣也隨即決策3140我們將可能出現(xiàn)的情況畫(huà)圖（圖一）列出，進(jìn)行分析，尋找可以作為區(qū)分兩種情況依據(jù)的圖形特征。觀察發(fā)現(xiàn)，(3,1)與(2,2)的特征性差別在于，(3,1)的情況下，一定會(huì)有1位忠臣看到的是(4,1)的情況，并已做出決策。因此想到算法1第三步中，把此人自身的狀態(tài)與他發(fā)出的箭頭合起來(lái)看的方法。圖SEQ圖\*ARABIC1設(shè)計(jì)算法列舉所有可能出現(xiàn)的情況忠臣狀態(tài)干擾后可能看到的情況決策情況（4，0）（5，0）立即作出正確決策(唯一):就緒狀態(tài)較多時(shí)發(fā)動(dòng)攻擊等待狀態(tài)較多時(shí)拒絕攻擊（4，1）（3，1）（4，1）（3，2）對(duì)于方法1：需分辨忠臣狀態(tài)是(3,1)還是(2,2)。根據(jù)約定，若為3人等待、1人就緒，則拒絕攻擊；其他情況下均發(fā)動(dòng)攻擊。對(duì)于方法2：需識(shí)別奸臣。（2，2）（3，2）（2，3）算法1（方法1）新的一天開(kāi)始。第一步：廣播自身狀態(tài)。忠臣如實(shí)，奸臣任意。以下情況下，忠臣做出決策：若看到就緒人數(shù)≥4，攻擊；若看到就緒人數(shù)≤2 拒絕；若看到就緒人數(shù)=3，且有不少于2人已做出決策，攻擊；若看到就緒人數(shù)=2，且有不少于2人已做出決策，拒絕。安全度過(guò)一天或進(jìn)入第二步。第二步：廣播自己看到的其余4人的狀態(tài)。忠臣如實(shí)，奸臣任意。若看到某人被指2紅2綠，或指錯(cuò)自己的狀態(tài)，可斷定此人為奸臣。此時(shí)若忠臣就緒人數(shù)≥2，則攻擊；若忠臣就緒人數(shù)=1，則拒絕。若已有不少于2人做出決策，可斷定此時(shí)忠臣狀態(tài)為(3,1)。此時(shí)若5名將領(lǐng)中就緒人數(shù)≥3，攻擊；若5名將領(lǐng)中就緒人數(shù)≤2，拒絕。安全度過(guò)一天或進(jìn)入第三步。第三步：對(duì)其余4人逐個(gè)進(jìn)行如下分析：把此人自身的狀態(tài)與他發(fā)出的箭頭合起來(lái)看，若存在一人的視角中總體情況為4紅1綠，可斷定此時(shí)忠臣中只有1人就緒，決策拒絕。（此時(shí)必定至少有1人已做出決策）否則，決策攻擊。安全度過(guò)一天，進(jìn)入下一天。算法2矛盾數(shù)辨奸臣（方法2）一、無(wú)矛盾圖在這種情況下中至少可以確定奸臣在所有人眼里的顏色相同，那么五個(gè)人的自身狀態(tài)在所有人的圖里就是共同點(diǎn)，直接通過(guò)五人狀態(tài)確定策略即可。二、矛盾圖1、辨奸臣定義狀態(tài)數(shù)組（x1,x2,x3,x4,x5）x1,x2,x3,x4,x5∈{0,1}(1)、x1=x2=x3=x4=x5忠奸不分(2)、x1=x2=x3=x4≠x5：“單異色元”(3)、x1≠x2=x3：奸臣！關(guān)于(1)、(2)若五個(gè)元素均為情況(1)，則該圖為無(wú)矛盾圖若五個(gè)元素中存在情況(3)，則奸臣已定若五個(gè)元素中不存在情況(3)且存在情況(2)，則——單異色元的討論產(chǎn)生：奸臣誤導(dǎo)：箭頭末端是奸臣奸臣污蔑：箭頭首端是奸臣結(jié)論：?jiǎn)萎惿漠a(chǎn)生都與奸臣有關(guān)3個(gè)或以上單異色元根據(jù)抽屜原理，單異色元只分兩類(lèi)，至少有兩個(gè)單異色元同屬奸臣誤導(dǎo)或奸臣污蔑，那么同時(shí)被矛盾箭頭指向或發(fā)出兩個(gè)矛盾箭頭的即為奸臣。2個(gè)或以下單異色元α.2個(gè)單異色元矛盾不重疊：同上可確認(rèn)奸臣身份矛盾重疊：同色矛盾：兩者完全等價(jià)，假設(shè)一個(gè)是奸臣即可異色矛盾：同時(shí)去掉這兩個(gè)元素，依照剩下三人決策β.1個(gè)單異色元：按照大多數(shù)人的意見(jiàn)修正自己的圖并依據(jù)5人顏色決策即可。2、決策根據(jù)1的論述，除無(wú)矛盾圖、α異色矛盾重疊圖以及β圖以外，我們可以準(zhǔn)確判斷奸臣身份。進(jìn)而進(jìn)入決策階段。確定奸臣的身份主要目的是保證決策一致性。在所有人的圖中，當(dāng)奸臣已知時(shí)，忠臣的自我聲稱(chēng)以及忠臣對(duì)奸臣的指認(rèn)是非常重要的共享信息，是所有人圖的共同點(diǎn)，通過(guò)這些信息決策自然可以保證決策一致性。因此我們約定：(1)依照指向奸臣的箭頭顏色多者決定奸臣顏色，若兩紅兩綠則視為奸臣未聲明。(2)在就奸臣顏色達(dá)成共識(shí)以后，按照五人顏色作出決策，若奸臣屬于未聲明狀態(tài)，忠臣兩紅兩綠則約定攻擊。注：1、我們的算法中假設(shè)奸臣足夠聰明，操作速度超神，不會(huì)因?yàn)椴僮鬟^(guò)慢而暴露身份。2、所有忠臣約定公布全部信息，如果奸臣不公布全部信息，那么觀察自己的圖中被一個(gè)四人雙向完全圖孤立在外的那個(gè)就是奸臣。算法3通過(guò)之前的探究，理解到問(wèn)題的關(guān)鍵：讓4名忠臣對(duì)戰(zhàn)場(chǎng)情況得出不錯(cuò)誤且一致的認(rèn)識(shí)（不必識(shí)別出奸臣）。在忠臣都如實(shí)廣播的前提下，指向忠臣的4個(gè)箭頭中有3個(gè)是忠臣發(fā)出，必定是此人真實(shí)的狀態(tài)。而指向奸臣的4個(gè)箭頭的顏色情況在所有忠臣的視角中都是相同的，可保證一致性。因此只需：廣播自身狀態(tài)，廣播看到的其余4人的狀態(tài)，如果指向某人的箭頭中有不少于2個(gè)是綠色，則認(rèn)為此人的狀態(tài)是就緒；否則認(rèn)為此人的狀態(tài)是等待。若5人中就緒的較多，則發(fā)動(dòng)攻擊；否則，拒絕攻擊。思考：第一階段與第二階