隱藏信息檢測與還原技術(shù)

第二部分分布式算法

第四次課中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)系國家高性能計(jì)算中心（合肥）1第三章環(huán)上選舉算法2本章提綱Leader選舉問題匿名環(huán)異步環(huán)同步環(huán)3問題 在一組處理器中選出一個特殊結(jié)點(diǎn)作為leader用途簡化處理器之間的協(xié)作； 有助于達(dá)到容錯和節(jié)省資源。 例如，有了一個leader，就易于實(shí)現(xiàn)廣播算法代表了一類破對稱問題。 例如，當(dāng)死鎖是由于處理器相互環(huán)形等待形成時，可使用選舉算法，找到一個leader并使之從環(huán)上刪去，即可打破死鎖。4§3.1leader選舉問題

Leader選舉問題：問題從具有同一狀態(tài)的進(jìn)程配置開始，最終達(dá)到一種配置狀態(tài)。每個處理器最終確定自己是否是一個leader，但只有一個處理器確定自己是leader，而其他處理器確定自己是non-leader。

算法的作用：如果要執(zhí)行一個分布式算法，且沒有一個優(yōu)先的優(yōu)選人做為算法的初始進(jìn)程，就要進(jìn)行進(jìn)程選舉。(例如指定根的DFS樹的生成問題)

5§3.1leader選舉問題

選舉算法的定義：（1）每個處理器具有相同的局部算法；（2）算法是分布式的，處理器的任意非空子集都能開始一次計(jì)算；

（3）每次計(jì)算中，算法達(dá)到終止配置。在每一可達(dá)的終止配置中，只有一個處理器處于領(lǐng)導(dǎo)人狀態(tài)，其余均處于失敗狀態(tài)。

一個算法解決了leader選舉問題需滿足(根據(jù)形式化模型)：終止?fàn)顟B(tài)被劃分為兩類：選中和未選中狀態(tài)。一旦一個處理器進(jìn)入選中(或未選中)狀態(tài)，則該處理器上的轉(zhuǎn)換函數(shù)將只會將其變?yōu)橄嗤臓顟B(tài)；在每個容許執(zhí)行里，只有一個處理器進(jìn)入選中狀態(tài)，其余處理器進(jìn)入非選中(non-selected)狀態(tài)。 本章只討論系統(tǒng)的拓?fù)浣Y(jié)構(gòu)是環(huán)的情況。（此項(xiàng)有時可以弱化）6§3.1leader選舉問題環(huán)的形式化模型 對每個i，0≤i≤n-1，

Pi到Pi+1的邊標(biāo)號為1，稱為左(順時針) Pi到Pi-1的邊標(biāo)號為2，稱為右(逆時針)

這里的標(biāo)號加減均是modn的環(huán)網(wǎng)絡(luò)之所以吸引了如此多的研究，是因?yàn)樗鼈兊男袨橐子诿枋?；且從環(huán)網(wǎng)絡(luò)推導(dǎo)出的下界，可應(yīng)用于具有任意拓?fù)浣Y(jié)構(gòu)的網(wǎng)絡(luò)算法設(shè)計(jì)7§3.2匿名環(huán)（anonymous）匿名算法：若環(huán)中處理器沒有唯一的標(biāo)識符，則環(huán)選舉算法是匿名的。更形式化的描述：每個處理器在系統(tǒng)中具有相同的狀態(tài)機(jī)，在這種算法里，msg接收者只能根據(jù)信道標(biāo)號來區(qū)別。（一致性的）uniform算法：若算法不知道處理器數(shù)目，則算法稱之為uniform，因?yàn)樵撍惴▽γ總€n值看上去是相同的。non-uniform算法：算法已知處理器數(shù)目n形式化描述：在一個匿名、一致性的算法中，所有處理器只有一個狀態(tài)機(jī)；在一個匿名、非一致性的算法中，對每個n值（處理器數(shù)目）都有單個狀態(tài)機(jī)，但對不同規(guī)模有不同狀態(tài)機(jī)，也就是說n可以在代碼中顯式表達(dá)。8§3.2匿名環(huán)（anonymous）對于環(huán)系統(tǒng)，不存在匿名的選舉算法。 為簡單起見，我們只證明

