前幾章談的是行程（process）與行程間的通訊。然而通訊只是故事的一半——與其密切相關的，是行程之間如何合作與同步（synchronization）。命名機制讓行程至少能共享資源，但合作還需要更多：例如多個行程不能同時存取印表機這類共享資源，必須協調出暫時的獨占存取權；又例如多個行程有時得對事件的先後順序達成共識——行程 P 送出的訊息 m1，究竟是在行程 Q 送出 m2 之前還是之後？

分散式系統中的同步，往往比單處理器或多處理器系統中的同步困難得多。本章討論的問題與解法本質上相當通用，會在分散式系統的許多不同情境中反覆出現。

本章的鋪陳如下：

• 先討論以實際時間為基礎的同步（時鐘同步），再轉向只在乎相對順序、不在乎絕對時間的同步（邏輯時鐘）。
• 接著討論分散式互斥（mutual exclusion）：如何保證同一時間至多一個行程存取共享資源。
• 順著時間量測的思路，介紹節點的全域定位：為節點指定幾何空間中的位置，讓節點間距離反映實際延遲。
• 最後討論選舉演算法（election algorithms）：一群行程如何推舉出一個協調者（coordinator）。

分散式演算法種類繁多，為各式系統而設計。更多範例可見 Andrews (2000) 與 Guerraoui and Rodrigues (2006)；較形式化的處理可參考 Attiya and Welch (2004)、Lynch (1996) 與 Tel (2000) 的教科書。

本章重點#

• 分散式系統沒有全域共享時鐘：各機器對「現在幾點」各有各的看法。時鐘同步演算法都建立在交換時鐘值、並估計訊息傳遞延遲之上；對延遲變異的處理方式，大致決定了同步的精度。
• 節點的幾何定位與時鐘同步問題相通：為每個節點指定 m 維空間座標，使幾何距離能準確反映節點間延遲，做法與 GPS 定位定時如出一轍。
• 很多情況下不需要絕對時間，只需要相關事件以正確順序發生。藍波特（Leslie Lamport）證明可以透過邏輯時鐘讓所有行程對事件順序達成全域共識：每個事件 e 得到全域唯一的邏輯時間戳記 C(e)，若 a 先於 b 發生，則 C(a) < C(b)；向量時間戳記（vector timestamps）進一步做到「若 C(a) < C(b)，則 a 因果先於 b」。
• 分散式互斥演算法保證一群行程中同一時間至多一個能存取共享資源。用一個協調者記錄輪到誰，最容易達成；全分散式演算法也存在，但缺點是通常對通訊與行程故障更敏感。
• 行程間的同步常需要某個行程擔任協調者。協調者不固定時，由選舉演算法決定誰來當；選舉主要用於協調者可能當機的場合，也可用於 P2P 系統中挑選超級節點（superpeer）。