分散式互斥（distributed mutual exclusion）

在單一機器上，當兩條執行緒不可同時碰同一份資料時，我們用一把鎖或一個號誌：誰先搶到誰先進，另一個等。這之所以行得通，是因為所有執行緒共用同一塊記憶體，所以鎖就是一個大家都看得到的物件。現在把這些參與者散到不同的、沒有共用記憶體的電腦上。沒有單一個鎖變數可以搶。分散式互斥就是要確保：在許多各自獨立的機器之間，任何一刻最多只有一台處於臨界區間（正在使用共享資源）——而且只能用訊息來達成。

既然沒有共用的鎖，這些行程就必須靠對話來協調。有幾種經典風格。權杖式（token-based）做法把一個特殊訊息（權杖）在群組裡傳來傳去；你只有在持有權杖時才可以進入臨界區間，由於權杖恰好只有一個，因此最多只有一個進入者。許可式（permission-based）做法（例如 Ricart-Agrawala 方案，它用邏輯時鐘的時間戳記來公平地打破平手）讓一個行程向所有其他行程請求許可，等到大家都同意後才進入。比較簡單但比較脆弱的做法，是用一個中央協調者像單一售票窗口那樣發放鎖。

為什麼重要，以及誠實的難處：每當各自獨立的機器共用某個「不可被兩台同時使用」的東西時，就需要分散式互斥——更新同一筆記錄、寫入同一個共享檔案、推選由誰來做某項工作。但它繼承了分散式運算的全部痛楚。訊息會花時間，所以它比本機鎖慢；訊息可能遺失，所以請求與釋放都可能失蹤；而一個行程可能在持有權杖或鎖時當掉、把所有人凍住，除非有復原機制。在容錯、公平、以及每次進入所需的訊息數目之間，存在真實的取捨。