Loại trừ lẫn nhau phân tán và Bầu chọn lãnh đạo

Loại trừ lẫn nhau và bầu chọn lãnh đạo là các vấn đề phối hợp cổ điển: đảm bảo rằng nhiều nhất một tiến trình truy cập một tài nguyên quan trọng và chọn một điều phối viên duy nhất nổi bật trong số các tiến trình ngang hàng.

Definition

Loại trừ lẫn nhau phân tán đảm bảo rằng nhiều nhất một tiến trình tại một thời điểm giữ một tài nguyên chia sẻ trong khi đảm bảo quyền truy cập cuối cùng cho tất cả các yêu cầu; bầu chọn lãnh đạo chọn một cách xác định chính xác một tiến trình làm điều phối viên, với tất cả các tiến trình đồng ý về kết quả.

Scope

Chủ đề này bao gồm các thuật toán loại trừ lẫn nhau dựa trên quyền (thuật toán dấu thời gian của Lamport, Ricart-Agrawala, phương pháp quorum của Maekawa) và các thuật toán dựa trên token, cùng với độ phức tạp thông điệp và các thuộc tính công bằng của chúng; và các thuật toán bầu chọn lãnh đạo cho các vòng (Chang-Roberts) và mạng tổng quát (thuật toán kẻ bắt nạt), bao gồm các giả định của chúng về định danh và đồng bộ hóa. Các nguyên thủy này lặp lại trong suốt các dịch vụ phối hợp và các hệ thống sao chép.

Core questions

• Làm thế nào các tiến trình có thể tuần tự hóa quyền truy cập vào một tài nguyên chia sẻ chỉ bằng cách sử dụng thông điệp?
• Những đánh đổi về độ phức tạp thông điệp và tính công bằng giữa các lược đồ dựa trên quyền và dựa trên token là gì?
• Làm thế nào một lãnh đạo duy nhất được chọn, và làm thế nào việc bầu chọn được kích hoạt lại sau khi lãnh đạo thất bại?

Key theories

Loại trừ lẫn nhau dựa trên quyền

Các thuật toán như Ricart-Agrawala sắp xếp các yêu cầu theo dấu thời gian logic và cấp quyền truy cập khi một người yêu cầu đã nhận được sự cho phép từ tất cả (hoặc một quorum của) các tiến trình ngang hàng, đạt được sự công bằng với chi phí thông điệp giới hạn cho mỗi lần vào phần quan trọng.

Loại trừ lẫn nhau dựa trên token

Một token duy nhất lưu hành hoặc được yêu cầu theo yêu cầu, và chỉ người giữ nó mới có thể vào phần quan trọng, giảm lưu lượng thông điệp nhưng yêu cầu các cơ chế để tạo lại một token bị mất sau khi xảy ra lỗi.

Bầu chọn lãnh đạo

Các thuật toán bầu chọn như Chang-Roberts cho các vòng và thuật toán kẻ bắt nạt cho các mạng tổng quát sử dụng các định danh tiến trình để hội tụ về một điều phối viên có ưu tiên cao nhất mà tất cả các tiến trình chính xác đều nhận ra.

Clinical relevance

Bầu chọn lãnh đạo được gọi bất cứ khi nào một hệ thống sao chép phải chọn một chính hoặc điều phối viên, và khóa phân tán tổng quát hóa loại trừ lẫn nhau; cả hai đều được phơi bày dưới dạng các dịch vụ cốt lõi bởi các hệ thống phối hợp được sử dụng trong toàn bộ cơ sở hạ tầng đám mây.

History

Bài báo về đồng hồ logic năm 1978 của Lamport đã giới thiệu một thuật toán loại trừ lẫn nhau dựa trên dấu thời gian; Ricart và Agrawala đã tối ưu hóa nó vào năm 1981, Maekawa đã giới thiệu các quorum ngay sau đó, và thuật toán kẻ bắt nạt năm 1982 của Garcia-Molina đã chính thức hóa bầu chọn lãnh đạo, mang lại cho lĩnh vực này các thuật toán phối hợp kinh điển.

Key figures

• Leslie Lamport
• Glenn Ricart
• Ashok Agrawala
• Hector Garcia-Molina

Seminal works

• ricart1981
• garcia-molina1982
• lynch1996

Frequently asked questions

Loại trừ lẫn nhau phân tán khác với khóa trên một máy đơn như thế nào?

Không có bộ nhớ chia sẻ hoặc trình quản lý khóa trung tâm để dựa vào, vì vậy các tiến trình phải phối hợp hoàn toàn bằng cách trao đổi thông điệp và phải xử lý rõ ràng độ trễ thông điệp và các lỗi, điều mà một khóa máy đơn có thể coi là đương nhiên.