在集中式系統中，時間沒有歧義：行程想知道時間，發個系統呼叫，核心（kernel）就告訴它。若行程 A 先問、行程 B 後問，B 拿到的值一定不會比 A 低。但在分散式系統中，要對時間達成共識並不簡單。

以 UNIX 的 make 為例。大型程式拆成多個原始檔，改一個檔只需重編那一個檔。make 的判斷方式很單純：比較原始檔與目的檔的最後修改時間——若 input.c 的時間是 2151、input.o 是 2150，就知道 input.c 在 input.o 產生之後被改過，必須重編。

現在想像一個沒有全域時間共識的分散式系統：output.o 的時間是 2144，稍後 output.c 被修改，但因為它所在機器的時鐘稍慢，被標上 2143。make 因此不會呼叫編譯器，最後的執行檔混雜了新舊原始碼的目的檔——程式八成會當掉，而程式設計師會抓狂地找不出程式碼哪裡有錯。

需要準確時間的例子遠不止於此：檔案時間戳記、金融交易、安全稽核（security auditing）、協同感測（collaborative sensing）等領域都仰賴準確計時。於是同步研究的起點是一個簡單的問題：**分散式系統中的所有時鐘，有可能同步嗎？**答案出乎意料地複雜。

實體時鐘#

幾乎所有電腦都有計時電路。雖然大家慣稱它「時鐘（clock）」，其實叫計時器（timer）更貼切。它通常是一塊精密加工的石英晶體：在張力下以固定頻率振盪，頻率取決於晶體種類、切割方式與張力大小。每塊晶體配有兩個暫存器——計數器（counter）與保持暫存器（holding register）——晶體每振盪一次，計數器減一；歸零時產生一次中斷，並從保持暫存器重新載入計數器。如此可讓計時器以每秒 60 次或任意頻率產生中斷，每次中斷稱為一個時鐘滴答（clock tick）。

系統開機時把日期時間換算成自某個起始日以來的滴答數存入記憶體（多數電腦有電池供電的 CMOS RAM，之後開機不必重新輸入）；每次滴答，中斷服務程序把記憶體中的時間加一，(軟體) 時鐘就這樣維持著。

• 單一電腦、單一時鐘時，時鐘偏差一點無妨：所有行程用同一個時鐘，內部仍是一致的，重要的只有相對時間。
• 一旦有多顆 CPU、各有各的時鐘，情況徹底改變：晶體振盪頻率雖然相當穩定，卻不可能保證不同電腦的晶體頻率完全相同。n 台電腦的 n 塊晶體會以略為不同的速率運行，使各軟體時鐘逐漸失去同步、讀出不同的值。這種時間值的差異稱為時鐘偏斜（clock skew）。

在某些系統（如即時系統）中，實際的時鐘時間很重要，這時需要外部實體時鐘。基於效率與冗餘考量，通常會配置多個實體時鐘，於是產生兩個問題：(1) 如何讓它們與真實世界的時鐘同步？(2) 如何讓這些時鐘彼此同步？

時間是怎麼量出來的#

自 17 世紀機械鐘發明以來，時間一直以天文方式量測。太陽到達天空最高視位置的事件稱為太陽中天（transit of the sun），兩次中天之間的間隔是太陽日（solar day）；一天 24 小時、每小時 3600 秒，**太陽秒（solar second）**便定義為太陽日的 1/86400。

1940 年代，人們確認地球自轉週期並不固定：潮汐摩擦與大氣阻力使地球自轉變慢。除了長期趨勢，日長還有短期變動（可能源自地核熔融鐵的擾動）。天文學家因此改為量測大量天數取平均再除以 86,400，得到平太陽秒（mean solar second）。

