Leslie Lamport viết Paxos thành chuyện nghị viện Hy Lạp đã biến mất. Ba người phản biện: “không quan trọng lắm”

13/10/2026 · VietTechies · Biên tập

Năm 1990, Leslie Lamport gửi tới tạp chí ACM Transactions on Computer Systems một bài báo trình bày Paxos dưới dạng câu chuyện về nghị viện trên một hòn đảo Hy Lạp cổ đại. Paxos là thuật toán ông nghĩ ra để giữ cho một nhóm máy tính thống nhất với nhau khi một số máy trong nhóm bị sập.

Theo lời Lamport kể, cả ba người phản biện đều thấy bài báo “có phần thú vị, dù không quan trọng lắm”, và nói rằng phải bỏ đi “toàn bộ chuyện Paxos”.

Lamport “khá bực mình khi thấy ai làm trong ngành này cũng có vẻ thiếu óc hài hước đến thế”. Vậy là ông “chẳng làm gì với bài báo”.

Tạp chí đăng bài báo vào tháng 5 năm 1998, tám năm sau ngày ông gửi đi.

Lamport chọn bối cảnh Hy Lạp là có tính toán. Trước đó, ông đã dùng câu chuyện về các vị tướng Byzantine để phổ biến bài toán đồng thuận, tức câu hỏi làm sao để những máy tính không đáng tin cậy thống nhất được với nhau về bất cứ điều gì. Lấy cảm hứng từ thành công ấy, ông biến thuật toán mới thành chuyện về nghị viện trên một hòn đảo mà Leo Guibas gợi ý đặt tên là Paxos. Theo lời ông giải thích, viết về một nền văn minh đã biến mất giúp ông “lược bỏ những chi tiết không thú vị”. Trong vài buổi thuyết trình, ông thậm chí còn hóa thân thành một nhà khảo cổ kiểu Indiana Jones, “có đủ cả mũ Stetson lẫn bình rượu bỏ túi”.

Theo đánh giá của chính Lamport, lối hài hước ấy là “một thất bại thảm hại”. “Những người dự buổi thuyết trình của tôi nhớ Indiana Jones, nhưng không nhớ thuật toán”, ông viết.

Lamport viết rằng trong số những người nhận được bài báo “và tự nhận là đã đọc” có ba chuyên gia trong ngành: Nancy Lynch, Vassos Hadzilacos và Phil Bernstein. Vài tháng sau, ông gửi email hỏi họ một câu: “Liệu bạn có thể xây dựng một cơ sở dữ liệu phân tán không mất tính nhất quán dù bao nhiêu tiến trình của nó gặp sự cố (có thể là tất cả), và sẽ hoạt động bình thường trở lại khi hơn một nửa số tiến trình chạy tốt như cũ không?”

“Không ai trong số họ nhận ra câu hỏi này có liên hệ gì với thuật toán Paxos.”

Paxos ngăn các server chọn hai giá trị khác nhau như thế nào

Bỏ chuyện nghị sĩ sang một bên, Paxos giải bài toán đồng thuận: một nhóm server, trong đó một số máy có thể bị sập hoặc trả lời chậm, phải cùng chốt một giá trị duy nhất, chẳng hạn như máy nào giữ vai trò điều phối. Trong bài “Paxos Made Simple” (2001), Lamport trình bày cơ chế này bằng lời lẽ dễ hiểu.

Mỗi đề xuất mang một số hiệu riêng, không trùng với đề xuất nào khác. Lamport gọi các server có quyền bỏ phiếu là bên chấp nhận (acceptor). Một giá trị được chọn khi đa số acceptor đã chấp nhận cùng một đề xuất mang giá trị đó.
Trước tiên, bên đề xuất (proposer) gửi một yêu cầu chuẩn bị (prepare) kèm số hiệu của mình. Acceptor nào trả lời thì hứa sẽ không chấp nhận bất kỳ đề xuất nào có số hiệu thấp hơn, đồng thời báo lại đề xuất có số hiệu cao nhất mà mình đã chấp nhận, nếu có.
Nếu có acceptor nào báo lại một đề xuất mình đã chấp nhận, proposer phải dùng lại giá trị của đề xuất có số hiệu cao nhất trong số các đề xuất được báo về, thay cho giá trị của chính mình. Như vậy, proposer đến sau sẽ kế thừa một giá trị có thể đã được chọn, chứ không ghi đè lên giá trị đó.

Mấu chốt nằm ở phần chồng lấn: “hai nhóm đa số bất kỳ đều có chung ít nhất một acceptor”. Vì thế, một khi giá trị đã được chọn, bất kỳ nhóm đa số nào trả lời một proposer đến sau cũng đều có ít nhất một acceptor đã chấp nhận giá trị đó. Đó chính là cách Paxos giữ được tính nhất quán khi một proposer bị sập giữa chừng và một proposer khác vào thay.

Những đồng nghiệp của Lamport cần đến Paxos thì đọc chuyện ngụ ngôn Hy Lạp không chút khó khăn

Lamport làm việc tại Trung tâm Nghiên cứu Hệ thống của Digital Equipment Corporation, và một số đồng nghiệp ở đó đọc chính bài viết về Paxos ấy mà không thấy vướng mắc gì. Lúc đó, Chandu Thekkath và Ed Lee đang xây dựng một hệ thống phân tán tên là Petal và cần một giao thức commit để các thao tác vẫn hoàn tất đúng khi có server gặp sự cố. Trước đó, họ thấy giao thức commit ba pha “hơi khó hiểu” và đã bỏ ý định triển khai giao thức này.