非均勻（非一致性）算法：非均勻算法（n已知）的不可能性=>均勻（n未知）算法的不可能性。Ex3.1證明同步環(huán)系統(tǒng)中不存在匿名的、一致性的領(lǐng)導(dǎo)者選舉算法。

同步算法：同步算法的不可能性=>異步算法的不可能性。（同步是異步的一種特例）

Ex3.2證明異步環(huán)系統(tǒng)中不存在匿名的領(lǐng)導(dǎo)者選舉算法。9§3.2匿名環(huán)同步算法的不可能性

在同步系統(tǒng)中，一個算法以輪的形式進(jìn)行。每輪里所有待發(fā)送msg被傳遞，隨后每個處理器進(jìn)行一步計(jì)算。一個處理器的初始狀態(tài)包括在outbuf里的任何msg。這些消息在第一輪里被傳遞到某處理器的左和右鄰居。

不可能性：

①在一個匿名環(huán)中，處理器間始終保持對稱，若無某種初始的非對稱(如，標(biāo)識符唯一)，則不可能打破對稱。在匿名環(huán)算法里，所有處理器開始于相同狀態(tài)。

②因?yàn)樗麄儓?zhí)行同樣的程序(即他們的狀態(tài)機(jī)相同)，在每輪里各處理器均發(fā)送同樣的msg，所以在每一輪里各處理器均接收同樣的msg，改變狀態(tài)亦相同。 因此，若選中一個處理器，則其他所有處理器亦被選中。因此，不可能有一個算法在環(huán)中選中單個處理器為leader。10§3.2匿名環(huán)假設(shè)R是大小為n>1的環(huán)（非均勻），A是其上的一個匿名算法，它選中某處理器為leader。因?yàn)榄h(huán)是同步的且只有一種初始配置，故在R上A只有唯一的合法執(zhí)行。Lemma3.1

在環(huán)R上算法A的容許執(zhí)行里，對于每一輪k，所有處理器的狀態(tài)在第k輪結(jié)束時是相同的。

Pf.

對k用歸納法

K=0(第一輪之前)，因?yàn)樘幚砥髟陂_始時都處在相同的初始狀態(tài)，故結(jié)論是顯然的。 設(shè)引理對k-1輪成立。因?yàn)樵谠撦喞锔魈幚砥魈幵谙嗤瑺顟B(tài)，他們都發(fā)送相同的消息mr到右邊，同樣的消息ml到左邊，所以在第k輪里，每處理器均接收右邊的ml

，左邊的mr

。因此，所有處理器在第k輪里接收同樣的消息，又因?yàn)樗鼈兙鶊?zhí)行同樣的程序，故第k輪它們均處于同樣的狀態(tài)。11§3.2匿名環(huán) 上述引理蘊(yùn)含著：若在某輪結(jié)束時，一個處理器宣布自己是leader(進(jìn)入選中狀態(tài))，則其它處理器亦同樣如此，這和A是一個leader選舉算法的假定矛盾！因此證明：Th3.2

對于同步環(huán)上的leader選舉，不存在非均勻的匿名算法。＋＋同步環(huán)→異步環(huán)非一致性→一致性算法↓↓對于環(huán)系統(tǒng)，不存在匿名的選舉算法12§3.3異步環(huán)

本節(jié)將討論異步環(huán)上leader選舉問題的msg復(fù)雜性上下界。 由Th3.2知，對環(huán)而言沒有匿名的leader選舉算法存在。因此以下均假定處理器均有唯一標(biāo)識符。 當(dāng)一個狀態(tài)機(jī)(局部程序)和處理器Pi聯(lián)系在一起時，其狀態(tài)成分變量idi被初始化為Pi的標(biāo)識符的值，故各處理器的狀態(tài)是有區(qū)別的。環(huán)系統(tǒng)：通過指派一個處理器列表按順時針(從最小標(biāo)識符起)指定環(huán)。注意是通過id排列，不是通過Pi的下標(biāo)i來排列(0≤i≤n-1)，假定idi是Pi的標(biāo)識符。（因?yàn)橄聵?biāo)i通常是不可獲得的）13§3.3異步環(huán)在非匿名算法中，均勻（一致性）和非均勻（非一致性）的概念稍有不同均勻算法：每個標(biāo)識符id，均有一個唯一的狀態(tài)機(jī)，但與環(huán)大小n無關(guān)。而在匿名算法中，均勻則指所有處理器只有同一個狀態(tài)。（不管環(huán)的規(guī)模如何，只要處理器分配了對應(yīng)其標(biāo)識符的唯一狀態(tài)機(jī)，算法就是正確的。）非均勻算法：每個n和每個id均對應(yīng)一個狀態(tài)機(jī)，而在匿名非均勻算法中，每個n值對應(yīng)一個狀態(tài)機(jī)。（對每一個n和給定規(guī)模n的任意一個環(huán)，當(dāng)算法中每個處理器具有對應(yīng)其標(biāo)識符的環(huán)規(guī)模的狀態(tài)機(jī)時，算法是正確的。） 下面將討論msg復(fù)雜性：O(n2)→O(nlogn)→Ω(nlogn)§3.3.1一個O(n2)算法