1948 年原子鐘問世後，計時可以不受地球晃動影響：物理學家接手計時工作，把秒定義為銫 133（cesium 133）原子完成 9,192,631,770 次躍遷所需的時間——這個數字的選擇，是為了讓原子秒等於引入當年的平太陽秒。世界各地多個實驗室設有銫 133 時鐘，定期向巴黎的國際時間局（Bureau International de l’Heure, BIH）回報滴答數，BIH 取平均後產生國際原子時（International Atomic Time, TAI）：即自 1958 年 1 月 1 日午夜以來銫鐘平均滴答數除以 9,192,631,770。

TAI 雖然高度穩定，卻有個嚴重問題：86,400 個 TAI 秒如今比一個平太陽日短了約 3 毫秒（因為平太陽日不斷變長）。若直接用 TAI 計時，正午會年復一年地提早，最終出現在凌晨。BIH 的解法是：每當 TAI 與太陽時的差距累積到 800 毫秒，就插入一個閏秒（leap second）。由此得到以恆定 TAI 秒為基礎、又與太陽視運動保持同相的時間系統——世界協調時間（Universal Coordinated Time, UTC）。UTC 是所有現代民用計時的基礎，實質上取代了舊標準格林威治標準時間（Greenwich Mean Time，天文時間）。至今引入 UTC 的閏秒總數約 30 個。

全球定位系統#

作為進入時鐘同步問題的踏板，先看一個相關問題：如何在地球上任何地方確定自己的地理位置。這個定位問題由一個高度專門的分散式系統解決——全球定位系統（Global Positioning System, GPS），1978 年發射啟用的衛星式分散式系統。它原本主要用於軍事，近年大量進入民用領域，尤以交通導航為著；GPS 手機讓通話者互相追蹤位置，同樣的原理也能追蹤寵物、小孩、汽車、船隻等。

GPS 使用 29 顆衛星，軌道高度約 20,000 公里。每顆衛星有多達四個原子鐘，定期由地面特殊站台校準。衛星持續廣播自己的位置，並為每則訊息蓋上本地時間戳記。原則上，只要三顆衛星就能讓地面接收器算出自己的位置。

先假設所有時鐘（包括接收器的）都同步。考慮二維情形：兩顆衛星各自定義一個「與該衛星等距」的圓，忽略最高處的交點後，兩圓交點即為唯一位置。這個「圓相交」原理推廣到三維，就需要三顆衛星來確定經度、緯度與高度。

但現實中有兩件事讓問題複雜化：

1. 衛星的位置資料要花時間才能到達接收器。
2. 接收器的時鐘通常與衛星不同步。

假設衛星的時間戳記完全準確，令 Δr 為接收器時鐘相對真實時間的偏差。收到衛星 i 帶時間戳記 Ti 的訊息時，接收器量到的延遲 Δi 包含兩部分：實際延遲，加上自己的時鐘偏差。訊號以光速 c 行進，量測距離即 c·Δi；令 di 為接收器與衛星的真實距離，則量測距離可改寫為 di + c·Δr，而真實距離由衛星座標 (xi, yi, zi) 與接收器座標的幾何距離算出。

於是若有四顆衛星，就得到四條方程式、四個未知數，可同時解出接收器座標 (xr, yr, zr) 以及時鐘偏差 Δr。換句話說，GPS 量測同時給出位置與實際時間。本章稍後討論節點定位時會回到類似的做法。

以上假設量測完全準確，實際上並非如此。GPS 不計入閏秒，與 UTC 存在系統性偏差（至 2006 年 1 月 1 日為 14 秒）——這在軟體中容易補償；但誤差來源還很多：衛星上的原子鐘並非隨時完美同步、衛星位置無法精確得知、接收器時鐘精度有限、訊號傳播速度不恆定（進入電離層等介質會變慢），加上地球不是完美球體，還需進一步修正。

總之，計算精確位置絕非小事，牽涉大量細節。即便如此，相對便宜的 GPS 接收器已可達 1–5 公尺的定位精度；專業接收器（可輕易接上電腦網路）宣稱誤差小於 20–35 奈秒。入門細節可參考 Zogg (2002) 的優秀綜述。

