Thuật toán phân tán

Thuật toán phân tán là một thuật toán được thiết kế để chạy trên phần cứng máy tính được xây dựng từ các bộ vi xử lý kết nối. Các thuật toán phân tán được sử dụng trong nhiều lĩnh vực ứng dụng khác nhau của điện toán phân tán, chẳng hạn như viễn thông, khoa học tính toán, xử lý thông tin phân tán, và điều khiển quá trình thời gian thực. Các vấn đề tiêu chuẩn được giải quyết bằng các thuật toán phân tán bao gồm bầu cử lãnh đạo, sự đồng thuận, giải thuật tìm kiếm, cây bao trùm, loại trừ lẫn nhau và phân bổ nguồn lực.

Thuật toán phân tán là một loại phụ của thuật toán song song, thường được thực hiện đồng thời, với các phần riêng biệt của thuật toán được chạy đồng thời trên các bộ xử lý độc lập và có thông tin hạn chế về những gì các phần khác của thuật toán đang làm. Một trong những thách thức lớn trong việc phát triển và triển khai các thuật toán phân tán là điều phối thành công hành vi của các phần độc lập của thuật toán khi đối mặt với sự thất bại của bộ vi xử lý và liên kết truyền thông không đáng tin cậy. Sự lựa chọn của một thuật toán phân tán phù hợp để giải quyết một vấn đề nhất định phụ thuộc vào cả đặc tính của vấn đề và các đặc tính của hệ thống mà thuật toán sẽ chạy trên như kiểu và xác suất của bộ xử lý hoặc lỗi liên kết, loại liên lạc liên có thể được thực hiện, và mức độ đồng bộ hóa thời gian giữa các quá trình riêng biệt.

Các vấn đề tiêu chuẩn

Xác nhận nguyên tử

Xác nhận nguyên tử là một hoạt động mà một tập hợp các thay đổi khác biệt được áp dụng như một thao tác đơn lẻ. Nếu xác nhận nguyên tử thành công, có nghĩa là tất cả các thay đổi đã được áp dụng. Nếu có một sự thất bại trước khi xác nhận nguyên tử có thể được hoàn thành, "xác nhận" bị hủy bỏ và không có thay đổi sẽ được áp dụng. Các thuật toán để giải quyết giao thức cam kết nguyên tử bao gồm giao thức xác nhận hai pha và giao thức xác nhận ba pha.

Đồng thuận

Các thuật toán đồng thuận cố gắng giải quyết vấn đề của một số quy trình đồng thuận về một quyết định chung. Cụ thể hơn, một giao thức đồng thuận phải đáp ứng bốn tính chất chính thức dưới đây.

• Chấm dứt: mỗi quá trình chính xác định rõ ràng định một số giá trị.
• Hiệu lực: nếu tất cả các quy trình đề xuất cùng một giá trị $v$, thì mọi quá trình chính xác sẽ quyết định $v$.
• Tính toàn vẹn: mọi quá trình chính xác định rõ ràng định nhiều nhất một giá trị và nếu nó quyết định một số giá trị $v$, thì $v$ phải được đề xuất bởi một số quy trình.
• Thoả thuận: nếu một quy trình chính xác định rõ ràng định $v$, thì mọi quá trình chính xác sẽ quyết định $v$.

Một thuật toán điển hình để giải quyết sự đồng thuận là thuật toán paxos.