LeLann、Chang和Roberts給出，LCR算法基本思想每個處理器Pi發(fā)送一個msg(自己的標(biāo)識符)到左鄰居，然后等其右鄰居的msg當(dāng)它接收一個msg時，檢驗(yàn)收到的idj，若idj>idi，則Pi轉(zhuǎn)發(fā)idj給左鄰，否則沒收idj(不轉(zhuǎn)發(fā))。下界14§3.3.1一個O(n2)算法若某處理器收到一個含有自己標(biāo)識符的msg，則它宣布自己是leader，并發(fā)送一個終止msg給左鄰，然后終止。當(dāng)一處理器收到一個終止msg時，向左鄰轉(zhuǎn)發(fā)此消息，然后作為non-leader終止。

因?yàn)樗惴ú灰蕾囉趎，故它是均勻的。

i—表示id單向15§3.3.1一個O(n2)算法CodeforPiinitvar:asleep←true,id←IBeginWhile(receivingnomessage)do(1)ifasleepdo(1.1)asleep←false(1.2)send<id>toleft-negihborendifEndwhileWhile(receiving<i>fromright-neighbor)do(1)ifid<<i>thensend<i>toleft-neighborendif(2)ifid=<i>then(2.1)send<Leader,i>toleft-neighbor(2.2)terminatesasLeaderendifEndwhileWhile(receiving<Leader,j>fromright-neighbor)do(1)send<Leader,j>toleft-neighbor(2)terminatesasnon-LeaderEndwhileend1617§3.3.1一個O(n2)算法分析

正確性

在任何容許執(zhí)行里，只有最大標(biāo)識符idmax不被沒收，故只有具有idmax的處理器接受自己的標(biāo)識符并宣布是leader，其他處理器不會被選中，故算法正確。msg復(fù)雜性

在任何容許執(zhí)行里，算法絕不會發(fā)送多于O(n2)個msgs，更進(jìn)一步，該算法有一個容許執(zhí)行發(fā)送O(n2)個msgs：1718§3.3.1一個O(n2)算法

考慮處理器標(biāo)識符為0，1，…，n-1構(gòu)成的環(huán)，其次序如右圖： 在這種配置里，id=i的處理器的msg恰好被發(fā)送i+1次，即發(fā)送到i-1,i-2,…,1,0，直到n-1時沒收。因此，msg總數(shù)為：1819§3.3.2一個O(nlgn)算法

仍然是繞環(huán)發(fā)送id，但使用更聰明的方法。保證最大id在環(huán)上周游且返回。k鄰居

一個處理器Pi的k鄰居是一個處理器集合：該集合中的任一處理器與Pi在環(huán)上的距離至多是k，一個處理器的k-鄰居集合中恰好有2k+1個處理器。

k=3，共有7個結(jié)點(diǎn)1920§3.3.2一個O(nlgn)算法基本思想