時鐘同步演算法#

若有一台機器配備 WWV 接收器，目標就是讓其他機器都與它同步；若沒有任何機器有 WWV 接收器，則各機器自行計時，目標是讓所有機器盡量彼此一致。相關演算法很多（綜述見 Ramanathan et al., 1990），但底層模型相同：

• 每台機器有一個每秒中斷 H 次的計時器，中斷處理常式為軟體時鐘加一。令 UTC 時間為 t 時，機器 p 的時鐘值為 Cp(t)。完美世界裡對所有 p、t 都有 Cp(t) = t，亦即 dC/dt 理想上為 1。
• dC/dt 稱為時鐘在時刻 t 的頻率（frequency）；頻率減 1 為偏斜（skew）；Cp(t) − t 為相對時刻 t 的偏移（offset）。
• 真實計時器不會精準地每秒中斷 H 次：H = 60 理論上每小時 216,000 滴答，現代計時晶片的相對誤差約 10⁻⁵，實際落在 215,998 到 216,002 之間。若存在常數 ρ 使得 1 − ρ ≤ dC/dt ≤ 1 + ρ，計時器就算符合規格；製造商給定的 ρ 稱為最大漂移率（maximum drift rate）。

若兩個時鐘朝相反方向漂離 UTC，同步後經過時間 Δt，兩者最多相差 2ρΔt。因此若要保證任兩時鐘的差距不超過 δ，就必須至少每 δ/2ρ 秒（以軟體）重新同步一次。各演算法的差別就在於如何進行這個重新同步。

網路時間協定（NTP）#

許多協定採用 Cristian (1989) 最早提出的做法：讓用戶端連向時間伺服器（time server）——伺服器因配備 WWV 接收器或精確時鐘而能提供準確時間。問題在於訊息延遲會讓回報的時間過時，訣竅是好好估計這些延遲：

• A 送出請求給 B，蓋上時間戳記 T1；B 記錄收到時刻 T2（取自 B 的本地時鐘），回覆時蓋上 T3 並附帶先前記下的 T2；A 記錄回覆到達時刻 T4。
• 假設 A→B 與 B→A 的傳播延遲大致相同（T2 − T1 ≈ T4 − T3），A 即可估出自己相對 B 的偏移 θ = ((T2 − T1) + (T3 − T4)) / 2。

時間不允許倒流。若 A 的時鐘偏快（θ < 0），原則上該把時鐘往回撥——但這不被允許：時鐘回撥後才編譯出的目的檔，時間可能早於回撥前才修改的原始檔，造成嚴重問題。修正必須漸進引入：例如計時器每秒中斷 100 次、每次本應加 10 毫秒，要調慢時每次只加 9 毫秒直到修正完成；要調快則每次加 11 毫秒，而不是一次跳過去。

網路時間協定（Network Time Protocol, NTP）把這個程序設定成伺服器成對進行：B 也會反過來探測 A 的時間。除了偏移 θ，同時估計延遲 δ；緩衝八組 (θ, δ) 值，取其中 δ 最小者作為兩伺服器間延遲的最佳估計，並以其對應的 θ 作為最可靠的偏移估計。

對稱地套用 NTP，原則上 B 也會向 A 調整時鐘——但若已知 B 的時鐘更準，這樣調就蠢了。NTP 用**階層（stratum）**解決：

• 配備參考時鐘（WWV 接收器或原子鐘）的伺服器是 stratum-1 伺服器（時鐘本身視為 stratum 0）。
• A 連向 B 時，只有當自己的 stratum 值比 B 高才調整時間；同步後 A 的 stratum 變成 B 的加一。也就是說，若 B 是 stratum-k 伺服器，A 原本的 stratum 高於 k，同步後就成為 stratum-(k+1)。由於 NTP 的對稱性，若 A 的 stratum 較低，則換 B 向 A 調整。

