Lamport時鐘和狀態機

我正在閱讀Lamport關於時鐘和狀態機的文章，並且有一點我不明白。 Lamport指出：「一個進程可以在得知所有其他進程的時間戳小於或等於T時發出的所有命令時執行命令時間戳T.精確的算法非常簡單，我們不會費神去描述它「。Lamport時鐘和狀態機

該算法很簡單，但我實際上並沒有它......一個進程如何知道沒有更多的傳入消息的時間戳小於或等於要處理的消息的時間戳？

當接收到消息時，它可以通過廣播ACK的所有進程來解決...因此，由於消息是有序的，所以在接收到ACK時進程知道沒有具有較低時間戳的傳入消息...但是這看起來不像「簡單的算法」。

希望我很清楚。

來源

2014-10-29 mname

該進程知道沒有更多的命令，因爲/當它從每其他進程收到一個時間戳> = T的命令。

假設我們有從過程P2接收具有時間戳T2> = T的命令在接收到該命令的處理P1，過程P1立即獲悉的所有經其或同時之前發出P2的命令其命令時間戳爲T.

事實上，即使P1還沒有收到所有的中間命令（例如，P2可以爲發送的每個命令分配一個序號，P1也會注意到號）。然後，P1可以選擇等待丟失的命令，或者在傳輸過程中丟失命令時重新請求它們。

所以執行與T中的命令時間戳，過程P1必須等待，直到它接收到一個單個命令與時間戳> = T從每其他過程 - 那麼它可以等待（或重新請求）中的所有缺少中間命令並執行命令T.

來源

2015-04-24 06:18:22

好吧，我明白了！當你發現它時錯過了「每一個」。這意味着我們最終可能會有很多延遲，等待其他進程發送時間戳大於等於T的消息，或者進程之間進行大量通信以確認每條消息。非常感謝！ – mname 2015-07-09 18:53:46

Lamport時鐘和狀態機

回答

相關問題