# 芭芭拉·利斯科夫 (Barbara Lisko）
----------------
## 人物相關介紹
美國計算機科學家，為編譯語言和分佈式計算做出傑出貢獻。1961年在加州大學伯克利分校學習數學學士學位，輔修物理學。1968年在斯坦福大學獲得計算機科學的博士學位。
## 相關認可和得到獎項
芭芭拉是美國國家工程院院士、國家科學院院士、美國藝術與科學院院士、美國計算機協會（ACM）會員。2002年被MIT最優秀女教師之一，02年discover雜志把芭芭拉評爲科學界最重要的50女性之一。 04年因對編程語言、編程方法論和分佈式系統的根本性貢獻榮獲“John von Neumann Medal”。05年11月19日被授予ETH榮譽博士.2011年和2017年分別被盧加諾大學和我馬德里理工大學授予榮譽博士學位。
**09年 因其在編程語言和軟件方法論設計方面的工作榮獲 2008年 ACM頒發的圖靈獎**
## 相關論文
> 通過自己進行閲讀和參考 部分論壇講解論文
### Practical Byzantine Fault Tolerance
> https://pmg.csail.mit.edu/papers/osdi99.pdf
這篇論文討論了對於replication算法解決拜占庭容錯算法。拜占庭算法又叫拜占庭將軍。討論與是允許在少數節點作惡（消息存在被僞造的風險）場景下如何達成共識問題。論文提出解決拜占庭容錯的狀態機副本複製的算法。這個算法在保證活性和安全性的前提下提供（n-1）/3的容錯性。從Lamport教授在1982年提出拜占庭問題開始，有一堆算法去進行解決。PBFT在此之上提出優化使得優化使得能夠應用在實際場景，在只讀操作中使用一次消息往返，在只寫操作中只是用2次消息往返，并且在正常操作中是使用了消息驗證編碼，簡稱MAC。
論文做出貢獻：
1. 首次提出在異步網絡環境下使用狀態機副本協議
2. 使用多優化性能顯著提升
3. 實現了一種拜占庭容錯的分佈文件系統
4. 為副本複製的性能損耗提供實驗數據支持
### 系統模型
系統假設為異步分佈式的，通過網絡傳輸的消息可能丟失、延遲、重複或者亂序。作者假設節點失效必須是獨立發生的，也就是說代碼、OS和管理員密碼這些東西在各個節點是不同的。
這篇論文中使用了加密技術來防止欺騙攻擊和重播攻擊，以及檢測被破壞的消息。消息包括公鑰也就是RSA算法、消息驗證編碼(mac)和無碰撞哈希函數生成的信息摘要。
系統攻擊者可以操縱多個失效節點、延遲通信甚至延遲正確的節點。但不能無限期延遲正確的節點，且算力有限不能破解加密算法。
### 算法
PBFT 是一種狀態機副本複製算法，即服務作爲狀態機進行建模， 狀態機在分布式系統不同的節點進行副本複製。將所有的副本組成的集合使用大寫字母R表示，使用0到R|-1的整數表示每一個副本。
所有副本在一個被稱爲視圖的輪換過程中運作。在某個視圖中一個副本作爲主節點，其他副本作爲備份。試圖是連續編號的整數。主節點由公式p=v mod |R|計算得到， 這邊v是視圖編號，p是副本編號。|R|是副本集合的個數。當主節點失效的時候就需要啓動試圖更換過程。Viewstamped Replication 算法和Paxos算法就是使用類似方法解決良性容錯率。
#### PBET算法:
* 客戶端向主節點發生請求調用服務操作
* 主節點通過廣播將請求放送給其他副本
* 所有副本都執行請求并將結果發回客戶端
* 客戶端需要等待f-1不同副本節點發回相同結果作爲整個 操作的最終結果
#### PBET 提出了對每個副本節點的兩個限定要求
1. 所有節點必須是確定性。換而言之，在給定狀態和參數相同的情況下，操作執行結果必須相同
2. 所有節點必須從相同的狀態開始執行。
## 客戶端
客戶端c向主節點發送<REQUEST,o,t,c>請求執行狀態機操作o,這邊的時間戳t用來保證客戶端請求只會執行一次。客戶端c 發出請求的是時間戳是全序排列的。
每個由副本節點發給客戶端的消息都包含了當前視圖編號，是客戶端可以跟蹤視圖編號，客戶端都過點對點向它認爲為主節點發送請求，再由主節點自動將該請求向所有備份節點進行廣播。
## PBET 算法流程
### 相關程序
> 由Chatgpt進行編寫
```
from collections import defaultdict
# PBFT configuration
n = 4 # Number of backup nodes
f = 1 # Maximum tolerated malicious nodes
# Dictionary to store the state of backup nodes
states = defaultdict(lambda: {"pre-prepare": None, "prepare": 0, "commit": 0})
# Simulated network communication between nodes
def send_message(sender, receiver, message):
# Simulate sending a message from sender to receiver
print(f"Node {sender} sends to Node {receiver}: {message}")
# In a real implementation, you'd use a network protocol to send messages.
def pre_prepare(node, request):
# Create a Pre-Prepare message in the prepare phase
states[node]["pre-prepare"] = request
for i in range(1, n):
if i != node:
send_message(node, i, f"Pre-Prepare: {request}")
def prepare(node):
# Create a Prepare message once Pre-Prepare is confirmed by a majority
states[node]["prepare"] += 1
for i in range(1, n):
if i != node and states[i]["pre-prepare"] == states[node]["pre-prepare"]:
send_message(node, i, f"Prepare: {states[node]['pre-prepare']}")
def commit(node):
# Create a Commit message once Prepare is confirmed by a majority
states[node]["commit"] += 1
for i in range(1, n):
if i != node and states[i]["pre-prepare"] == states[node]["pre-prepare"]:
send_message(node, i, f"Commit: {states[node]['pre-prepare']}")
def execute(request):
# Execute the request
print("Executing request:", request)
def pbft(request):
# Client sends a request to the primary node (Node 0)
primary_node = 0
pre_prepare(primary_node, request)
# Primary node broadcasts the request to other backup nodes
for node in range(1, n):
pre_prepare(node, request)
# Backup nodes process messages
for node in range(1, n):
if states[node]["pre-prepare"] == request:
prepare(node)
for node in range(1, n):
if states[node]["pre-prepare"] == request and states[node]["prepare"] >= 2 * f:
commit(node)
for node in range(1, n):
if states[node]["pre-prepare"] == request and states[node]["commit"] >= 2 * f:
execute(request)
request = "Client's request content"
pbft(request)
```
##### 想要更詳細瞭解PBFT 的相關程式碼 可以參考 https://github.com/bigpicturelabs/simple_pbft
Sign in with Wallet
Connect another wallet