- 論壇徽章:
- 0
|
|
<p>前兩天看到一篇應(yīng)該屬于“計算機科學(xué)”而非“計算機技術(shù)”的文章，“Knowledge and Common Knowledge in a Distributed Environment”，很遺憾，根據(jù)我目前有限的知識和更為有限的精力，并不能完全讀懂這篇文章，只是能了解個大概意思。</p> <p> 在作者（Halpern，Moses）看來，一個分布式系統(tǒng)中的各個節(jié)點所擁有的Knowledge狀態(tài)，在這個分布式系統(tǒng)中扮演著極其基礎(chǔ)的角色。對這種Knowledge狀態(tài)的描述和理解，可以用于設(shè)計一個分布式協(xié)議，證明該協(xié)議的屬性，理解一個分布式系統(tǒng)的運行等。文章中使用了形式化的方法來定義系統(tǒng)、Knowledge極其狀態(tài)，并且使用這些定義證明了兩個經(jīng)典的問題。作者認為，該形式系統(tǒng)可以用于解決（當(dāng)然指的是理論上的證明）一般性的分布式系統(tǒng)問題。</p> <p> 注：原文大量使用了形式化的定義，在數(shù)學(xué)上十分嚴謹，而本文不再使用那些定義，只是給出我對它們的理解。</p> <p> 什么是一個分布式系統(tǒng)？直觀上講，一個分布式系統(tǒng)包含一組相對獨立的計算節(jié)點{p1, p2, p3, … , pn}；每個節(jié)點的行為僅僅由它本地的信息決定；節(jié)點通過某種網(wǎng)絡(luò)進行連接，節(jié)點之間只能通過消息傳遞進行通信。這里面，“節(jié)點本地的信息”和節(jié)點的knowledge關(guān)系十分緊密。假設(shè)存儲足夠，每一個節(jié)點的本地信息包括該節(jié)點初始時知道的信息，它接收到的所有消息和它觀察到的所有事件。</p> <p> 一個節(jié)點的Knowledge就是由該節(jié)點的本地信息可以知道的所有的事實。當(dāng)然，Knowledge不單單可以關(guān)聯(lián)在一個節(jié)點上，我們也可以討論一組節(jié)點所擁有的knowledge。</p> <p> </p> <p> 先看一個例子：一個家庭有好些個孩子，比如n個，這些孩子每天都一起出去玩，一起回來。如果一個孩子的額頭上沾了泥巴，媽媽就會懲罰他。每個孩子可以看到別的孩子額頭上是否有泥巴，卻看不到自己的。同時，每個孩子都樂于看到別人受到懲罰，所以不會主動告訴別人額頭上是否有泥巴。有一天，這些孩子同時回到家門口，恰好爸爸回來了，爸爸告訴他們說，“至少有一個人的額頭上有泥巴”。之后，爸爸開始不斷地重復(fù)一個問題，“誰頭上有泥巴請回答yes，沒有的請回答no”。假設(shè)每個孩子在不確定自己是否有泥巴時，都會認為自己沒有，會回答“no”，只有確定自己有泥巴時，才會回答“yes”。所有的孩子每次都是同時回答的，他們都是誠實且有足夠的邏輯能力的。問題是如果有k個孩子頭上有泥巴，會出現(xiàn)什么現(xiàn)象？</p> <p> 答案：在爸爸的前k-1個問題時，所有人都回答no，第k個問題時，有泥巴的所有小孩回答yes，其他回答no。</p> <p> 對于這個問題，網(wǎng)上有很多變種，也有詳細的解釋，此處不再贅述。問題在于，如果k>=2，那么每個小孩其實自己都知道“至少有一個人的額頭上有泥巴”這個事實，如果爸爸不宣布這句話而直接開始提問，那么無論問多少次，所有的孩子都會回答no。但是，爸爸宣布了一件本來大家都知道的事情之后，再開始提問，情況卻發(fā)生了改變，為什么？直觀上推測，爸爸宣布“至少有一個人的額頭上有泥巴”，一定還包含了另外的信息，這些信息使得每個小孩的knowledge的狀態(tài)發(fā)生了變化。</p> <p> </p> <p> 在本文中，作者將一個分布式系統(tǒng)的knowledge分成了幾類，這幾類根據(jù)它們之間的包含關(guān)系，構(gòu)成了一個層次。如下所述：</p> <p> 假設(shè)f是一個事實，如果節(jié)點i的知道f，我們就說節(jié)點i擁有關(guān)于f的knowledge，記做K[i](f) |= true，或者f 屬于集合K[i]。我們把一個分布式系統(tǒng)中的節(jié)點的集合記做G。</p> <p> D[G](f) |= true：系統(tǒng)G擁有關(guān)于f的Distributed Knowledge。如果存在一個系統(tǒng)G之外的實體，該實體知道G中每個節(jié)點的Knowledge，那么該實體知道f，此時，我們稱G擁有關(guān)于f的Distributed Knowledge。</p> <p> S[G](f) |= true：G中某個節(jié)點知道f。即S[G](f)等于K[i](f)的或。</p> <p> E[G](f) |= true：G中每個節(jié)點都知道f。即E[G](f)等于K[i](f)的與。</p> <p> E^k[G](f) |= true：G中每個節(jié)點都知道E^(k-1)[G](f) |= true。這個需要解釋下，假如說f是“昨天吃排骨了”，E[G](f) |= true表示G中每個節(jié)點都知道“昨天吃排骨了”，而E^2[G](f) |= true表示G中每個節(jié)點都知道 每個節(jié)點都知道“昨天吃排骨了”，依此類推。呵呵，類似與“我知道 你知道我知道”。</p> <p> C[G](f) |= true：當(dāng)且僅當(dāng)E[G](f) |= true 且 E^2[G](f) |= true且…且E^k[G](f) |= true 且…。這被稱為系統(tǒng)G的Common Knowledge。理論上講，Common Knowledge是一個系統(tǒng)G各個節(jié)點之間最強的一種agreement(唉，沒想好應(yīng)該選哪個中文詞來表達這個意思，大概是“關(guān)于xxx的意見高度統(tǒng)一”吧)。</p> <p> 有了這種knowledge的分層定義，我們再來看前面提到的那個問題。我們僅僅看k==2的情況，其它情況可以用數(shù)學(xué)歸納法證明。此時，我們假設(shè)所有小孩構(gòu)成的分布式系統(tǒng)是G，額頭有泥巴的小孩分別是a和b，f代表“至少有一個人的額頭上有泥巴”這個事實。在爸爸宣布f之前，有E[G](f) |= true，即每個孩子都知道f，但是，E^2[G](f) |= false，即，并不是每個人都知道每個人都知道f。比如，a就不知道b知道f，而第三個小孩c知道a不知道b知道f。而爸爸宣布f，使得E^2[G](f) |= true，即每個人都知道每個人都知道f，由于多了這些信息，或者說系統(tǒng)G關(guān)于f的knowledge的狀態(tài)變得更強了，導(dǎo)致了孩子可以在爸爸第二次問問題的時候判斷出自己的額頭上是否有泥巴。</p> <p> 對于一般的k，如果Ek[G](f) |= true，那么孩子們在父親第k次提問的時候就會判斷出自己的頭上是否有泥巴，否則，無法判斷。而父親宣布f這件事，其實使得C[G](f) |= true。</p> <p> </p> <p> 再來看一個問題：有一個山谷，兩邊的山上駐扎著紅軍，谷中駐扎的藍軍。如果山谷兩側(cè)的紅軍同時攻擊，就會取勝，而如果一側(cè)攻擊，而另一側(cè)沒有同時攻擊，就會讓藍軍突圍。兩側(cè)紅軍的將軍只有確認對方會和自己一起攻擊的情況下才會發(fā)起攻擊。兩側(cè)紅軍只能通過通訊員傳遞消息，通訊員可能在路上被藍軍殺死。問題是，是否可以設(shè)計一種協(xié)議，使得紅軍的兩個將軍可以達成一致并發(fā)起攻擊？</p> <p> 答案：不可能設(shè)計出這樣的協(xié)議。具體解釋也請參考網(wǎng)上眾多的文章。</p> <p> 現(xiàn)在我們來看為什么。假設(shè)一個理想情況，在紅軍相互傳遞消息的時候，運氣非常好，沒有一個通訊員被藍軍殺死。設(shè)兩側(cè)紅軍分別是a和b，a想“在明天12點發(fā)起進攻”，所以首先向b派出通訊員。我們用f表示“在明天12點發(fā)起攻擊”這個“事實”。當(dāng)?shù)谝粋�通訊員到達b時，E[G](f) |= true，但是E^2[G](f) |= false；a和b通過不斷地向?qū)Ψ脚沙鐾ㄓ崋T并接收對方的通訊員，對于任意一個有限k，可以做到E^k[G](f) |= true，但是，在有限的步驟中卻達不到C[G](f) |= true。而事實上，對于任何一個有限的k，E^k[G](f) |= true都不能使得a和b進行攻擊，只有C[G](f) |= true時，兩邊才會進行攻擊。證明的方式仍然是數(shù)學(xué)歸納法。</p> <p> </p> <p> 在文章中，作者證明了一個定理：在一個分布式系統(tǒng)G中（節(jié)點數(shù)>=2），如果通信不是可靠的，那么，不可能通過通信來達到對于某個事實f的C[G](f) |= true。換句話說，在這樣一個系統(tǒng)中，對于任何一個事實f而言，要么不需要任何通信，已經(jīng)是C[G](f) |= true了（例如，每個節(jié)點都知道每個節(jié)點的配置文件中都有一個“明天12點攻擊”）；否則，無論怎么通信，f也不可能變成C[G](f) |= true。</p> <p> 看到這個結(jié)論的時候，讓我又受了一次打擊。這豈不是說，在任何實際使用的分布式系統(tǒng)中，都無法通過通信的方式，使得C[G](f)由false變?yōu)閠rue嗎？現(xiàn)在的分布式系統(tǒng)中的節(jié)點是怎么通過協(xié)商確定配合完成某件事的？</p> <p> </p> <p> 題外話：什么時候總結(jié)下計算機科學(xué)家們讓我受的各種打擊，呵呵。一下子能想到的只有兩個：</p> <p> 本科時《可計算性理論》課上第一次明確知道世界上存在（還存在非常非常多）計算機不可判定的問題——“停機問題不可判定”的證明。這之前我一直認為計算機可以解決所有人腦可以解決的問題（包括制造與人一樣的機器人），只是我們還沒想出來好的算法或者計算機的性能還不夠。</p> <p> 研究生做編譯即編譯優(yōu)化時在程序分析課上知道了rice那哥們證明了“關(guān)于程序的任何非平凡屬性都是不可判定的”這個定理，而平凡屬性只剩下“所有程序都真，或者對所有程序都假的屬性”�？赐曜C明后的第一個想法是“這還怎么做編譯優(yōu)化？！”。</p> <p> </p> <p> 想想我們常見的那些分布式算法/協(xié)議，它們主要的困難點就在于協(xié)調(diào)系統(tǒng)中各個節(jié)點的行為，使得各個節(jié)點在某些方面達成一致。用作者的話說，這些協(xié)議做的很重要的兩件事就是“發(fā)現(xiàn)某個事實f”和“發(fā)布f，使的C[G](f) |= true”，只有系統(tǒng)中的各個節(jié)點擁有Common Knowledge，才能協(xié)調(diào)工作啊。</p> <p> 還好，實踐中的分布式系統(tǒng)并不是一定需要嚴格的Common Knowledge才能工作，就好象即使rice證明了rice定理，gcc仍然有上百中優(yōu)化一樣。實踐中使用的Common-Knowledge并不是理論上那么嚴格的，而是一些弱化的變體。在該文章中，作者舉了兩個例子，分別是e-Common Knowledge（‘e’代表epsilon）和eventually-Common Knowledge。</p> <p> </p> <p> 這篇文章提出的這個形式化的方法，可以用于從理論上證明分布式系統(tǒng)/協(xié)議的“可能”與“不可能”，同時，對這種想法有個了解后，對于我們自己去理解別的分布式系統(tǒng)，也有一定的幫助。</p> <p> </p> <p> 看了這篇文章，還想再嘮叨幾句。</p> <p> 我從小就很fan“科學(xué)”，現(xiàn)在一點也沒變。大學(xué)本科學(xué)計算機時，有一段時間非常郁悶，那時學(xué)到的都是些工程技術(shù)，完全不像數(shù)學(xué)、物理那樣。那時，我覺得跟別人說“我會計算機”和說“我會修自行車”一樣，這是一種純技術(shù)的活動。而我fan的人卻是那些提出并證明“自行車的輪子應(yīng)該是圓的”或“自行車可以保持平衡”的人。這種郁悶直到看了《自動機理論基礎(chǔ)》和《可計算性導(dǎo)引》之后。再之后，終于逐漸的感覺到了離散數(shù)學(xué)和計算機程序的聯(lián)系。也看了一些純理論的文章。我才相信，計算機是包含“科學(xué)”部分的。</p> <p> 比較遺憾的是，今天我從事的幾乎所有的工作，都只是工程技術(shù)。書店里計算機相關(guān)的書籍中，絕大部分都是在講各種各樣的技術(shù)；這大概是計算機界的規(guī)則吧。</p> |
|
免費注冊
發(fā)表于 2011-12-19 13:54