邏輯時鐘，可以是計算機、數字電路、機械結構密碼機、CPU內部操作、音效卡、顯示卡和各種系統等等內部操作的時鐘，她的狀態於時間基準有固定或可改變的規則。
基本介紹
簡介,產生背景,定義,可行性,同步化,
簡介
邏輯時鐘也可以是人文科學上的套用，比如符合某些規則、條例作出決策，金融、股票分析等等。
產生背景
計算機系統時鐘的基本元素是石英振盪器，若干次振盪形成一次時鐘中斷，若干次（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）如果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元的向量<0k,1k,„1kn>。使得處理器Pi的狀態是指第ik個事件之後的狀態。對於任意的i和j，如果Pi上第Ki+1個計算事件不在Pj上第Kj個事件之前發生，那么這個向量就是一致的，稱為一致割。