NTP 還有許多重要特性，多與錯誤辨識與遮蔽、以及安全攻擊相關。NTP 見 Mills (1992)，已知可達到全球範圍 1–50 毫秒的精度；最新版 NTPv4 的詳細描述可見 Mills (2006)。

柏克萊演算法#

在 NTP 等許多演算法中，時間伺服器是被動的：只回答別人的查詢。Berkeley UNIX 採取完全相反的做法（Gusella and Zatti, 1989）：時間伺服器（其實是時間常駐程式，time daemon）主動輪詢每台機器問現在幾點，根據回答計算平均時間，然後告訴所有機器把時鐘調快到新時間，或調慢直到達成指定的減量。

流程是：時間常駐程式把自己的時間告訴其他機器並詢問它們的時間；各機器回報自己比它快或慢多少；常駐程式算出平均後，告訴每台機器該如何調整。

這個方法適合沒有任何機器配備 WWV 接收器的系統，時間常駐程式的時間須由操作員定期手動設定。值得注意的是：對許多用途而言，所有機器彼此一致就夠了，不必與電台播報的真實時間一致——即使常駐程式的時鐘從未被校準，只要沒有節點與外部電腦通訊，大家開心地同意一個與現實無關的「現在時間」也無妨。

無線網路中的時鐘同步#

傳統分散式系統的優勢是能輕易有效地部署時間伺服器，且多數機器能彼此聯絡、資訊散播相對簡單。這些假設在許多無線網路（尤其是感測網路）中不再成立：節點資源受限、多跳（multihop）繞送昂貴，且演算法常需為能耗最佳化。這些觀察催生了截然不同的無線時鐘同步演算法。以下看一個具體解法；其他解法的簡要綜述見 Sivrikaya and Yener (2004)，詳盡調查見 Sundararaman et al. (2005)。

參考廣播同步（Reference Broadcast Synchronization, RBS）（Elson et al., 2002）與其他提案有兩點根本不同：

1. 不假設有任何節點掌握準確的實際時間。它不求提供 UTC，只求讓時鐘內部同步，跟柏克萊演算法一樣。
2. 先前的解法都是讓傳送者與接收者同步（雙向協定）；RBS 只讓接收者們彼此同步，把傳送者排除在外。

RBS 中，傳送者廣播一則參考訊息（reference message）讓接收者調整時鐘。關鍵觀察是：在感測網路中（不考慮多跳繞送時），訊號從離開傳送者網路介面那一刻起的傳播時間大致恆定。於是估計延遲時，兩大變異來源不再有影響：建構訊息的時間、以及存取網路的時間。

相較之下，NTP 這類協定在訊息交給網路介面之前就蓋時間戳記；而無線網路採競爭式協定，訊息要等多久才能真正送出並無定數。RBS 消除了這些不確定因素，剩下的只有接收端的遞送時間，其變異遠小於網路存取時間。

RBS 的想法很簡單：節點廣播參考訊息 m 時，每個節點 p 記下自己收到 m 的時刻 Tp,m（讀自 p 的本地時鐘）。忽略時鐘偏斜，兩個節點 p、q 交換彼此的收訊時刻，就能估計相互的相對偏移：把 M 則參考訊息的 (Tp,k − Tq,k) 取平均。重要的是，節點 p 因此知道 q 的時鐘相對自己的值——而且只要存下這些偏移即可，不必調整自己的時鐘，省下能量。

不幸的是時鐘會漂移，直接取平均會失效：越晚送出的值越不準，而且偏移大概會隨時間增大。Elson 等人用很簡單的方法補償：不取平均，改用標準**線性迴歸（linear regression）**把偏移表示成時間的函數 αt + β，常數 α 與 β 由資料點 (Tp,k, Tq,k) 算出。如此節點 p 就能更準確地換算出 q 當下的時鐘值，反之亦然。