Đồng hồ logic và đồng hồ vật lý

Đồng hồ logic sắp xếp các sự kiện theo quan hệ nhân quả mà không tham chiếu đến thời gian thực, trong khi đồng hồ vật lý đồng bộ hóa các đồng hồ thời gian thực của các máy riêng biệt để chúng gần nhau mặc dù có sự trôi lệch.

Definition

Đồng hồ logic gán cho mỗi sự kiện một dấu thời gian số nguyên đơn điệu dọc theo mỗi tiến trình và tăng lên qua giao tiếp, nắm bắt thứ tự nhân quả; đồng bộ hóa đồng hồ vật lý là quá trình điều chỉnh đồng hồ phần cứng của các máy để chúng hiển thị cùng một thời gian thực xấp xỉ.

Scope

Chủ đề này bao gồm đồng hồ logic (vô hướng) của Lamport và mối quan hệ "xảy ra trước" mà chúng tuân thủ, việc xây dựng một thứ tự tổng thể từ các dấu thời gian logic, và đồng bộ hóa đồng hồ vật lý—giới hạn sự trôi lệch, trao đổi dấu thời gian để ước tính độ lệch, và các thuật toán (phương pháp của Cristian, thuật toán Berkeley, NTP) được sử dụng trong thực tế. Nó đối chiếu khi nào thời gian logic nhân quả là đủ và khi nào thời gian thực sự cần thiết.

Core questions

• Làm thế nào có thể gán dấu thời gian để chúng tuân thủ mối quan hệ nhân quả "xảy ra trước"?
• Làm thế nào để xây dựng một thứ tự tổng thể nhất quán trên các sự kiện từ đồng hồ logic?
• Đồng hồ vật lý có thể được đồng bộ hóa chặt chẽ đến mức nào khi có sự chậm trễ mạng và trôi lệch biến đổi?

Key theories

Đồng hồ logic Lamport

Mỗi tiến trình giữ một bộ đếm được tăng lên ở mỗi sự kiện và được mang theo tin nhắn; các dấu thời gian thu được tuân thủ mối quan hệ "xảy ra trước", và các trường hợp trùng lặp được giải quyết bằng định danh tiến trình tạo ra một thứ tự tổng thể nhất quán với quan hệ nhân quả.

Đồng bộ hóa xác suất và khứ hồi

Phương pháp của Cristian ước tính đồng hồ từ xa bằng cách đo thời gian khứ hồi và giả định độ trễ đối xứng, cung cấp các giới hạn xác suất về lỗi đồng bộ hóa có thể đạt được qua mạng.

Giao thức Thời gian Mạng (NTP)

NTP tổ chức các máy chủ thời gian thành một hệ thống phân cấp theo tầng và sử dụng bộ lọc thống kê các phép đo độ lệch lặp lại để điều chỉnh đồng hồ trên internet trong vòng vài mili giây.

Clinical relevance

Đồng hồ logic sắp xếp các hoạt động trong các kho dữ liệu sao chép và hàng đợi tin nhắn mà không cần tin cậy vào thời gian đồng hồ treo tường, trong khi đồng bộ hóa vật lý là nền tảng của các cơ sở dữ liệu được sắp xếp theo dấu thời gian, theo dõi phân tán và các giao thức bảo mật phụ thuộc vào lỗi đồng hồ có giới hạn.

History

Bài báo về đồng hồ logic năm 1978 của Lamport đã định nghĩa lại thời gian trong các hệ thống phân tán như một khái niệm nhân quả hơn là vật lý; song song đó, Cristian và những người khác đã phát triển đồng bộ hóa xác suất, và NTP của Mills đã trở thành cơ chế tiêu chuẩn để giữ cho các đồng hồ internet được căn chỉnh.

Debates

Thời gian logic so với thời gian vật lý để sắp xếp các hoạt động

Đồng hồ logic đảm bảo tính đúng đắn nhân quả mà không cần tin cậy vào đồng hồ phần cứng, nhưng không thể liên hệ các sự kiện với thời gian thực; đồng hồ vật lý cho phép suy luận thời gian thực với rủi ro sắp xếp sai khi sự trôi lệch vượt quá độ trễ tin nhắn, thúc đẩy các phương pháp lai.

Key figures

• Leslie Lamport
• Flaviu Cristian
• David Mills

Seminal works

• lamport1978
• mills1991
• cristian1989

Frequently asked questions

Nếu a có dấu thời gian Lamport nhỏ hơn b, thì a có xảy ra trước b không?

Không nhất thiết—dấu thời gian nhỏ hơn là nhất quán với "xảy ra trước" nhưng không ngụ ý điều đó, vì các sự kiện đồng thời có thể nhận được dấu thời gian có thứ tự. Để xác định chính xác quan hệ nhân quả, bạn cần đồng hồ vector, không phải đồng hồ logic vô hướng.