算法按階段執(zhí)行，在第l階段一個處理器試圖成為其2l-鄰接的臨時leader。只有那些在l-th階段成為臨時領(lǐng)袖的處理器才能繼續(xù)進(jìn)行到(l+1)th階段。因此，l越大，剩下的處理器越少。直至最后一個階段，整個環(huán)上只有一個處理器被選為leader。具體實(shí)現(xiàn)phase0:每個結(jié)點(diǎn)發(fā)送1個probe消息(其中包括自己的id)給兩個1-鄰居，若接收此msg的鄰居的id大于消息中的id，則沒收此msg；否則接收者發(fā)回一個replymsg。若一個結(jié)點(diǎn)從它的兩個鄰居收到回答msgreply，則該結(jié)點(diǎn)成為phase0里它的1-鄰居的臨時leader，此結(jié)點(diǎn)可繼續(xù)進(jìn)行phase1。2021§3.3.2一個O(nlgn)算法phasel：在l-1階段中成為臨時leader的處理器Pi發(fā)送帶有自己id的probe消息至它的2l鄰居。若此msg中的id小于左右兩個方向上的2*2l個處理器中任一處理器的id，則此msg被沒收。若probe消息到達(dá)最后一個鄰居而未被沒收，則最后一個處理器發(fā)送reply消息給Pi，若Pi從兩個方向均接收到reply消息，則它稱為該階段中2l鄰居的臨時leader，繼續(xù)進(jìn)入下一階段。終止：接收到自己的probe消息的結(jié)點(diǎn)終止算法而成為leader，并發(fā)送一個終止msg到環(huán)上。2122§3.3.2一個O(nlgn)算法控制probemsg的轉(zhuǎn)發(fā)和應(yīng)答

probe消息中有三個域：<prob,id,l,hop> id-標(biāo)識符

l-階段數(shù)

hop-跳步計(jì)數(shù)器：初值為0，結(jié)點(diǎn)轉(zhuǎn)發(fā)probe消息時加1.

若一結(jié)點(diǎn)收到的probe消息時，hop值為2l，則它是2l鄰居中最后一個處理器。若此時msg未被沒收也不能向前轉(zhuǎn)發(fā)，而應(yīng)該是向后發(fā)回reply消息。2223§3.3.2一個O(nlgn)算法算法：Alg3.1異步leader選舉

varasleepinittrue;

uponreceivingnomsg:ifasleepthen{ asleep:=false;//每個結(jié)點(diǎn)喚醒后不再進(jìn)入此代碼

send<probe,id,0,0>toleftandright;}

uponreceiving<probe,j,l,d>fromleft(resp,right):

if(j=id)then//收到自己id終止，省略發(fā)終止msgterminateastheleader;

if(j>id)and(d<2l)then//向前轉(zhuǎn)發(fā)probemsg send<probe,j,l,d+1>toright(resp,left)2324§3.3.2一個O(nlgn)算法

if(j>id)and(d≥2l)then//到達(dá)最后一個鄰居仍未沒收

send<reply,j,l>toleft(resp,right)//回答

//若j<id,則沒收probe消息uponreceiving<reply,j,l>fromleft(resp,right):ifj≠idthensend<reply,j,l>toright(resp,left);//轉(zhuǎn)發(fā)replyelse//j=id時，Pi已收到一個方向的回答msg ifalreadyreceived<reply,j,l>fromright(resp,left)then//也收到另一方向發(fā)回的reply send<probe,id,l+1,0>toleftandright; //Pi是phasel的臨時leader，繼續(xù)下一階段2425§3.3.2一個O(nlgn)算法分析正確性：因?yàn)榫哂凶畲骾d的處理器的probe消息是不會被任何結(jié)點(diǎn)沒收的，所以該處理器將作為leader終止算法；另一方面，沒有其他probe消息能夠周游整個環(huán)而不被吞沒。因此，最大id的處理器是算法選中的唯一的leader。msg復(fù)雜性（最壞情況下） 在phasel

里：一個處理器啟動的msg數(shù)目至多為：4*2l有多少個處理器是啟動者呢？

-l=0，有n個啟動著（最多）

-l≥1，在l-1階段結(jié)束時成為臨時leader的節(jié)點(diǎn)均是啟動者2526§3.3.2一個O(nlgn)算法Lemma3.3

對每個k≥1，在phasek結(jié)束時，臨時leader數(shù)至多為n/(2k+1).pf:

若一結(jié)點(diǎn)Pi在k階段結(jié)束時是一臨時leader，則在Pi的2k-鄰居里每個結(jié)點(diǎn)的id均小于Pi的id。

在該階段里，距離最近的兩個臨時leaderPi和Pj必滿足：

