邏輯時鐘

狀態於時間基準有固定或可改變的規則，例如各種跳頻通訊，加密、解密通訊，解碼、編碼方式，VCD、DVD的圖像處理，電視台的圖像同步信號，3G通訊格式，聲音、圖像的編碼傳輸都有複雜的邏輯時鐘關係。

邏輯時鐘也可以是人文科學上的應用，比如符合某些規則、條例作出決策，金融、股票分析等等。

計算機系統時鐘的基本元素是石英振盪器，若干次振盪形成一次時鐘中斷，若干次（H）中斷構成時鐘值的一次遞增。設系統時鐘為C，UTC時間為t。由於時鐘芯片存在誤差，如果H=60，則每小時時鐘應當振盪60×3600=216000次，但實際的震盪次數大約在215998－216002之間。因此存在一個常量ρ（由芯片製造廠商提供，稱為最大漂移率），有1 -ρ≤dC/dt≤1 + ρ。如果兩個時鐘反向漂移（最壞情況），而系統要求它們之間的時鐘誤差是δ，則它們必須在每δ/2ρ秒之內進行一次重新同步。這就產生了邏輯時鐘的概念。

1 一般定義

邏輯時鐘，可以是計算機、數字電路、機械結構密碼機、CPU內部操作、顯卡和各種系統等等內部操作的時鐘，她的狀態於時間基準有固定或可改變的規則。例如各種跳頻通訊，加密、解密通訊，解碼、編碼方式，VCD、DVD的圖像處理，電視台的圖像同步信號，3G通訊格式，聲音、圖像的編碼傳輸都有複雜的邏輯時鐘關係。

2 分佈式系統中的定義

邏輯時鐘是（松耦合）分佈式系統的特性，要求的是系統節點進展之間的相對一致性（同步）。 只有相關的系統（進程）才需要有邏輯時鐘同步，同步的目的是維持事件的順序性。除時間的基本特性（一維）外，邏輯時鐘與標準時鍾（物理時鐘）之間沒有通用意義上的明確的關係。

邏輯時鐘同步的算法是有意義並且可行的，只要有以下三方面的理由：

（1）如果兩個進程之間不存在相互作用，它們的同步沒有意義；

（2）時鐘同步不需要絕對同步，不需要所有進程在時間上完全一致，而是它們在事件的發生順序要完全一致；

（3）邏輯時鐘只關心事件的發生順序，而不關心是否與物理時間接近。

算法涉及到的概念

（1）時標：邏輯時鐘通常用時標(timestamp)表示，稱為Lamport時標，沒有具有物理意義的單位的概念，一般情況下以正整數標識；

特點：時標只能通過節點之間進行消息交換完成；時標完全沒有物理時鐘方面的要求。

（2）事件：進程中相對獨立的一段程序（代碼，語句序列）的一次運行，具有不可分割性和相對獨立的語義。

特點：是併發與同步分析的基本單位（不可分割）；事件之間不存在包含關係；含有發送或接收動作的事件是系統的同步點。

（3）事件間的關係：一個沒有死鎖的特定系統，在確定了併發進程和各進程的事件後，任何2個事件間要麼是“先於發生（→）”關係，要麼是“併發（||）”關係。具有併發關係的事件可以併發完成，也可以先後完成，沒有順序要求，具有發生在先關係的事件必須按該關係所規定順序先後完成。

發生在先關係的定義為：

（1）如果a和b是同一個進程中的事件且a在b之前被執行，則a→b；

（2）如果a是某個進程發送消息的事件，b是另一個進程接收該消息的事件，則a→b；

（3）如果a→b且b→c，則a→c；

（4）a→a對於任何事件a都不成立。如果事件a和b之間不存在發生在先關係，則它們是併發的。

事件發生在先關係要求：

（1）單個進程執行中所有的事件是全（偏）序的；

（2）相對的要求，可以通過調節事件的分割來滿足

（3）當消息接收方發現自己的（邏輯）時鐘小於收到的消息的時標時，要將自己的時鐘調整到比收到的時標至少大1的值，以維持偏序關係的成立。

1. Lamport標量邏輯時鐘

沒有一個直接的全局的邏輯時鐘，但每個進程Pi維護一個當前邏輯時鐘LCi，它是一個非減的整數序列且初始化為init (≥0)。進程中的每個事件均有一個邏輯時鐘，其數值等於發生時刻所屬進程的邏輯時鐘的取值；Pi發出的每個消息m都帶有本地邏輯時鐘，可表示為(m,LCi, i)。通過這些邏輯時鐘和消息，可以維護事件間的先於發生關係。附加條件：兩個事件不可以同時發生。LCi的更新原則為：

（1）在發生一個（外部發送或內部）事件之前更新LCi=LCi+ d；

（2）當收到一個帶時戳的消息(m, LCj, j)時，Pi執行更新LCi=max（LCi,LCj）+ d （d＞0）。

2. 向量時鐘

對標量邏輯時鐘算法的改進是向量時鐘算法。在一個由n個併發進程構成的系統中，每個事件的邏輯時鐘均由一個n維向量（n元組）構成，其中第i維（分量）對應於第i個進程的邏輯時鐘Vi。第i個進程在事件發生時，繼承上一事件的邏輯時鐘並將自身所對應的分量Vi增加一個步長，任何進程Pi在發出任何信息時都要將自己當前的邏輯時鐘分量Vi起發送出去，如果是接收事件，且發送方為j，則比較自己繼承的Vj和收到的邏輯時鐘，並取其中較大者為自己的Vj。這樣，每次消息都能使接收方更新對系統每個進程的時鐘認識。

3. 一致割

一致割是指處理器可以併發保留的狀態，在一個分佈式系統中，基本上沒有可以記錄系統狀態瞬時快照的觀察者。可是，這樣一種能力在解決譬如系統崩潰後的恢復、檢測系統中是否存在死鎖及檢測計算是否已經終止時是需要的。可以取代的方法是系統自身通過協作來獲取近似的瞬時信息快照。分佈式系統裏的一個割是一個n元的向量。使得處理器Pi的狀態是指第ik個事件之後的狀態。對於任意的i和j，如果Pi上第Ki+1個計算事件不在Pj上第Kj個事件之前發生，那麼這個向量就是一致的，稱為一致割。