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.[1]

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.[1]

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

[sửa | sửa mã nguồn]

Xác nhận nguyên tử

[sửa | sửa mã nguồn]

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

[sửa | sửa mã nguồ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ị , thì mọi quá trình chính xác sẽ quyết định .
  • 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ị , thì 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 , thì mọi quá trình chính xác sẽ quyết định .

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

Tham khảo

[sửa | sửa mã nguồn]
  1. ^ a b Lynch, Nancy (1996). Distributed Algorithms. San Francisco, CA: Morgan Kaufmann Publishers. ISBN 978-1-55860-348-6.
Chúng tôi bán
Bài viết liên quan
Hướng dẫn build Albedo - Genshin Impact
Hướng dẫn build Albedo - Genshin Impact
Làm SP DPS ngon, build Dmg theo Hoa Khoảnh Khắc (DEF) không cần vũ khí 5 sao mới mạnh
HCTVPG #11 - Làm thế nào để hài hước một cách thông minh
HCTVPG #11 - Làm thế nào để hài hước một cách thông minh
Thật kỳ lạ khi một số nhà sư phát triển khiếu hài trong một điều kiện kỷ luật khắc nghiệt, thiếu thốn Internet và meme
Giới thiệu nhân vật Evileye trong Overlord
Giới thiệu nhân vật Evileye trong Overlord
Keno Fasris Invern, trước đây được gọi là Chúa tể ma cà rồng huyền thoại, Landfall, và hiện được gọi là Evileye, là một nhà thám hiểm được xếp hạng adamantite và người làm phép thuật của Blue Roses cũng như là bạn đồng hành cũ của Mười Ba Anh hùng.
Review sách: Dám bị ghét
Review sách: Dám bị ghét
Ngay khi đọc được tiêu đề cuốn sách tôi đã tin cuốn sách này dành cho bản thân mình. Tôi đã nghĩ nó giúp mình hiểu hơn về bản thân và có thể giúp mình vượt qua sự sợ hãi bị ghét