併行歷史的不完全記錄
2013
作者 Lamport, Leslie Barry
我們非常榮幸能在 POTSI 2014 邀請到 Leslie 的圖靈獎演講。這裡有他兩個版本的簡介。我會讀出其中兩個版本，而你們將選擇哪一個是 Leslie 自己寫的。所以這是第一個版本。Lamport 博士擁有 Brandeis University 數學博士學位，其博士論文關於解析偏微分方程中的奇異點。這加上他完全沒有電腦科學方面的教育，為他在 Massachusetts Computer Associates、SRI、Digital 和 Compact 擔任電腦科學家做好準備。他聲稱這並非他的錯，在這四家公司中，只有原本應該是非營利的那家仍然存在。所以其餘的都已不復存在。他於 2001 年加入 Microsoft，而我不會在剛才那句話之後說出任何預測。因此，Lamport 博士在併行演算法方面的早期研究使他以 Lattice 的作者身份聞名，這是一個文件格式化系統，適用於那些寫公式而非畫圖的日益減少的人群。他也因寫下「分散式系統就是一個你甚至不知道它存在的電腦故障，就能讓你的電腦無法使用」而聞名，這確立了他作為分散式系統專家的地位。他對地中海歷史的興趣，包括對拜占庭將軍和神祕的希臘島嶼 Paxos 的研究，使他獲得了五個歐洲大學的榮譽博士學位，並讓 IEEE 送他去義大利領取其 2004 年 Prior Award，以及去魁北克領取其 2008 年 Von Neumann Medal。然而，他總是回到他在加州的家。這種愛國行為使他獲得了 National Academy of Engineering 和 National Academy of Science 的會員資格。最近，Lamport 博士通過主張在實作演算法或系統之前先理解它來惹惱電腦科學家和工程師，並通過說他們應該使用數學來嚇唬他們。為了讓他談論其他事情，ACM 授予了他 2013 年 Turing Award。謝謝。現在是官方版本，所以你們明白是誰寫了第一個版本，對嗎？官方版本是這樣說的。晚安。我很榮幸歡迎各位參加 ACM Turing Lecture。這個年度演講由 ACM Turing Award 的獲獎者發表，該獎項以英國數學家 Alan Turing 的名字命名。此榮譽常被稱為計算領域的諾貝爾獎。這是電腦科學家所能獲得的最負盛名的電腦科學獎項，並附帶 250,000 美元的獎金，由 Intel 和 Google 慷慨資助。該獎項的獲獎者可以選擇其演講的會議地點。今年，獲獎者 Leslie Lamport 選擇了 ACM Symposium on Principles of Distributed Computing。許多分散式併行系統理論與實踐中固有的核心概念，都源於 Leslie Lamport 的研究。他在 SRI International、Digital 以及現在在 Microsoft Research 擔任首席研究員期間的研究，以及作為近 150 本書籍和出版物的作者或合著者，他創造了一系列對於分散式計算應用至關重要的著作。他幫助發明了拜占庭故障的概念，並開發了儘管存在此類故障仍能達成一致的演算法。他幫助提出了併行系統的證明方法。他設計了重要的分散式演算法、形式化建模和驗證方法，以及用於提高實際分散式系統品質的工具。他所有的貢獻都有一個共同主題，即在分散式處理器集合的明顯混亂中，施加清晰、明確的順序。因此，研究人員可以設計更有效的分散式演算法，程式設計師可以編寫更有效的分散式程式。如果沒有 Leslie Lamport，分散式計算系統將無法完成其設計目的的工作。請大家歡迎 Leslie 上台演講。謝謝。謝謝。我會指出，官方 ACM 獎項讚揚我發明了因果關係的概念，所以請記住在我之前世界是多麼混亂。
併行歷史的不完全記錄
這是從 2014 年視角的歷史，這是對歷史非常個人的觀點。我真的應該稱其為回憶錄而不是歷史，我希望這可以免除我所有的遺漏。當然，這是用 40 年後的觀點來解釋的。從名稱開始，這個領域曾被稱為許多不同的名稱，而今晚，今天，我將簡單地稱其為併行（concurrency），以涵蓋所有這些不同的名稱。
開端：Dijkstra 與互斥
好的，一開始，有了 Dijkstra。他於 1965 年發表的論文《併行控制中一個問題的解決方案》（Solution of a Problem in Concurrent Control）。這是一篇絕對出色的論文，開創了這個領域。它引入了互斥問題。正如你們大多數人所知，在那個問題中，N 個處理器可以各自重複執行其程式碼的一部分，稱為臨界區段（critical section）。而問題在於它們必須僅僅通過讀取和寫入共享記憶體來同步自己，以確保：首先，互斥性成立，這意味著沒有兩個處理器同時執行它們的臨界區段；其次，滿足我們現在稱為無死結（live lock freedom）的屬性，即如果有處理器試圖執行其臨界區段，那麼某個處理器最終將執行其臨界區段。不一定是同一個處理器，但如果有人想執行他們的臨界區段，那麼就會有人成功。並且，任何電腦都可以在其同步點之外停止，當它不再對其臨界區段感興趣，不想再執行時，它被允許停止。這最後一個條件實際上是一個關鍵要求，排除了一些非常簡單但不有趣的解決方案。
當時，Dijkstra 沒有做出任何即時假設。唯一的假設是每個沒有停止的處理器，每個沒有停止的處理器，都會繼續採取步驟。它最終會採取一個步驟，然後最終會採取另一個步驟，依此類推。而在 Dijkstra 的應用中，他無法假設任何更強的條件，因為在那個時代，多處理意味著單個電腦處理器被多個處理器共享。因此，你無法假設任何即時行為，也無法假設一個處理器一定會在合理的時間內採取一個步驟，因為當其他處理器正在執行時，其他處理器就只是坐在那裡什麼也不做。
為了節省時間，我將主要忽略公平性（fairness）和活絡性（liveness），而只考慮安全性（safety）。
進入故事：Bakery 演算法
所以，我在 1972 年相當不起眼地進入了這個故事，當時我瞭解了這個問題並閱讀了 Dijkstra 的論文，我對自己說，實際上，那不是 Dijkstra 的論文，是 72 年發表的另一篇互斥演算法，我對自己說，哦，這是一個相當容易解決的問題。於是我迅速寫出了一個漂亮、簡單的演算法，並提交給 CACM (Communications of the ACM)。幾週後，我收到了編輯的一封信，解釋了為什麼我的解決方案是錯誤的。嗯，我從中學到了兩件事，或者說它對我產生了兩個影響。首先，它讓我生氣了，我決定我真的必須解決那個問題。其次，同樣重要的是，它教會了我對併行演算法進行嚴謹證明（rigorous proofs）的必要性。我應該提一下，Dijkstra 寫出了第一個互斥演算法。發表的第二個互斥演算法是錯誤的。它也是在 CACM 上發表的。
好的，所以它對我的第一個影響是我發明或發現的 Bakery 演算法。基本思想是，一個想執行其臨界區段的處理器只需拿取一個編號的票券。這是一種你可能在熟食店或類似地方見過的流程，當顧客進來時，有一台機器發放票券，人們在進入時拿取票券，並按票券號碼依序服務。問題是，當時沒有票券號碼，沒有票券製造商，因為那將是一個不允許停止的處理器。所以處理器必須自己製作編號的票券。一個處理器製作自己的編號票券的方法是讀取所有其他已經製作票券的處理器的號碼，然後製作一個比它讀取到的所有號碼中最大的號碼還要大一號的票券。這個簡單的解決方案有幾個問題。它需要一些改進，但這就是基本思想。它非常簡單。
現在，那個解決方案有一個問題，那就是票券號碼會無限增長。這不是一個實際問題，因為即使在那個時代，記憶體也不是那麼昂貴，而且如果處理器每奈秒執行一次臨界區段，那麼在不多的臨界區段執行次數內太陽就會爆炸，所以你不會需要一個太大的號碼來使這成為一個實際的解決方案。然而，它可能需要將票券儲存在多個記憶體字中，因為在那個時代，我不知道，最大的記憶體可能是 36 位元，我認為這無法達到 10 的 27 次方。所以你有多個記憶體字，而一台電腦，一個處理器，只能以單一動作原子地讀取或寫入單個記憶體字。所以，但是當我寫證明時，我意識到這個演算法一個非常顯著的特性，那就是讀取或寫入整個號碼不需要是原子的。如果當沒有併發寫入時，讀取能獲得正確的值，那麼這個演算法就是正確的。也就是說，如果一個處理器已經寫入了 472，這個號碼已經被寫入，而且沒有其他人在寫入，而且它也不再寫入它，那麼任何其他來讀取的人都會得到 472。但一個與寫入重疊的讀取
可能會得到任何可能的值。如果一個處理器正在寫入 472 時有人讀取，另一個處理器可能會得到 427、3493、0，任何值都沒關係。演算法仍然是正確的。這意味著演算法在不假設任何更低層級互斥的情況下實現了互斥，因為對一個暫存器進行原子存取以實現原子讀取或寫入意味著沒有兩個處理器同時讀取和寫入那個號碼的互斥性，這需要某種形式的互斥來保證。所以這是一個不需要任何底層互斥的真正的互斥演算法。
現在，在 1973 年，這被認為是不可能的，Brink Hansen 的一篇論文宣稱為了解決互斥問題，你需要更低層級的互斥。我幾年後出現並證明了相反的情況。但即使在 1990 年，專家們仍然認為這是不可能的。CACM 上發表了一份自我評估考試，其中一個問題的正確答案是，你需要底層互斥來解決互斥問題。
剩下一個問題。如何將票券號碼限制在臨界區段執行次數的範圍內？換句話說，如果每次一個新處理器試圖進入其臨界區段時，另一個處理器試圖進入其臨界區段，它的號碼不能大於試圖執行其臨界區段的總人數或臨界區段執行次數加一，那麼這是可行的。但是，如果讀取與寫入同時發生可能獲得任何值，你如何實現這一點？換句話說，如果當你寫入 472 時，我能得到 472 或更大的值，那沒關係，但是如果我得到 4,072,000 怎麼辦？那麼顯然，隨著併發的讀取和寫入，號碼可能會任意快速地增長，事情就行不通了。
這是一個相關的問題。它本質上是同一個問題。你如何實現一個時鐘，它能計數自大爆炸以來的奈秒數？所以它有很多數字要計數。其中讀取和寫入都是原子的，只能原子地讀取和寫入記憶體的個別字，而且時鐘值必須佔用多個字。並且正確性條件是讀取必須返回在讀取時鐘期間某個正確的時間。所以如果我在凌晨 1 點到 2 點之間讀取時鐘，我應該能得到 1 點 30 分或 1 點 45 分，但不是 5 點 20 分或類似的時間。所以這是正確性條件。有一個更難的問題。這是同一個問題，但是這個時鐘不是永遠計數，而是循環運行。好吧，我把這留給你們作為一個問題。你們可以查閱我的出版物頁面找到答案。這是一個非常好的問題。
嚴謹證明和模型的需求
我的併行程式設計入門經歷產生的第二個影響是需要嚴謹的證明。現在，證明意味著數學推理。對演算法進行數學推理需要演算法的數學模型。現在，如果你細讀或仔細思考 Dijkstra 的論文，其隱含的模型是，一個執行被表示為一系列狀態。這是計算中最普遍有用的模型。例如，Turing machine 的執行就是一系列狀態，其中狀態包括膠帶上寫的內容、膠帶的位置以及記憶體的內容。我稱之為標準模型。
標準模型假設原子動作。但是假設原子動作對於一個具有非原子讀寫操作的演算法來說並不是一個非常自然的模型。特別是，如果我已經假設了原子讀寫，那就不會引導我發現 Bakery 演算法確實實現了互斥。
所以我設計了所謂的 Two-Arrow 模型。但在我深入介紹之前，先離題一下，一個難題。處理器間通訊，即同步的基本問題，要求確保某個處理器 P 執行的操作發生在另一個處理器 Q 執行的操作之前。其中一個例子是互斥，它說必須確保如果一個處理器 P 執行其臨界區段，要麼發生在 Q 執行臨界區段之前，要麼反之。所以處理器間通訊的正確性。基本問題是確保一個處理器的動作發生在另一個處理器的動作之前。
現在，一些現代多處理器提供了記憶體屏障（memory barrier）指令來實現處理器間通訊，處理器間同步。記憶體屏障的執行是這樣工作的，如果一個處理器執行指令 A，然後執行一個記憶體屏障，然後執行指令 B，所有這些都在同一個處理器中，那麼這保證了 A 發生在 B 之前。但請注意，記憶體屏障提供的是關於在單個處理器內操作執行順序的條件。而處理器間同步要求排序兩個不同處理器中操作的執行。那麼，一個提供了單個處理器內同步的記憶體屏障指令，如何幫助實現處理器之間的同步呢？請思考一下這個有趣的難題。
Two-Arrow 模型
好的，讓我回到 Two-Arrow 模型。一個執行被表示為一組操作執行，以及兩個關係：實線箭頭（solid arrow）和虛線箭頭（dashed arrow）。它們的語義如下。你將一個操作視為在有限時間內發生的事情。在這張圖中，我們有三個處理器，時間是朝這個方向流動的，所以這個操作 A1 的執行從這裡開始，在這裡停止。X 實線箭頭 Y 意味著 X 在 Y 開始之前結束。例如，A1 實線箭頭 B2，因為 A1 的結束發生在 B 的開始之前，抱歉，發生在 C2 的開始之前，因為它發生在 C2 的開始之前。X 虛線箭頭 Y 意味著 X 在 Y 結束之前開始。所以例如，A1 虛線箭頭 B1，因為 A1 的開始發生在 B1 的結束之前。同樣地，A1 虛線箭頭 C1，A1 虛線箭頭 B2，你實際上可以看到 A1 實線箭頭 B2，而且一般來說，實線箭頭蘊含虛線箭頭。
所以這些關係有四個性質。首先，實線箭頭是一個偏序關係（partially ordered relation），或者說偏序。這意味著它是遞移且反自反的。而實線箭頭蘊含虛線箭頭，且反方向的虛線箭頭不蘊含實線箭頭的這個性質，你可以坐下來畫一張圖，理解它的含義，這些事情真的很容易理解。還有這個關係。以及這個相當有趣的關係，當你第一次看它時，它是其中一個看起來不太明顯的，直到你畫了一張小圖說服自己。但這是一個說明。A 箭頭 B 意味著 A 的結束發生在 B 的開始之前。虛線箭頭意味著 B 的開始發生在 C 的結束之前。實線箭頭意味著 C 的結束發生在 D 的開始之前，這蘊含 A 的結束發生在 D 的開始之前。這證明了 A4。
如果我們忽略語義，我們只取這個模型，一組操作執行和滿足 A1 到 A4 的這兩個關係，並將 A1 到 A4 作為公理。現在，關於 Bakery 演算法，我們需要做出什麼假設？首先，單個處理器中的操作執行是全序的（totally ordered）。這實際上在 Dijkstra 對其演算法的描述和證明中是隱含假定的。對於同一個記憶體字的讀取和寫入，要麼 R 虛線箭頭 W，要麼 W 實線箭頭 R。如果你看看它的語義，你會發現這對於任何一對操作來說似乎都是合理的。但我們只需要對讀取和寫入做出這個假設。在 Bakery 演算法中，每個處理器，每個記憶體字僅由單個處理器寫入。也就是說，每個共享記憶體字，一個處理器將其票券寫在某處，而且只有他自己寫自己的票券，其他處理器只讀取該票券。所以每個記憶體字只由單個處理器寫入。讓 W1、W2 為寫入序列。我們做出的假設是，一個與寫入不重疊的讀取會得到正確的答案，這意味著如果一個寫入發生在讀取之前，並且發生在下一個寫入之前，那麼 R 會讀取由前一個寫入所寫入的值。現在，這些，以及 Bakery 演算法的正確性，都遵循這些公理和假設。這是我所知的關於該演算法正確性的最優雅的證明。
同時，關於記憶體屏障的難題怎麼辦？我們想，處理器間同步要求確保不同處理器中操作執行之間的實線箭頭關係。而我們有，但是處理器間通訊只能確保不同處理器中操作執行之間的虛線箭頭關係。如果 C，某個操作 C 看到了操作 B 的效果，那麼這意味著 B 必須在 C 結束之前開始，這意味著 B 必須虛線箭頭 C。但是你無法因此推斷出任何實線箭頭關係，因為處理器間通訊。發生的是，我們使用 A4，演算法公理 A4，從處理器間的虛線箭頭關係和處理器內的實線箭頭關係推導出處理器間的關係。所以在處理器一中，我們有這種情況。我們有 A 實線箭頭 B，因為 B 虛線箭頭 C，以及 C 實線箭頭 D。從中，我們可以推導出處理器內的實線箭頭關係，即 A 發生在 D 之前。現在的現代多處理器並不按照順序執行操作。它們同時執行大量操作。我們需要記憶體屏障指令來確保在我們想要同一個處理器中兩個操作之間的實線箭頭關係時能夠獲得它。所以我們使用記憶體屏障來獲得處理器內的實線箭頭關係。我們使用處理器間通訊來獲得兩個處理器之間的虛線箭頭關係。然後我們使用 A4 來推導出處理器間的實線箭頭關係。這就是記憶體屏障工作的原因。
生產者-消費者同步
它出現在硬體中，絕對是最早建造的電腦中的一個併行問題，再次由 Dijkstra 在這份未出版的筆記中提出，也是在 1965 年。我將描述這個問題，不是以通常的生產者-消費者的說法，而是作為一個 FIFO（先進先出）佇列，也稱為一個有界 FIFO 傳輸線。這是對一個有界 FIFO 佇列的要求，即它的規範。我們假設有一個無限的輸入值序列 in，然後是一個最多可以容納一定數量的緩衝區 buff，以及一個 out 序列，它是已經輸出的值序列。我們有兩個處理器，一個生產者處理器將值從輸入移動到緩衝區，一個消費者處理器將值從緩衝區移動到輸出。
這是規範。現在在 1965 年，它會只用英文散文或偽程式碼來寫。但在 2014 年，偽程式碼已經過時了。所以我將用 Plus-Cal 演算法語言來指定它。現在的假設是，輸入 Input 是一個無限的序列。這是演算法，我們稱它為演算法 PC。聲明三個變數：in、out 和 buff。in 的初始值是 Input。out 和 buff 的初始值都是空序列。所以這些是初始值。
有兩個處理器，一個生產者處理器和一個消費者處理器。我們將給它們標識符，例如，生產者是處理器零，消費者是處理器一。這只是 Plus-Cal 語法的要求。
所以首先是生產者處理器，它是一個無限迴圈，它重複執行這個動作。它首先等待緩衝區長度小於 n。這樣就有地方放置新值。然後它將緩衝區設定為將輸入（這是一個序列，序列的第一個元素）的頭部附加到緩衝區末尾的值。它將 in 設定為 in 的尾部，即截去頭部後得到的序列。它重複執行這個動作。
現在要指定一個併行演算法，你必須說明什麼構成一個原子步驟，除非你像 Bakery 演算法那樣沒有原子步驟，那麼情況就變得更困難。但這是一個更傳統的帶有原子步驟的演算法。在 Plus-Cal 中，一個原子步驟是從一個標籤到下一個標籤的執行。所以我們在這裡放一個標籤，這意味著整個 while 迴圈主體的執行，如這個看不見的指標所示，被作為一個單一的原子步驟執行。消費者也是類似的。別擔心，Shlomi，我能應付。再次，無限迴圈。它首先等待緩衝區非空，這樣就有東西可以發送。它將緩衝區頭部附加到輸出序列的尾部，並將緩衝區設定為緩衝區的尾部。再次，臨界區段的整個主體被作為單一的原子步驟執行。
這是生產者-消費者問題的規範。你知道，要實現它，你必須用一些更低層級的演算法來實現這段 Plus-Cal，但我不會擔心這個。
標準模型中的不變性證明
不變性（invariance）作為一種證明性質的方法，由 Ed Ashcroft 於 1975 年在他這篇論文中引入，借用 Tony Hoare 的話。你可以通過證明兩件事來證明某個狀態謂詞 inv 是一個歸納不變量（inductive invariant）：inv 在初始狀態為真，並且演算法的任何一個步驟，任何一個可能的步驟，如果從 inv 為真的狀態開始，都會使其保持為真。很明顯，通過歸納法，這意味著不變量 inv 對於演算法所有可能的執行的每一個狀態都是真。借用 Tony Hoare 的話，Ashcroft 的方法是後續許多工作的顯著改進，我應該補充，包括我的一些工作。
演算法 PC 的歸納不變量是幫助我們理解演算法的歸納不變量和不變量。那麼演算法 PC 的歸納不變量是什麼？它簡單地說，緩衝區的長度小於或等於 n，並且輸入等於 out、buff 和 in 的串聯。那個小圓圈是序列的串聯。這就是不變量，它基本上告訴你所有出去的東西都進來了，並且沒有其他不應該添加到 out 的東西被添加進去。
檢查這個規範是否正確，你通常會給出的證明按照 20 世紀的標準是嚴謹的，但在 21 世紀，我們需要對事情更加嚴謹。我們確實發現需要另一個不變量的合取，即 out 是一個有限序列，buff 是一個有限序列，而 in 是一個無限序列的假設。就安全性而言，它可以是一個有限序列，但對於活絡性（liveness），我們會發現它確實需要是一個無限序列。請注意，傳統的類型檢查（type checking）說，哦，類型檢查證明了這一點。它沒有，因為例如，傳統的類型檢查會說一個取得緩衝區尾部的演算法是正確的，即使它這樣做，它可以在緩衝區為空時這樣做，這不能保證在你取得空緩衝區的尾部後，你仍然得到一個緩衝區。天知道你會得到什麼。
演算法 PC 的執行。記住，一個執行是一個狀態序列。所以它開始於
Petri 網與標記圖
一個輸入標記，它的每條輸入弧上都有一個標記，並且通過移除其每條輸入弧上的一個標記並在其輸出弧上添加一個標記來觸發。我們通過重複觸發節點來保留一個觸發序列。這是一個標記圖（marked graph）的例子。例如，我可以得到一個觸發序列。我們可以首先執行 A，通過移除其輸入弧上的這兩個綠色標記並將它們添加到其輸出弧上來觸發 A。所以我們可以首先觸發 A，然後我們可以用同樣的方式觸發 B，觸發 X，等等。
現在，這是將 N=3 的生產者-消費者問題表示為一個標記圖。這是觸發序列。首先我們能做的就是執行一個 P。然後我們可以執行另一個 P，然後我們可以執行一個 C 或一個 P，等等。請注意，頂部弧上的標記表示值在緩衝區中。我們處於一個緩衝區中有兩個值的狀態。底部弧上的標記表示緩衝區中的空位。緩衝區還有一個位置可以放入一個項目。事實證明，確定性演算法（即沒有競爭條件的演算法）的通用類別，都是可以用標記圖來表示的。所以標記圖是生產者-消費者問題的推廣。
處理器在觀察者的眼中
讓我們再看看生產者-消費者同步。讓我用另一種方式來畫這張圖。我把這個 P 放在這裡，把下一個 P 放在那裡，把第一個 C 放在這裡，把下一個 C 放在這裡。現在我要把下一個 P 放在這裡。注意我在複製每個節點和每條箭頭，等等，我得到了一個像這樣的圖。
現在，讓我這樣標記這些行，稱它們為緩衝區零、緩衝區一、緩衝區二。所以我們現在可以將其視為一個三處理器系統，其中每個處理器輪流執行一個 P 動作，然後一個 C 動作，然後一個 P 動作，然後一個 C 動作。每個緩衝區都被表示為一個處理器。這些是完全相同的表示方式，這意味著它是完全相同的圖，所以演算法也是相同的。所以我們有一個雙處理器演算法不知何故神奇地變成了一個三處理器演算法，這告訴你處理器這個概念沒有什麼神奇之處，沒有什麼根本性。正如我在論文標題中寫的，處理器在觀察者的眼中。
通常情況下，具有 N 個緩衝區的生產者-消費者同步可以被視為一個由 N 個處理器組成的系統，其中每個緩衝區都是一個處理器。第 i 個值通過緩衝區號 i 減一傳輸。所以在事件歷史模型中很容易看到這種等價性。在標準模型中也很容易看到，但只有當追蹤（traces）以數學方式而不是偽程式碼來指定時。
事件歷史模型
1977 年，這篇論文我在引言中可能提到過，實際上文章中有一個印刷錯誤。它應該是在 77 年提交的。這是一張來自論文的插圖。這裡，時間是垂直方向流動的。這些垂直線表示同一個處理器中的事件。這些波浪箭頭表示訊息。箭頭尾部的事件是發送訊息。箭頭頭部的事件是接收該訊息。
所以我們將其視為一個事件歷史。我們有這些排序關係：發送訊息的事件必須發生在接收該訊息的事件之前。一般來說，執行必須用不止一個事件歷史來表示，不像生產者-消費者那樣，而是多個可能的事件歷史。例如，從 Q 發送到 R 的這兩個不同的訊息可能會以任何順序到達。如果它們以不同的順序，相反的順序到達，那麼你會有一個不同的圖。你有一個不同的事件歷史。所以這裡有真正的非確定性（non-determinism）。
現在，如果你畫一條線，這條線將所有動作執行，所有這些節點劃分開來，並且沒有被任何弧線以錯誤方向穿過，從上方穿到下方就是錯誤方向，那麼任何這樣的劃分都表示一個在標準模型的某個行為中可達到的全域狀態。因為再次，就像生產者-消費者一樣，標準模型中的執行是通過找到所有事件的任何一個與這個偏序一致的序列順序來獲得的。所以任何一條劃分動作執行的線，只要沒有被弧線以錯誤方向穿過，使得所有在上半部分的事件在偏序上都發生在下半部分的事件之前。所以這是另一條這樣的線，表示一個可能的全域狀態。
所以這裡我們有同一個事件歷史產生了不同的全域狀態。這表明分散式系統沒有有意義的全域狀態概念，因為對於某個處理器的任何局部狀態，可能有許多全域狀態，可能的全域狀態，對於該處理器來說看起來是相同的局部狀態。所以我們不應該從全域狀態的角度思考，我們不應該使用標準模型，對嗎？
聽起來合理，但卻是錯誤的。理解和推理分散式系統的最佳方法是藉助全域不變量（global invariants）。這沒問題，可能存在多個不相容的全域狀態，這並不是說這有什麼不對，因為我們討論的是對所有可能的全域狀態都為真的事情，而不僅僅是標準模型中某個表示中的所謂實際全域狀態。並且，精確地指定演算法或系統並嚴謹地對其進行推理的最佳方法是使用標準模型。其他模型可以提供有用的洞察力。它們可以幫助我們發明演算法，它們可以幫助我們設計涉及系統設計的這種創造性概念。但是，當在洞察力之後，在創造力完成之後，需要精確地指定和驗證你的演算法或你的電腦系統時，你應該使用標準模型，因為它有效，就這麼簡單。
重訪實線與虛線箭頭關係
回想一下，一個事件歷史是一組執行以及一個偏序關係 <，或者我寫作 <。現在，將 E 劃分為一組稱為操作執行的事件集合。然後對於 U 和 V，我們定義 U 實線箭頭 V 意味著對於 U 中的每一個事件 E 和 V 中的每一個事件 F，E 發生在 F 之前。這就是實線箭頭的含義。所以例如，包含 P1 的操作執行發生在由 P3、P4 和 P5 組成的操作執行之前。而虛線箭頭，除了將「對於每一個」替換為「存在」之外，其他都一樣。它說 U 虛線箭頭 V，有時讀作 U 可能因果影響 V，如果 U 中存在某個事件發生在 V 中某個事件之前。
這是實線箭頭的一個例子。這些定義蘊含了公理 A1 到 A4。所以，同樣的事情適用於，我們的系統不必離散地定義。如果操作執行實際上是時空中的區域，並且偏序關係是狹義相對論中的可能因果影響關係，那麼它也可以是正確的。
遺漏
正如我所說，這是一段不完整的併行歷史。以下是我遺漏的一些內容：活絡性（liveness）和公平性（fairness）。公平性假設是由 Dijkstra 在 1974 年為了確保活絡性而引入的，但沒有人注意到。事實上，我最大的貢獻之一是在 83 年的 POTSI 受邀演講中，提醒人們 Dijkstra 的文章。人們更需要被提醒而不是被告知，這被考慮得不夠充分。但我現在沒有時間深入探討這個問題，所以這將留給其他人來撰寫下一章。
- 活絡性與公平性
- 由 Amir Pinueli 於 1977 年在他的論文中引入的時間邏輯（temporal logic）是形式化推理活絡性的最佳方法。
- 程式語言結構，如號誌（semaphores）、條件臨界區段（conditional critical regions）、監視器（monitors）等，所有這些東西。70 年代的大部分關於併行、併行程式設計的文獻都是關於實現併行的語言結構。它們是關於語言設計，而不是原則或演算法。
- 我認為可以肯定地說，大多數關於語言設計的論文已經被遺忘了，但像 Dijkstra 這樣關於原則的論文卻沒有。
- 其他模型，那些似乎影響力最大的模型是 CCS (Milner's calculus of communicating systems)、Tony Hoare 的 CSP (I forget what that stands for)、Petri nets。它們都可以被視為程式語言，而且它們的程式實際上可以用標準模型來描述，但這樣做並不能體現它們的價值，因為它們是為了研究那些在標準模型中不容易表達的性質而引入的。事實上，這些性質通常不是像我這樣研究併行演算法的研究人員感興趣的安全性或活絡性性質。結果，併行演算法和併行理論，後者通常被認為與程序代數（process algebra）同義，基本上分裂成了兩個獨立的領域。我不知道它們最近是否已經重新結合。
- Petri nets，其標記圖（marked graphs）是 Petri nets 的一種特殊形式，設計成不能有仲裁（arbitration）。在 Petri nets 中，Petri nets 的一個優點是仲裁在語法上是可見的。你可以通過語法查看 Petri net 並確定，例如，是的，有仲裁，不，沒有。然而，Petri nets 最初引入時表達能力不夠，無法建模併行演算法，因為它們本質上是有限狀態的。所以它們被擴展了各種額外的功能。我認為
從我的角度來看，它們基本上已經變成了程式語言。這大約涵蓋了 65 年到 77 年。78 年發生了什麼？容錯（Fault tolerance）。容錯實際上是由 Dijkstra 在 1974 年引入的，但沒有人注意到。事實上，我最大的貢獻之一是在 83 年的 POTSI 的一次受邀演講中，提醒人們 Dijkstra 的文章。人們更需要被提醒而不是被告知，這被考慮得不夠充分。但我現在沒有時間深入探討這個問題，所以這將留給其他人來撰寫下一章。謝謝。
[掌聲]