Consensus

Là bài toán kinh điển của mạng phân tán, khi các node/process cần đạt sự đồng thuận về trạng thái tiếp theo của hệ thống, với trạng thái đầu vào giống hệt nhau. Các ứng dụng điển hình của consensus như:

• Đồng thuận về việc commit hay abort transaction vào distributed database
• Leader election
• Điều khiển UAV (máy bay không người lái)
• Clock synchronization
• Pagerank
• Load balancing
• Blockchain

Mô tả vấn đề

Bài toán consensus giải quyết sự đồng thuận giữa các node/processor trong mạng phân tán, với khả năng chịu lỗi xảy ra (fault-tolerance) hoặc ở processor hoặc ở mạng truyền tin. Bài toán consensus là bài toán kinh điển luôn xuất hiện trong các hệ thống phân tán có nhiều tác nhân tham gia. Cách tiếp cận tự nhiên để đạt được sự đồng thuận là toàn bộ processor phải đồng ý 1 giá trị được số đông chấp nhận, ít nhất là quá bán (50%+1). Tuy nhiên, cách tiếp cận này luôn gặp vấn đề khi các processor lỗi có thể luôn cản trở việc đạt được đồng thuận hoặc không bao giờ đạt được đồng thuận. Do đó, bài toán đồng thuận luôn có giới hạn ở số lượng maximum các processor lỗi.

Có 3 điều kiện luôn được đặt ra trong bài toán consensus:

Termination (điều kiện kết thúc quá trình đồng thuận) các processor hoạt động đúng sẽ dần dần đưa ra giá trị quyết định.

Integrity (tính toàn vẹn / đồng bộ của quá trình đồng thuận) nếu tất cả processor hoạt động đúng đều đề xuất giá trị v, thì bất kì processor hoạt động đúng nào đều phải đồng ý giá trị v là quyết định.

Agreement (luật bất biến của quá trình đồng thuận) mọi processor hoạt động đúng đều phải đồng ý trên cùng 1 giá trị.

Điều kiện integrity có nhiều biến thể phụ thuộc từng thuật toán và mục đích sử dụng consensus. Ví dụ 1 integrity yếu hơn là giá trị quyết định có thể được chọn bởi 1 nhóm các processor hoạt động đúng thay vì tất cả.

Một chút lịch sử

Bài toán consensus lần đầu được đề cập vào năm 1978 bởi Robert Shostak với công bố về “Interactive consistency problem” khi ông làm việc ở dự án SIFT (Software Implemented Fault Tolerance) tại Computer Science lab ở SRI International (được NASA tài trợ). Lúc công bố, Shostak chứng minh được cần tối thiểu 3n+1 processor trong mạng để bài toán consensus có thể chạy được với n=1 processor bị lỗi. Sau này Leslie Lamport đặt lại bài toán 1 cách tổng quát hơn và chứng minh được cho trường hợp n>1.

Consensus trong môi trường mạng đồng bộ

Trong mạng đồng bộ, quá trình consensus được thực hiện theo từng round, đợi hết round này mới tới round kia.

Consensus trong trường hợp truyền tin bị lỗi (link failure)

Bài toán consensus xuất hiện trong rất nhiều ứng dụng phân tán. Ví dụ: các processes cần thống nhất liệu nên commit hay abort một transaction trong distributed database. Vấn đề consensus điển hình và mang tính fundamental được gọi tên là “coordinated attack problem” - là khi đặt vào tình huống messages có thể mất.

Mô tả bài toán coordinated attack problem:

Một số vị tướng (process) quyết định lên kế hoạch phối hợp tấn công một vùng đất. Họ hiểu rằng việc tấn công chỉ có thể thành công nếu tất cả cùng tham gia. Vấn đề là họ đóng quân ở nhiều vị trí khác nhau, và phương tiện liên lạc chỉ là truyền miệng. Họ cần phải thống nhất thời điểm cùng đồng loạt tấn công. Các vị tướng ở lân cận nhau có thể giao tiếp với nhau thông qua người truyền tin.

Nếu tất cả người truyền tin đều đáng tin cậy thì toàn bộ vị tướng có thể gửi tin lẫn nhau. Như vậy sau 1 vài round truyền tin, họ có thể thống nhất thời điểm tấn công. Tuy nhiên, việc truyền tin luôn có thể bị thất bại => độ khó của bài toán tăng lên.

Bài toán này được chứng minh là có thể giải, với một tỉ lệ xác suất lỗi nhất định (nghĩa là có thể xảy ra trường hợp không thể giải). Và tỉ lệ xác suất lỗi này là không thể tránh khỏi.

Version 1: Deterministic version

Mô hình hoá bài toán: n vị tướng đánh số từ 1,…n. Trạng thái quyết định ban đầu của mỗi vị tướng là 0 (ko tấn công) hoặc 1 (tấn công). Bài toán cân nhắc việc truyền thông tin có thể bị thất bại. Bài toán cần giải là các vị tướng đi tới kết luận cuối cùng.

