算法模型
并發執行算法的模型與順序執行算法不一樣。在設計順序執行算法時，我們的出發點是如何減少執行的步數（時間開銷）和記憶體的占用空間（空間開銷），我們會很習慣地思考第一步做什麼、第二步做什麼。
但在面對并發執行算法時，其執行軌迹空間與程序數、步數的階乘成正比，這種第一步做什麼、第二步做什麼的思維就會面臨巨大的困難。
為分布式算法編寫過代碼的讀者一定有這樣的經曆：在編寫每行代碼時，都要考慮有哪些程序的哪行代碼可能會與本行代碼并發執行？如果并發執行會造成什麼後果？等等。
看似簡單的十幾行代碼可能會耗費我們一整天的時間去思考它的正确性，就是因為這寥寥數行代碼對應的執行軌迹空間太大了！若要保證每個執行軌迹都是正确的，需要大量的腦力。常見的情況是，即使我們對着十幾行代碼盯了一整天，可代碼運作一陣子後還是出錯了，于是我們隻能繼續修改。最無奈的情況是，我們即使絞盡腦汁，也隻能讓錯誤出現得更晚一點。是以，我們必須換一個思路去設計分布式算法。
I/O自動機
1987年，Nancy A.Lynch和Mark R.Tuttle在他們的論文中首次提出輸入/輸出自動機（Input/Output Automaton，I/O自動機）模型，目前它已經被廣泛用在各種異步并行系統的模組化中。作為一種異步并行系統，分布式系統也可以通過I/O自動機模組化。
基本模型
我們可以把一個程序看成一個自動機，把一個分布式系統看成一個自動機叢集，其中，每個自動機都執行相同的算法。是以，設計一個分布式算法，其實就是設計一套讓所有自動機都遵照執行的算法。
順序執行算法研究的是第一步做什麼、第二步做什麼，一連串動作下來，問題得以解決；而分布式算法研究的是在什麼情況下應該執行什麼動作。這裡的“情況”就是事件，例如收到某個消息可以看作一個事件，自動機處于某個狀态也可以看作一個事件；“動作”就是改變自動機的狀态。設計分布式算法的目标，就是讓系統中的自動機叢集達到我們想要的狀态。
接下來，我們依次介紹狀态和事件。
每個自動機有自己的記憶體空間，可以維持自己的狀态。所謂狀态，可以了解為自動機内部用于表示某些狀态的變量值。例如，有一個選主自動機，它用一個内部變量leader表示目前主程序，那麼變量leader的值就是這個選主自動機的狀态。我們希望看到的是，選主自動機叢集中的每個自動機的變量leader都指向同一個正常工作的程序，這也是我們設計分布式選主算法的目标。一個自動機可以有無限多個狀态，這樣可以用來描述一些無容量上限的資料結構，例如計數器或不限長度的隊列等。
自動機的行為是由事件驅動的。所謂事件，就是需要自動機執行某些動作的那些“情況”。我們可以為自動機a定義一個簽名（Signature），記為acts（
a）。簽名實際上是一個事件集合，自動機a的簽名就是自動機a可能接收和發送的全體事件集合。
為了更好地了解簽名，我們用C語言作類比。在C語言中，函數的簽名是指這個函數的輸入參數和傳回值的類型，它描述了函數與外界互動的資料的類型。
也可以這麼了解：函數的簽名就是該函數能夠接收的所有輸入參數和産生的所有傳回值的全體集合。同理，自動機的簽名描述了該自動機可以接受的事件的類型，即符合該類型的全體事件集合。
如果一個事件的類型不屬于某個自動機的簽名，那麼該自動機會忽略該事件。若無特殊說明，下面提到的事件都是簽名中的事件。
自動機a的簽名可以分為輸入事件、輸出事件和内部事件這三個兩兩不相交的三個事件子集，分别記為in（a）、out（a）和int（a），且acts（a）=in（a）∪out（a）∪int（a）。
輸入事件和輸出事件可用于自動機與外部環境的通信，是以被統稱為外部事件或者接口事件，這個外部環境被稱為運作時環境。内部事件是自動機自己觸發、自己處理的事件，僅對自動機自身可見。輸出事件和内部事件是自動機觸發的，受自動機的控制，是以被統稱為本地事件。輸入事件的觸發不受自動機的控制，自動機随時都有可能收到輸入事件。
例如，自動機從運作時環境收到消息是輸入事件，自動機發送一個消息給運作時環境是輸出事件，自動機的内部狀态滿足某個條件而觸發的事件是内部事件。
事件可以驅動自動機狀态的變化，這個變化被稱為狀态轉移（State Transition）。一個自動機可以有一個或多個初始狀态，這是自動機進行狀态轉移的起點。如果自動機通過事件e從狀态s轉移到狀态s1，就可以表示為“s-e-s1”，并且說“事件e在狀态s下是激活（enable）的”。由于自動機在任何時候都有可能收到輸入事件，是以輸入事件在任何狀态下都是激活的。
一次狀态轉移被稱為一步（Step）。步是不可再分的，一個自動機必須執行完這一步，才能開始執行下一步，不能同時執行兩個步。這一點非常重要，後續所有的算法都是基于這一點而設計的。
圖 2-1 是一個雙向通信鍊路的自動機，它的狀态由内部的發送隊列和接收隊列組成。在初始狀态下，兩個隊列均為空。它的簽名由兩個事件組成，其中一個是輸入事件<Send|m＞，當自動機收到該輸入事件時，會把消息m放入發送隊列尾部，使發送隊列的長度從0變成1，實作狀态轉移。當接收隊列不為空時，自動機會把接收隊列頭部的消息取出，并觸發一個輸出事件<Receive|m＞，表示它收到了一個消息 m。自動機随時可能收到輸入事件<Send|m＞，是以它永遠都是激活的。至于消息m是如何從一個程序的發送隊列進入另一個程序的接收隊列的，這取決于通信鍊路的實作方案。
圖 2-1 雙向通信鍊路的自動機
組合模型
在設計順序執行算法時，往往會用子產品化的思想實作代碼複用。例如，在 C 語言中，我們可以在函數func1 的實作中調用函數func2，進而避免在函數func1 中重寫函數func2的邏輯。同理，在I/O自動機模型中，我們也可以讓自動機a“調用”自動機b，進而避免在自動機a中重寫自動機b的邏輯。
隻不過在函數調用中，函數func1必須等待函數func2傳回，才能執行後續邏輯；而在自動機的調用中，自動機a在調用了自動機b的輸入事件後無須等待，即可繼續執行後續邏輯。
通過對一些基礎的自動機進行組合，可以構成更大、更複雜的自動機。
在組合的過程中，這些基礎的自動機被稱為部件自動機（Component Automaton），所構成的自動機被稱為合成自動機（Composed Automaton）。
令集合I表示系統中所有自動機的編号的全集，編号為i的部件自動機用ai表示，合成自動機用a表示。若要将多個部件自動機組合為一個合成自動機，則對于任何兩個不同的部件自動機ai和aj，必須滿足如下條件。
（1）int（ai）∩acts（aj）=∅，即部件自動機的内部事件僅作用于該部件自動機内部。
（2）out（ai）∩out（aj）=∅，即不同部件自動機的輸出事件是不同的。
上述條件被稱為相容條件。将滿足相容條件的部件自動機組成合成自動機，規則如下。
（1）合成自動機的狀态是各個部件自動機的狀态的集合。
（2）每個部件自動機的輸出事件都是合成自動機的輸出事件，即out（a）=∪{out（ai）， i∈I}。
（3）每個部件自動機的内部事件都是合成自動機的内部事件，即int（a）=∪{int（ai）， i∈I}。
（4）部件自動機的輸入事件若不是其他部件自動機的輸出事件，那就是合成自動機的輸入事件，即in（a）=∪{in（ai）， i∈I}-out（a）。
（5）共享同一個事件的所有部件自動機都同時進行狀态轉移，而其他部件自動機不進行狀态轉移。
例如，部件自動機a、b、c、d的狀态分别為sa、sb、sc、sd，事件e既是自動機a的輸出事件，又是自動機b和c的輸入事件，但不是自動機d的任何事件。那麼當事件e發生時，自動機a、b、c同時進行狀态轉移，而自動機d不發生狀态轉移。對于合成自動機而言，它的狀态轉移可表示為“（sa，sb，sc，sd）-e-（sa'，sb'，sc'，sd）”（注意：sd未發生變化），且隻能算一步，而不是多步。
同時，根據條件1和規則3可知，該合成自動機的内部事件必然隻屬于某一個部件自動機，是以當合成自動機因内部事件進行狀态轉移時，隻有其中一個部件自動機會發生狀态轉移。
隐藏操作
子產品化的好處是不僅可以提升代碼的複用率，還可以隐藏一部分内部細節。例如在C語言程式設計中，對那些無須外部可見的函數，可以加上static關鍵字，使之變成一個靜态函數，這就是一種隐藏實作細節的做法。
在 I/O 自動機模型中，為了讓合成自動機在後續進一步合成時減少暴露内部事件，可以對合成自動機采取隐藏操作（Hiding Operation）。将這部分需要被隐藏的接口事件記為集合 Φ，那麼隐藏操作後所得到的自動機 A′的簽名與隐藏操作前的合成自動機A的關系如下。
in(A')=in(A)out(A')=out(A)\ Φ
int(A')=int(A) ∪ Φ
也就是說，隐藏操作并不改變合成自動機的輸入事件，隻是把一部分需要隐藏的接口事件轉成了合成自動機的内部事件。
圖 2-2所示為兩個程序x和y通過加密鍊路進行單向通信的合成自動機。
程序x有一個合成自動機p，它由加密自動機a和發送鍊路自動機c組成；程序y有一個合成自動機q，它由解密自動機b和接收鍊路自動機d組成。
圖2-2 通過加密鍊路進行單向通信的合成自動機
加密自動機a在收到輸入事件<Read|m＞後，對消息m進行加密，生成消息m'，并将m'放入加密緩存。
當加密緩存不為空時，自動機 a 從加密緩存中取出消息 m'，然後調用發送鍊路自動機c的輸入事件<Send|m'＞，完成狀态轉移。自動機c收到輸入事件<Send|m'＞後，将消息 m'放入發送隊列，完成狀态轉移。對于合成自動機 p 而言，這兩個狀态轉移在一步内完成。
當接收鍊路自動機d的接收隊列不為空時，自動機d從接收隊列中取出消息m'，然後觸發輸出事件<Receive|m'＞，完成狀态轉移。當解密自動機b收到自動機d發出的輸出事件<Receive|m'＞後，将消息m'解密為消息m，然後放入解密緩存，并觸發輸出事件<Write|m＞，完成狀态轉移。對于合成自動機q 而言，這兩個狀态轉移在一步内完成。這樣，程序x和y就完成了單向的加密通信。至于消息m'是如何從自動機c的發送隊列進入自動機d的接收隊列的，這取決于通信鍊路的實作方案。
組合模型不僅使合成自動機p和q分别複用了發送鍊路自動機c和接收鍊路自動機d，同時還分别隐藏了<Send|m'＞和<Receive|m'＞事件，使自動機p對外僅有一個輸入事件<Read|m＞，自動機q對外僅有一個輸出事件<Write|m＞。
與業務邏輯的關系
在真實的應用中，業務邏輯和分布式邏輯是共存的，但本書中的I/O自動機模型僅針對分布式邏輯，不針對業務邏輯。也就是說，業務邏輯使用什麼模型，與分布式邏輯無關。下面舉例說明。
假如有一個分布式線上購物應用，該應用部署在n台伺服器上，伺服器之間沒有任何共享資料，僅通過網絡互相通信。該應用的業務邏輯中的一個環節是把商品放到購物車中暫存，在一段時間内，消費者（用戶端）可以通過任何一台伺服器通路購物車，且能夠看到完全相同的商品清單。而過了一段時間後，該消費者的購物車就被清空了。
業務邏輯與分布式邏輯分層示意圖如圖 2-3所示。從縱向來看，該購物應用由n個程序組成，它們之間沒有共享資料，通過網絡（圖中未畫）進行通信；從橫向來看，該購物應用由業務邏輯（虛線部分）和分布式邏輯（實線部分）組成。在業務邏輯中有一個購物車子產品，它以異步的方式與分布式邏輯中的緩存自動機進行互動。在分布式邏輯中，緩存自動機與廣播自動機、鍊路自動機之間也以異步的方式進行互動。本書所描述的算法僅針對分布式邏輯，不涉及任何業務邏輯。
需要特别指出的是，有些人認為，為了提升性能，采取緊耦合的算法比子產品化的算法要好。對于設計分布式算法來說，這種觀點是非常危險的。如1.3.1節所述，一個分布式系統可能的執行軌迹的數量是O（n！），其中n與程序的步數成線性正比，是以每增加一個步驟，就會導緻執行軌迹的數量大幅增加，進而導緻編寫正确代碼的難度大幅增加。
一些軟體開發人員為了提升性能，把原本可以分開的分布式邏輯揉在一起，甚至把業務邏輯與分布式邏輯也揉在一起，最後發現可能的執行軌迹太多了，幾乎無法保證代碼實作的正确性。是以，分布式算法比順序執行算法更需要子產品化的思想，要盡可能地讓每個子產品的任務簡單，才能更容易編寫正确的代碼。
圖2-3 業務邏輯與分布式邏輯分層示意圖
小結
設計分布式算法就是在設計 I/O 自動機的簽名及其内部實作狀态和狀态轉移邏輯，使各個自動機互相協同。例如，對于一個分布式選主算法，每個程序都有一個用來表示主程序的狀态變量leader，該算法的目标是讓每個程序的leader變量都指向同一個活着的程序。
盡管一個允許多程序并發運作的分布式系統十分複雜，但通過I/O自動機模型，我們仍然有機會像設計順序執行算法那樣，對并發執行的分布式算法進行子產品化，抽象出部件自動機，并通過組合實作更複雜的合成自動機，實作豐富的功能。
程式設計模型
在了解了I/O自動機和分布式系統模型之後，為了将I/O自動機模型變成算法，我們還需要定義一套描述I/O自動機模型的語言，這就是本節所要介紹的程式設計模型。
我們仍然用C語言來對比。在C語言中，一個函數可以分為定義、實作和執行三個部分。對于函數的定義，我們隻關心非靜态函數的簽名和功能，因為靜态函數對外是不可見的。在函數的實作中，我們才考慮算法邏輯。
同理，我們把自動機的定義稱為抽象（Abstraction）。例如，一個鍊路自動機被稱為鍊路抽象，一個廣播自動機被稱為廣播抽象，等等。對于抽象，我們隻關心它的接口事件（内部事件對外不可見）和功能，而不關心它的内部事件或實作細節。
自動機的實作方法被稱為算法，它實作了抽象。一個抽象可能有多種不同的實作算法。與順序執行算法類似，不同的算法有不同的性能特征，例如，有的算法的時間複雜度高，有的算法的空間複雜度高。但與順序執行算法不同的是，同一個抽象的不同實作算法可能有不同的适用條件，例如程序失敗模型、時間假設及韌性等，隻有滿足這些條件，算法才是正确的。這也是順序執行算法和分布式算法的一個不同之處。
正在運作的自動機被稱為執行個體（Instance）。例如，一個正在運作的鍊路自動機被稱為鍊路執行個體，一個正在運作的廣播自動機被稱為廣播執行個體，等等。
執行個體可以被運作時環境建立或銷毀，也可以自己銷毀自己，但不能自己建立自己。一個分布式系統由多個程序組成，每個程序pi都運作了自動機A的執行個體ai，這些執行個體的集合{ai|i∈I}被稱為自動機A的執行個體組（Instance Group）。
在不産生歧義且不需要強調的情況下，我們有時會省略“抽象”“實作”“算法”“執行個體”“執行個體組”這些特指的表達方式，而直接用自動機的名字。例如廣播抽象、廣播實作、廣播算法、廣播執行個體、廣播執行個體組等，可直接用“廣播”兩字簡化。
同理，在不産生歧義且不需要強調的情況下，我們有時也會把“程序的某某執行個體如何如何”簡述為“程序如何如何”。例如，“程序p内的鍊路執行個體a發送了消息m”可被簡述為“程序p發送了消息m”，“程序p内的鍊路執行個體a接收了消息m”可被簡述為“程序p接收了消息m”。
調用關系
在描述順序執行算法時，函數間通過參數和傳回值進行通信。但實際上，參數和傳回值是人為分類的，兩個函數完全可以利用一個共享變量進行通信。當把 C 語言編譯成彙編語言後，彙編語言中的兩個過程其實就是靠共享的寄存器或記憶體進行通信的。區分參數和傳回值的好處是有利于階層化，更清晰地區分誰是請求者、誰是實作者，是以被廣泛使用。
同理，作為分布式算法中執行個體間通信的接口，事件本不需要分類，但為了更好地将執行個體階層化，更清晰地區分誰是請求者、誰是實作者，我們可以把輸入事件看成參數，把輸出事件看成傳回值。
執行個體間的調用關系如圖 2-4所示，對于執行個體a而言，執行個體a請求執行個體b的過程被稱為調用（Invoke），即“執行個體a調用了執行個體b的一個輸入事件”；對于執行個體b而言，執行個體a請求執行個體b的過程被稱為受理（Accept），即“執行個體b受理了一個輸入事件”。接下來，執行個體b繼續調用執行個體c的一個輸入事件。
當執行個體 c 處理完輸入事件後，将“宣告（Declare）一個輸出事件”；因為執行個體 c的輸出事件屬于執行個體b的簽名，是以“執行個體b将感覺（Perceive）執行個體c的輸出事件”。接下來，執行個體b将繼續宣告一個輸出事件，因為執行個體b的輸出事件屬于執行個體a的簽名，是以執行個體a将感覺執行個體b的輸出事件。
一個執行個體調用另一個執行個體的輸入事件，或宣告本執行個體的輸出事件，統稱為觸發（Trigger）事件；一個執行個體受理本執行個體的輸入事件，或感覺另一個執行個體的輸出事件，統稱為收獲（Obtain）事件。我們假設在同一個程序内部，觸發一個事件和收獲這個事件是同時發生的。這意味着，執行個體a調用執行個體b的輸入事件e1，與執行個體b受理了輸入事件e1，兩者是同時發生的；執行個體c宣告一個輸出事件e2，與執行個體b感覺輸出事件e2，兩者也是同時發生的。
如果把執行個體b和執行個體c看成一個合成自動機執行個體，那麼執行個體b和執行個體c之間的輸入和輸出事件就變成合成自動機的内部事件了。
圖2-4 執行個體間的調用關系示意圖
注意，當執行個體 a 調用執行個體 b 的輸入事件時，我們會明确說“……調用了執行個體 b的……”；而當執行個體b受理了這個輸入事件時，我們不會說“……受理了執行個體a調用的……”。這是因為，執行個體 b 不是從執行個體 a，而是從運作時環境中受理了一個輸入事件。同理，當執行個體b宣告一個輸出事件時，我們不會說“……向執行個體a宣告了……”，這是因為執行個體b不是向執行個體a，而是運作時環境宣告了這個輸出事件。實際上，執行個體b并不知道哪個執行個體會感覺到這個輸出事件，因為可以有多個自動機執行個體感覺到這個輸出事件，隻要這些自動機的簽名包含了這個輸出事件。總之，隻有調用（或感覺）方關心它調用（或感覺）的是誰，而受理（或宣告）方不關心誰在調用（或感覺），隻是“埋頭苦幹”地處理事件。
在約定了上述調用關系後，合成自動機内部的層次關系就變得更加明确和清晰了，這有助于我們在簡單的部件自動機的基礎上建構功能更強大、更複雜的合成自動機，實作更複雜的分布式算法。同時，開發者可以繼續以順序執行的思維模式開發上層應用：當需要調用底層分布式算法時，首先調用底層執行個體的輸入事件，然後等待底層執行個體宣告一個輸出事件。在此過程中，上層應用處于阻塞狀态。這樣就把一個異步過程轉化成了同步過程，大大降低了上層應用的開發難度。
事件和事件處理器
事件由類型和屬性組成，我們将其記為<Event|Attr，…＞。
不同的自動機抽象可能會使用相同的事件類型來定義事件，例如鍊路抽象和廣播抽象都定義了輸入事件<Send|m＞，但顯然兩者的語義是不同的。此外，同一個自動機抽象可以對應多個不同的自動機執行個體。為了更清晰地指出這是哪個執行個體的哪個事件，我們把自動機執行個體a的事件記為<a，Event|Attr，…＞。但是在不産生歧義且不需要強調的情況下，我們有時将其簡寫為<Event|attr，…＞、<a，Event＞或<Event＞。
當需要調用執行個體a的輸入事件<Event|…＞時，可以用“invoke<a，Event|…＞”這樣的語言。當執行個體a需要宣告輸出事件<Event|…＞時，可以用“declare<a，Event|…＞”這樣的語言。當需要收獲執行個體a的事件<Event|…＞，則可以用“when event<a，Event|…＞do”這樣的語言，後面再接上事件處理過程，這個事件處理過程被稱為事件處理器。
下面是某個自動機執行個體a的算法片段，在注釋中有每行語句的語義。當執行個體a受理一個輸入事件<a，Event＞時，就調用執行個體a1的輸入事件<a1，Event1＞；當感覺執行個體a1宣告的輸出事件<a1，Event2＞後，就宣告執行個體a的輸出事件<a，Event3＞。其中，輸入事件<a1，Event1＞和輸出事件<a1，Event2＞是整個合成自動機執行個體的内部事件，輸入事件<a，Event＞和輸出事件<a，Event3＞是整個合成自動機執行個體的接口事件。
通常，我們通過上下文就能判斷這個事件到底是輸入事件還是輸出事件。為了簡化表達，在不産生歧義且不需要強調的情況下，我們不會每次都說“輸入事件<Event＞”或者“輸出事件<Event＞”，而是直接說“事件<Event＞”，甚至直接說“<Event＞”。因為“<＞”是事件的獨有表示方式，是以一個完整的事件表達“輸入事件<a，Event|attr…＞”可以被簡化為“<Event＞”。
自動機執行個體在被運作時環境初始化之後，就開始等待簽名中的事件。對于不屬于簽名中的事件，即使自動機執行個體所處的程序的底層收到了，例如程序從網絡中收到了包含事件的封包，自動機執行個體也會忽略它。對于屬于簽名中的事件，執行個體将進行處理。
所謂處理事件，其實就是做兩件事情：第一，進行狀态轉移，例如将變量leader從“未知”改為1，表示“将辨別為1的程序選為主程序”；第二，觸發相應的事件，例如宣告一個輸出事件，并在該事件的屬性中指名主程序的辨別。
如果一個執行個體a的輸出事件恰好是另一個執行個體b的輸入事件，那麼執行個體a在執行完事件處理器後，執行個體b會立即執行相應的事件處理器，且這兩個事件的處理過程是不可分割的，對于整個合成自動機而言，這是其中的一步。
如果執行個體在處理某個事件的同時收獲了新的事件，執行個體不會立即處理新事件，而是繼續處理原事件，直到完成完整的一步。這一點非常重要，它確定了執行個體的狀态不會被兩個事件處理器并發地修改。當第一個事件處理完成之後，執行個體會依據最新的而非原來的狀态繼續處理新事件。
簽名中的每個事件被選中的機率大于0，不會出現某個事件因系統性的阻塞而永遠得不到處理的情況，這被稱為公平排程。
若某個執行個體将要收獲的事件是來自本程序的，那麼該事件遲早會被該執行個體處理。如果某個執行個體收獲了多個來自本程序的事件，那麼這些事件的處理順序與它們的觸發順序是相同的。
有時，事件處理器的執行并非因為收獲了某個事件，而是因為執行個體的狀态達到了某個條件。這種事件處理器由when開頭，然後是條件。這種事件處理器的形式如下：
有時，事件處理器的執行不能僅憑是否收獲了某個事件，執行個體内部的狀态還必須達到某個條件，兩者缺一不可。這種事件處理器的形式如下：
有時，such that後面的condition先被滿足，而尚未收獲事件，此時事件處理器不會被執行。有時，事件已經收獲了，但是such that後面的condition尚未得到滿足，此時事件将會被暫存在執行個體的存儲空間中，等到such that後面的condition被滿足，事件處理器才會執行。然而在真正實作時，一個執行個體能夠暫存的事件數量是有限的。
如果無法暫存更多的新到來的事件，要麼就拒絕感覺新的事件，進而造成某種程序失敗（3.4.2 節會提到，這屬于遺漏式失敗）；要麼就将緩存的事件寫入持久化存儲中，待condition被滿足後再從本地存儲中删除。本書假設的是後一種情形。
抽象和實作
抽象是自動機中的定義。抽象由一個名字（Name）來辨別，并由一些特性（Properties）加以區分。所謂特性，是指實作這個抽象的執行個體必須滿足的一些性質，例如，一個選主執行個體必須滿足“最終有一個正确的程序被選為主程序”的性質。
抽象還定義了接口事件，即輸入和（或）輸出事件。上層應用可以通過接口事件與自動機執行個體進行通信。例如，一個選主抽象定義了一個輸出事件<Leader|p＞，當上層應用感覺到選主執行個體宣告的輸出事件<Leader|p＞後，就知道程序p已經被選為主程序了。
抽象 2-1中定義了一個簡單的Task處理器抽象，這個抽象的名字是TaskHandler。該抽象定義了輸入事件<Submit|task＞，上層應用可以調用該輸入事件送出task。該抽象還定義了一個輸出事件<Confirm|task＞，當 TaskHandler 執行個體受理了輸入事件<Submit|task＞後，就會宣告輸出事件<Confirm|task＞，确認task已被送出。
該抽象定義了TH1響應保證特性，該特性要求每個送出的task都會被确認，但該特性并未保證task被确認時task已經被處理了。
算法2-1是抽象2-1的一個簡單的同步實作。
“Instance：th implements TaskHandler”表示執行個體th實作了抽象TaskHandler。該算法比較簡單。當執行個體th受理了輸入事件<Submit|task＞後，就開始處理task。當task處理完成後，執行個體th就宣告一個輸出事件<Confirm|task＞。在這個算法實作中，當執行個體th宣告輸出事件<Confirm|task＞時，task已經被處理完了，但上層應用并不應該做此假設，因為TaskHandler抽象的特性并沒有做此承諾。
算法 2-2實作了抽象 2-1定義的TaskHandler執行個體th。它使用了一個特殊的輸入事件<Init＞，這是一個初始化事件。初始化事件比較特殊，執行個體在被初始化時，它會被運作時環境自動調用，往往用于初始化執行個體内部的一些狀态。在本算法中，集合buffer就是該執行個體的狀态。當執行個體處理初始化事件時，将集合buffer設定為空集（用∅表示）。
此外，該異步實作還針對内部狀态設定了事件處理器，即當集合buffer不是空集時，則從集合buffer中挑出一個task進行處理，處理完成後，将該task從buffer中去除。顯然，這是一個異步的實作，因為當執行個體宣告輸出事件<Confirm|task＞時，僅僅表示确認這個task被送出了，并不表示這個task被處理了。
抽象2-2定義了一個有緩存上限的Task處理器抽象，名字叫BufferedTaskHandler。如果上層應用調用輸入事件<Submit|task＞的速度太快，那麼BufferedTaskHandler的執行個體将宣告輸出事件<Error|task＞給上層應用，以示拒絕。
算法2-3實作了抽象2-2定義的BufferedTaskHandler執行個體bth。“Uses：TaskHandler，instance th”表示執行個體bth需要使用（Use）一個TaskHandler執行個體，這個TaskHandler執行個體用變量th表示。
對于同一個抽象，在不同的假設下可以有不同的算法，是以每個算法都有其适用的假設。例如，“Assumes：Fail-Silent，f<N”表示該算法适用于靜音型失敗模型，且韌性f小于程序總數N。這也是算法未指明适用假設時預設适用的假設。至于失敗模型、韌性的含義，會在第3章中介紹，讀者可以暫時忽略這些看不懂的名詞。
為了更好地展示子產品化的設計思想，執行個體bth隻負責檢查集合buffer是否溢出，而把處理task的工作交給了底層的執行個體th，使整個算法層次更清晰、更容易了解。BufferedTaskHandler子產品化示意圖如圖 2-5所示，當上層應用需要送出一個task時，就調用執行個體bth的輸入事件<Submit|task＞。執行個體bth會檢查buffer是否溢出，如果是，則執行個體bth将宣告輸出事件<Error|task＞給上層應用，表示拒絕task；否則，先将task放入buffer，然後宣告輸出事件<Confirm|task＞。
圖2-5 BufferedTaskHandler子產品化示意圖
同時，當buffer不為空且handling為FALSE（表示沒有task待處理）時，那麼從buffer中取出一個task，然後調用執行個體th的輸入事件<Submit|task＞，讓底層的執行個體th去處理task，并将handling設為TRUE，表示執行個體th正在處理某個task。當執行個體bth感覺到執行個體th宣告的輸出事件<Confirm|task＞後，就知道執行個體th已經完成處理了，并将handling設為FALSE。
如果執行個體bth需要同時送出多個task給底層的TaskHandler執行個體，則可以相應地使用多個TaskHandler執行個體，并用更多的執行個體變量來表示，例如th1、th2等。
本文給大家講解的内容是算法模型：I/O自動機、程式設計模型
- 下文給大家講解的内容是系統模型