Pi的2k鄰居的左邊恰好Pj的2k-鄰居的右邊，即Pi和Pj之間有2k個處理器。 因此，在phasek里臨時leader的最大數(shù)目必是以上述方式分布的，因?yàn)槊?k+1個結(jié)點(diǎn)至多有一個臨時leader，所以leader數(shù)至多是n/(2k+1).2627§3.3.2一個O(nlgn)算法Th3.4.存在一個異步的leader選舉算法，其msg復(fù)雜性為O(nlgn).Pf: 由lemma3.3知，知道phaselg(n-1)時只剩下一個leader(最后的leader).msg總數(shù)：

i)phase0:msg數(shù)為4n. ii)終止msgs：n.Note:雙向通信.該msg復(fù)雜性的常數(shù)因子不是最優(yōu)的.2728§3.3.3下界Ω(nlgn) 現(xiàn)證明對于uniform算法，異步環(huán)里任何leader選舉算法至少發(fā)送Ω(nlgn)個msgs。

我們的下界證明是針對leader選舉問題的一個變種：選中的leader必定是環(huán)上具有最大id的處理器。所有處理器必須知道被選中l(wèi)eader的id，即每處理器終止前，將選中l(wèi)eader的id寫入一個特殊變量?；舅枷?。 設(shè)A是一個能解上述leader選舉變種問題的均勻算法，證明存在A的一個允許執(zhí)行，其中發(fā)送了Ω(nlgn)個msgs，證明采用構(gòu)造法。2829§3.3.3下界Ω(nlgn)

對于大小為n/2的環(huán)構(gòu)造算法的一個耗費(fèi)執(zhí)行(指msg的耗費(fèi))，然后將兩個大小為n/2的不同環(huán)粘貼在一起形成一個大小為n的環(huán)，將兩個較小環(huán)上的耗費(fèi)執(zhí)行組合在一起，并迫使θ(n)個附加msg被接收。調(diào)度：前面定義過調(diào)度是執(zhí)行中的事件序列，下面給出能夠被粘貼在一起的調(diào)度。Def3.1開調(diào)度 設(shè)σ是一個特定環(huán)上算法A的一個調(diào)度，若該環(huán)中存在一條邊e使得在σ中，邊e的任意方向上均無msg傳遞，則σ稱為是open，e是σ的一條開邊。這種擴(kuò)展依賴于算法是一致的且對各種規(guī)模的環(huán)以相同的方式執(zhí)行2930§3.3.3下界Ω(nlgn)Note：開調(diào)度未必是容許的調(diào)度，即它可能是有限的事件序列，環(huán)上的處理器不一定是終止的。 直觀上，既然處理器不知道環(huán)的大小，我們能將兩個較小的開調(diào)度粘貼為一個較大環(huán)的開調(diào)度，其依據(jù)是：算法是均勻的。 為簡單起見，不放設(shè)n為2的整數(shù)次冪。Th3.5對于每個n及每個標(biāo)識符集合(大小為n)，存在一個由這些標(biāo)識符組成的環(huán)，該環(huán)有一個A的開調(diào)度，其中至少接收M(n)個消息，這里：

3031§3.3.3下界Ω(nlgn) 顯然遞歸方程的解為M(n)=θ(nlgn)，他蘊(yùn)含了異步環(huán)選舉問題消息復(fù)雜度下界。下面用歸納法證明之，其中Lemma3.6對每個由兩個標(biāo)識符構(gòu)成的集合，存在一個使用這兩個標(biāo)識符的環(huán)R，R有A的一個開調(diào)度，其中至少有一個msg被接受。（歸納基礎(chǔ)）pf：假定R有兩個處理器P0和P1，其標(biāo)識符分別為x和y，不妨設(shè)x>y.3132§3.3.3下界Ω(nlgn)

設(shè)α是A的一個容許執(zhí)行，因?yàn)锳是正確的，在α中，最終P1定將P0的標(biāo)識符寫入其中。因此，α中至少須接收一個msg，否則P1不知道P0的標(biāo)識符為x.

設(shè)σ是α的調(diào)度的最短前綴：它包括第一個接受msg的事件。因?yàn)闆]有接收第一條msg的邊是開的，因此σ中只有一個msg被接收且有一條開邊，故引理成立。故σ是滿足引理的開調(diào)度。

