# 1-1 Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services
探討在分散式系統中實現**一致性(Consistency)**、**可用性(Availability)和分區容忍性(Partition Tolerance)** 三個特性的可行性。**證明在異步網路模型中，這三個特性是不可能同時達成的**，並進一步**討論了在部分同步模型中解決此問題的方法**。透過理論分析和模型建立，文章提出了在特定條件下達成其中兩個特性的可能性，並探討了實現這一目標的策略和實際應用。

## 1. Introduce

Brewer提出一個猜想：在一個網路服務中不可能同時提供下列三種服務
* **availability(可用性)**
* **consistency(一致性)**
* **partition tolerance(分區容忍性)**

整篇論文首先解釋這個猜想的意思，進而證明其正確性，並嘗試提出可行的解決方案，最後指出在一個高度分散的網路上，提供一定的容錯能力是被允許的，當一些節點crash或一些通訊link失敗時，服務還是可以按預期執行。在本篇論文中，不會考慮那些導致整個過程停止運作的失敗情形。

## 2. Formal Model(定義CAP三種服務)
* **Atomic Data Objects(consistency)：**

這邊將一致性服務的概念形象化成 Atomic Data Object，在一致性的保證下，所有操作必須存在一個完全的順序，使得每個操作看起來就像是在單一瞬間完成的，**每一次對系統的讀取皆能讀到最新一次寫入的資料。**
* **Available Data Objects(available)：**

**每一次對系統的請求皆能返回結果**，也就是系統中的每一個非失敗節點接收到的每一個請求都必須回復一個結果一個響應，即使發生嚴重的網路故障，每個請求也必須終止。
* **Partition Tolerance：**

網路允許丟失從一個節點發送到另一個節點的消息，導致網路被分區，系統分成兩個或多個子系統無法通訊，在此情形下，在網路被分區的情況下，整個系統仍能保持運作返回正確結果。

## 3. Asynchronous Networks
### 3.1 Impossibility Result
定理1如下：
:::info
透過反證法證明**在所有公平的執行的異步網路模型中，實現一個同時保證Atomic consistency和availability的讀/寫data object是不可能的。**
設立一個場景，假設網路至少由2個node組成，因此可以被劃分成2個不相交的非空集合G1和G2，假設G1和G2的通訊全斷，就算沒有其他客戶端請求干擾，一個節點組中的寫操作完成後，另一個節點組的讀操作也無法獲得該寫操作的更新值，從而違反了線性一致性的定義。


fair execution指的是包含訊息遺失的執行
:::

接著透過定理1.1推論到推論1.1如下
:::info
在異步模型中，算法無法確定消息是已經lost還是在傳輸中被延遲。因此，如果存在一個算法，在沒有消息丟失的執行中保證線性一致性，那麼就會存在一個在所有執行中都能保證線性一致性的算法。這違反定理1。

:::

### 3.2 Solutions in the Asynchronous Model
雖然在異步模型中，雖然無法同時實現一致性、可用性和分區容忍性這三個屬性，但可以達成其中的任意兩個。
#### 3.2.1 Atomic, Partition Tolerant
如果一個執行中的所有消息都被送達，系統就是可用的，且所有操作都能順利中止。也就是說，只要系統內部有一個元件還沒更新成最新結果，就一律返回錯誤，直到元件彼此重新連上線，同步完結果後，讀取請求才會返回正確結果。

這邊舉一個簡單的中心化算法可達到上述的請求：指定一個特定的節點負責維護數據對象的值，當有讀寫請求時，其他節點會將請求轉發給這個特定的節點，由它來回應請求。只有在沒有任何故障發生的情況下，系統的活性才能得到保證。這意味著在理想狀態下，系統能保證操作的完成，但在出現故障的情況下，這種保證就不再成立。同時也代表只有在無故障的情況下，這三者才可能同時被滿足。
#### 3.2.2 Atomic, Available
如果沒有分區，一定可以提供Atomic、Available的特性。舉例：執行在內網或是區網的系統。
#### 3.2.3 Available, Partition Toleran
如果沒有一致性的要求，可以對每個請求都返回初始值v0。除此之外，也可以提供弱一致性到此類系統的設定中，如web cache。

## 4. Partially Synchronous Networks
### 4.1 Partially Synchronous Model
在3.1提出的定理中指出在純異步網路中無法保證線性一致性，但在現實生活中，大多數網路並非純異步，因此作者轉向討論部分同步模型來規避這個定理。在部分同步模型中，**每個節點都有一個時鐘**，所有時鐘以相同的速率運行，但這些時鐘不需要完全同步，可能在同一時刻顯示不同的時間，可作為本地計時器使用，讓process能夠測量時間並相應地安排事件。而對於每條訊息，系統假設它要麼在一個已知的時間內被送達（$t_{msg}$），不然就會被認為lost，每個節點在一個已知的時間內處理接收到的消息（$t_{local}$），且這個處理過程不消耗時間。

通過上述方式，作者提出了一種通過引入時鐘和對消息傳遞及處理時間進行明確假設的方法，來實現在分布式系統中維持部分同步，從而可能規避在純異步系統中遇到的一些一致性保證問題。這種方法強調了在設計分布式系統時考慮實際網路條件的重要性。
### 4.2 Impossibility Result
**在部分同步模型下，沒有一個算法能夠在所有情況下（包括消息丟失的情況）同時保證數據的可用性和線性一致性，** 與定理1的結論一致。證明這個定理的方法與先前的定理1證明方法相似。通過將網路分為兩部分來展示，即使在所有消息最終都被送達的情況下，如果網路中的消息可能丟失，那麼仍然無法保證可用性及線性一致性。
### 4.3 Solutions in the Partially Synchronous Model
部分同步模型中雖然與定理1結論一致，但不適用於類似於推論1.1的情況，因為推論1.1的證明依賴於節點不知道message何時lost。而在部分同步算法中，當一次執行中的所有消息都被傳遞時（沒有分區），它們會返回線性數據；而當消息lost時，則可能返回不一致的（可能是前幾次操作）數據。

這邊將３.2.1的中心化算法新增超時機制，用於處理消息丟失，在所有消息成功送達時能保持數據的線性一致性，但在消息丟失時可能無法維持一致性，只能通過本地節點已知的最佳值來回應client，而這種情況下，可能就會違法線性一致性。
### 4.4 Weaker Consistency Conditions
除了保證在所有訊息都被正確送達的執行中返回的線性是有用的，決定在有訊息丟失或延遲時會發生什麼也是重要的問題，這邊討論一個弱一致性問題，允許出現分區時會回應之前的資料，但對這些資料的時效性有一定的要求，例如在一個線性執行中，我們會定義讀和寫的排序，然後要求如果一個操作在另一個操作結束後開始，那前者在部分排序中不應該早於後者，**概念和最終一致性的概念差不多**，定義如下：

中央節點**透過sequence number來決定寫資料的順序**，如果執行中所有訊息都被送達，算法保證線性，因為中央節點將請求序列化並維護部分排序，在無訊息丟失的時間間隔後，所有節點將被通知到新的值，使得任何後來的操作都不會早於這次寫操作，對於讀資料，也是一樣，任何後來的操作都不會早於在無訊息丟失的時間間隔後的讀操作，讀取一定是一連串順序寫入的某一時刻的值。

## 5. Conclusion
在分布式系統中，要實現一致性、可用性和分區容忍性這三者的完美平衡是不可能的，特別是在沒有同步時鐘的異步系統中。但是通過部分同步模型，我們可以在一致性和可用性之間找到實際運作的平衡點。