Lamport đưa cho Lee một bản báo cáo kỹ thuật về Paxos. Về sau, Thekkath viết rằng mình “đặc biệt thích chất hài hước trong đó”. “Paxos có đủ mọi đặc tính cần thiết mà chúng tôi muốn cho hệ thống của mình, và chúng tôi nghĩ mình có thể triển khai được”, Thekkath nhớ lại. “Một năm sau, khi cần một server khóa phân tán cho hệ thống tệp Frangipani, chúng tôi lại dùng Paxos.”

Lamport viết rằng Butler Lampson “hiểu ngay tầm quan trọng của thuật toán” và đã khiến Nancy Lynch, một trong ba người từng không nhận ra mối liên hệ kia, quan tâm đến Paxos.

Sau khi Lynch, Lampson và Roberto De Prisco công bố bản đặc tả và chứng minh của riêng họ, Lamport đề nghị Ken Birman, khi đó là biên tập viên của tạp chí, cho đăng bài báo. Birman gợi ý sửa lại bài. Lamport cho rằng phần mô tả và chứng minh thuật toán trong bài đã “đủ chính xác và chặt chẽ”, nên thay vì sửa, ông đề xuất một lối tắt: đăng bài dưới dạng “một bản thảo vừa được phát hiện lại, kèm chú giải của Keith Marzullo”. Nhờ vậy, trò đùa được kéo dài thêm, và theo lời Lamport, ông cũng đỡ mất công.

Một số bản kể lại đã rút gọn sự việc năm 1990 thành một lần bị từ chối đơn thuần. Một bài chân dung trên Brandeis Magazine năm 2017 viết rằng tạp chí “đã từ chối bài báo vì cho là không có gì đáng kể” và về sau “đã xem xét lại quyết định của mình”. Còn theo lời kể của Lamport, những người phản biện muốn bỏ phần chuyện Hy Lạp, ông chọn không sửa bài, và chính ông là người đưa bài báo trở lại.

Đơn giản với Lamport, khó với nhiều kỹ sư

Tại một hội nghị năm 2001, Lamport “phát mệt vì ai cũng nói thuật toán Paxos khó hiểu đến thế nào”. Theo ông, người ta “quá sa lầy vào những cái tên nhại tiếng Hy Lạp” đến mức thấy bài báo khó đọc. Toàn bộ phần tóm tắt của “Paxos Made Simple”, bài báo ông viết để đáp lại, chỉ vỏn vẹn một câu: “Trình bày bằng tiếng Anh giản dị thì thuật toán Paxos rất đơn giản.”

Một số người khác lại thấy Paxos khó ngay cả khi không có cái tên Hy Lạp nào. Chubby, dịch vụ khóa mà Google mô tả trong một bài báo năm 2006, đã dùng chính thuật toán “không quan trọng lắm” ấy để các bản sao (replica) trong hệ thống đạt được đồng thuận. Trong “Paxos Made Live” (2007), ba kỹ sư Google nhận xét rằng có thể mô tả Paxos bằng một trang mã giả, trong khi bản triển khai hoàn chỉnh của họ dài tới vài nghìn dòng C++. Năm 2014, Diego Ongaro và John Ousterhout giới thiệu Raft, một thuật toán thay thế được thiết kế với mục tiêu dễ hiểu, vì “Paxos khá khó hiểu”. Trong nghiên cứu của hai tác giả, 33 trên 43 sinh viên trả lời các câu hỏi về Raft tốt hơn các câu hỏi về Paxos.

Phép thử cho tài liệu thiết kế, và giới hạn của lời văn giản dị

Phần hữu ích nhất của câu chuyện là bức email của Lamport. Bức email ấy nêu lại bài toán bằng lời lẽ thông thường, không có hòn đảo nào, cũng chẳng có nghị sĩ nào. Ba người từng nói đã đọc bài báo vẫn không nối được câu hỏi ấy với nội dung bài.

Đó là phép thử mà kỹ sư nào cũng có thể đem về dùng. Trước khi dựa vào một tài liệu thiết kế, hãy đặt cho một người đã đọc nó một câu hỏi mà tài liệu có lời đáp, nhưng diễn đạt bằng những từ không hề xuất hiện trong đó. Nếu người ấy không nối được câu hỏi với tài liệu, hãy nghi ngờ cách trình bày trước, dù nó khéo léo đến đâu, rồi hẵng trách người đọc.

Lời văn giản dị cũng có giới hạn. Năm 2015, Michael Deardeuff ở Amazon báo với Lamport rằng một câu trong “Paxos Made Simple” mang nghĩa mơ hồ. Nếu hiểu sai, câu đó sẽ dẫn đến một thuật toán sai, và Deardeuff đã tìm thấy chính thuật toán ấy trong một số bản triển khai Paxos trên GitHub. Lamport không chịu sửa câu ấy cho hết mơ hồ, cũng không cho biết đó là câu nào. Thay vào đó, ghi chú của ông khuyên những người triển khai đừng dựa vào phần văn xuôi mà hãy tìm đến một bản mô tả chính xác: “Văn xuôi không phải là cách để mô tả chính xác thuật toán.”

Bài liên quan

Đọc bằng ngôn ngữ khác: English