Lemma3.7選擇n>2，假定對每個大小為n/2標(biāo)識符集合，存在一個使用這些標(biāo)識符的環(huán)，它有A的一個開調(diào)度，其中至少接收M(n/2)個msgs(歸納假設(shè))，那么對于n個標(biāo)識符的每個集合，存在一個使用這些標(biāo)識符集的環(huán)，它有A的一個開調(diào)度，其中接收至少2M(n/2)+(n/2-1)/2個msgs(歸納步驟)。3233§3.3.3下界Ω(nlgn)

pf：設(shè)S是n個標(biāo)識符的集合，將S劃分為兩個集合S1和S2，每個大小為n/2，由假設(shè)分別存在一個使用S1和S2中標(biāo)識符的環(huán)R1和R2，它們分別有A的一個開調(diào)度σ1和σ2，其中均至少接收M(n/2)個msgs，設(shè)e1和e2分別是σ1和σ2的開邊，不妨設(shè)鄰接于e1和e2的處理器分別是p1，q1和p2，q2，將e1，e2刪去，用ep鏈接p1和p2，eq鏈接q1和q2，即可將兩個環(huán)R1和R2粘貼在一起形成環(huán)R。 現(xiàn)說明如何在R上構(gòu)造一個A的開調(diào)度σ，其中至少有2M(n/2)+(n/2-1)/2個msg被接收。其想法是先讓每個較小環(huán)分別執(zhí)行“耗費(fèi)”的開調(diào)度。

3334§3.3.3下界Ω(nlgn)

1)σ1σ2構(gòu)成R上A的一個開調(diào)度

考慮從R的初始配置開始發(fā)生的事件序列σ1，因?yàn)镽1中的處理器由這些事件并不能區(qū)別R1是一個獨(dú)立的環(huán)還是R的一個子環(huán)，它們執(zhí)行σ1恰像R1是獨(dú)立的那樣?？紤]環(huán)R上后續(xù)事件序列σ2(與上類似)，因?yàn)闆]有msg在ep和eq上傳遞，故R2中處理器在σ2中亦不能區(qū)別R2是獨(dú)立環(huán)還是R的子環(huán)。

因此，σ1σ2是一個調(diào)度，其中至少有2M(n/2)個msgs被接收。

2)現(xiàn)說明如何通過連通ep和eq(但不是二者)來迫使算法接收(n/2-1)/2個附加的msgs。

考慮每個形式為σ1σ2σ3的有限調(diào)度，因?yàn)棣?σ2中ep和eq均為開的，若σ3中存在一邊上至少有(n/2-1)/2個msg被接收，則σ1σ2σ3是要找的開調(diào)度，引理被證。

假設(shè)沒有這樣的調(diào)度，那么存在某個調(diào)度σ1σ2σ3，它導(dǎo)致相應(yīng)執(zhí)行中的一個“靜止”配置。(配置：由全體結(jié)點(diǎn)狀態(tài)構(gòu)成)

一個處理器狀態(tài)是“靜止”的：若從該狀態(tài)開始的計(jì)算事件序列中不send消息，即處理器接收一個msg之前不發(fā)送另一msg（即處理器的內(nèi)部事件不引發(fā)send動作）3435§3.3.3下界Ω(nlgn) 一個配置是“靜止”的(關(guān)于ep和eq)：若除開邊ep和eq外，沒有msgs處在傳遞之中，每個處理器均為靜止?fàn)顟B(tài)。 不失一般性，假設(shè)R中最大id的處理器是在子環(huán)R1中，因?yàn)闆]有msg從R1傳到R2中，R2中的處理器不知道leader的id，因此R2里沒有處理器能夠在σ1σ2σ3結(jié)束時終止。(在σ1σ2σ3結(jié)束時，R2里無結(jié)點(diǎn)終止)

我們斷定在每個擴(kuò)展σ1σ2σ3的容許調(diào)度里，子環(huán)R2里的每個處理器在終止前必須接收至少一個附加msg，因?yàn)镽2里每一處理器只有接收來自R1的msg才知道leader的id。 上述討論清楚地蘊(yùn)含在環(huán)R上必須接收Ω(n/2)個msgs，但因?yàn)閑p和eq是連通的，故調(diào)度未必是開的，即兩邊上均可能傳遞msg。 但若能說明ep或eq只