Thời gian và Trạng thái Toàn cục
Thời gian và trạng thái toàn cục đề cập đến cách một hệ thống phân tán sắp xếp các sự kiện và suy luận về điều kiện tập thể của nó khi không có đồng hồ chia sẻ và không có cái nhìn toàn cục tức thời.
Definition
Trong một hệ thống phân tán, các sự kiện xảy ra tại các tiến trình riêng biệt mà không có đồng hồ chia sẻ; nghiên cứu về thời gian và trạng thái toàn cục cung cấp các quan hệ và thuật toán—đồng hồ logic và vector, ảnh chụp nhanh, và phân phối có thứ tự—cho phép hệ thống sắp xếp các sự kiện theo quan hệ nhân quả và nắm bắt các trạng thái toàn cục nhất quán.
Scope
Lĩnh vực này bao gồm đồng hồ logic và quan hệ xảy ra trước (happened-before), đồng bộ hóa đồng hồ vật lý, đồng hồ vector và việc phát hiện quan hệ nhân quả và đồng thời, việc xác định các ảnh chụp nhanh toàn cục nhất quán, và các đảm bảo về thứ tự (FIFO, nhân quả, tổng thể) cần thiết cho multicast đáng tin cậy. Cùng với nhau, những công cụ này cho phép các hệ thống phân tán đưa ra các tuyên bố có ý nghĩa về 'thời điểm' và 'trạng thái nào' bất chấp sự vắng mặt của một đồng hồ toàn cục.
Sub-topics
Core questions
- Làm thế nào các sự kiện tại các tiến trình khác nhau có thể được sắp xếp mà không có đồng hồ vật lý chia sẻ?
- Làm thế nào một tiến trình có thể xác định liệu hai sự kiện có liên quan nhân quả hay đồng thời?
- Làm thế nào một ảnh chụp nhanh toàn cục nhất quán có thể được ghi lại trong khi tính toán vẫn tiếp tục?
- Những đảm bảo về thứ tự nào đối với việc phân phối thông điệp là cần thiết để bảo toàn quan hệ nhân quả?
Key theories
- Quan hệ xảy ra trước và đồng hồ logic
- Quan hệ xảy ra trước của Lamport định nghĩa một thứ tự nhân quả từng phần trên các sự kiện, và đồng hồ logic (vô hướng) gán các dấu thời gian nhất quán với nó, cung cấp một khái niệm về thứ tự không cần đồng hồ đủ để xây dựng một thứ tự tổng thể cho nhiều giao thức.
- Đồng hồ vector và quan hệ nhân quả
- Đồng hồ vector mở rộng đồng hồ logic sao cho việc so sánh hai dấu thời gian nắm bắt chính xác liệu một sự kiện có xảy ra trước một sự kiện khác theo quan hệ nhân quả hay liệu hai sự kiện đó có đồng thời, cho phép theo dõi quan hệ nhân quả một cách chính xác.
- Ảnh chụp nhanh toàn cục nhất quán
- Thuật toán ảnh chụp nhanh Chandy-Lamport ghi lại một trạng thái toàn cục nhất quán—trạng thái tiến trình cộng với các thông điệp đang truyền—mà không làm dừng hệ thống, bằng cách truyền các dấu hiệu (markers) dọc theo các kênh.
Clinical relevance
Đồng hồ logic và vector là nền tảng cho tính nhất quán nhân quả, phát hiện xung đột trong các kho lưu trữ được sao chép, và gỡ lỗi các thực thi phân tán; các ảnh chụp nhanh nhất quán là nền tảng cho việc kiểm tra phân tán, phát hiện tắc nghẽn và kết thúc, và phục hồi lỗi xử lý luồng.
History
Bài báo năm 1978 của Lamport đã giới thiệu thời gian logic và quan hệ xảy ra trước, một trong những kết quả được trích dẫn nhiều nhất trong khoa học máy tính; Chandy và Lamport đã chính thức hóa các ảnh chụp nhanh toàn cục nhất quán vào năm 1985; và Fidge cùng Mattern đã độc lập phát triển đồng hồ vector vào cuối những năm 1980, hoàn thiện bộ công cụ nền tảng để suy luận về thời gian và trạng thái.
Key figures
- Leslie Lamport
- K. Mani Chandy
- Colin Fidge
- Friedemann Mattern
Related topics
Seminal works
- lamport1978
- chandy1985
- fidge1988
Frequently asked questions
- Tại sao các hệ thống phân tán không thể chỉ sử dụng đồng hồ vật lý được đồng bộ hóa?
- Đồng hồ vật lý bị trôi và không thể được đồng bộ hóa hoàn hảo trên một mạng có độ trễ thay đổi, do đó thứ tự thời gian thực của hai sự kiện có thể không rõ ràng. Thay vào đó, đồng hồ logic và vector nắm bắt thứ tự nhân quả thực sự quan trọng đối với tính đúng đắn.
- Điều gì làm cho một ảnh chụp nhanh toàn cục 'nhất quán'?
- Một ảnh chụp nhanh là nhất quán nếu, bất cứ khi nào nó bao gồm việc nhận một thông điệp, nó cũng bao gồm việc gửi thông điệp đó. Một trạng thái như vậy có thể đã xảy ra trong quá trình thực thi, mặc dù không có một khoảnh khắc nào được quan sát toàn cục.