Agreement: Không có 2 vị tướng nào quyết định hai giá trị khác nhau.

Validity:

• Nếu toàn bộ vị tướng quyết định ko tấn công (0) thì 0 phải là kết quả cuối cùng.
• Nếu toàn bộ vị tướng quyết định tấn công (1), và toàn bộ tin tức truyền đi thông suốt, thì 1 là quyết định cuối cùng.

Termination: Toàn bộ các vị tướng đều phải có quyết định cuối cùng.

Điều kiện Agreement và Termination thì khá chặt chẽ. Còn điều kiện Validity thì có thể có nhiều biến thể. Thực ra điều kiện Validity ở trên là thuộc dạng yếu. Một số biến thể khác, ví dụ 1: nếu 1 vị tướng quyết định ban đầu là 1 thì thuật toán cuối cùng chọn kết quả 1. Ví dụ 2: nếu toàn bộ vị tướng quyết định ban đầu là 1, và chỉ cần 1 bản tin truyền đi bị mất thì thuật toán cho phép dừng với quyết định cuối cùng là 0.

Coi mạng lưới giữa các vị tướng là một đồ thị vô hướng, đường đi của những người truyền tin là cạnh đồ thị. Toán học chứng minh được rằng bài toán không thể giải với bất kì loại đồ thị nào có từ 2 đỉnh trở lên. Nghĩa là luôn xảy ra trường hợp không có lời giải.

<Bỏ qua phần chứng minh về toán>

Version 2: Randomized version

Ở version trên ta đưa ra giả thuyết rằng n vị tướng được sắp xếp quyết định ban đầu (mặc dù ngẫu nhiên), được sắp xếp vị trí và người truyền tin (đồ thị đã xác định). Ở version này, ta đưa thêm một số giả định để tăng tính ngẫu nhiên:

• Cho phép điều kiện agreement vẫn chấp nhận được với 1 tỷ lệ e các vị tướng có kết luận khác nhau.

=> cần đánh giá cận biên min_e <= e <= max_e so với số lần truyền tin (r) cần thiết để bài toán kết thúc.

=> Các tính toán toán học chỉ ra rằng tỷ lệ e này không hề nhỏ so với r. <bỏ qua chứng minh về toán>

Kết quả cuối cùng: 1/(r+1) <= e <= 1/r.

Consensus trong trường hợp process bị lỗi (process failure)

Mô tả bài toán agreement problem

Xem xét trường hợp việc truyền tin không hề bị lỗi (perfectly reliable) mà bản thân các process có thể lỗi. Có 2 trường hợp lỗi: 1) stopping failure - lỗi bị offline 2) byzantine failure - lỗi bị tấn công giả mạo.

Mô hình hoá bài toán: n process kết nối với nhau trong đồ thị. Mỗi process đều kết nối được với các process còn lại. Giả sử có 1 tỷ lệ maximum f process có thể lỗi và các cạnh đồ thị hoạt động không lỗi.

Validity: Nếu tất cả process được khởi tạo cùng giá trị v thì v sẽ là giá trị đồng thuận cuối cùng và duy nhất. Agreement: Chấp nhận hệ thống vẫn hoạt động tiếp mặc dù có một số maximum f process cho ra kết quả khác với phần lớn process còn lại.

Trường hợp stopping failure:

Agreement: Không có 2 process nào quyết định 2 giá trị khác nhau. Validity: như trên. Termination: Toàn bộ non-stop process sẽ dần dần ra quyết định.

Trường hợp byzantine failure:

Giả định chặt chẽ là process byzantine chỉ có thể gây ảnh hưởng bằng 2 việc 1) truyền sai thông tin 2) tự nó chuyển đổi state sai. Byzantine process không thể tác động lên kết quả hay bản tin của các process khác.

Agreement: Không có 2 process lỗi nào quyết định 2 giá trị khác nhau. Validity: Như trên, cho tất cả process không lỗi. Termination: Toàn bộ non-byzantine process sẽ dần dần ra quyết định.

Điểm khác nhau giữa stopping failure và byzantine failure Các process stopping phải chấp nhận kết quả của đám đông, còn các process byzantine thì không thể kiểm soát được.

Thuật toán cho trường hợp stopping failures:

• FloodSet
• EIGStop (Exponential Information Gathering)

Thuật toán cho trường hợp byzantine failures: Toán học chứng minh được bài toán byzantine chỉ có thể có lời giải khi số lượng process (n) phải lớn hơn 3 lần số failure process: n >= 3f + 1

• EIGByz

Cho trường hợp process chỉ cần ra quyết định 0 hoặc 1:

• TurpinCoan
• ConsistentBroadcast
• PolyByz

Một số kết luận chú ý:

• Điều kiện n >= 3f + 1 là bắt buộc cho mọi thuật toán giải quyết bài toán consensus đảm bảo fault tolenrance.
• Số round tối thiểu cần thực hiện cho tới khi đạt được trạng thái đồng thuận là f + 1.
• Kết luận trên áp dụng cho cả hai trường hợp: stopping failure và byzantine failure.