Các Mô hình Thời gian và Lỗi

Các mô hình thời gian và lỗi quy định những gì một thuật toán phân tán có thể giả định về độ trễ thông điệp và tốc độ bộ xử lý, cũng như cách các thành phần được phép gặp lỗi.

Definition

Một mô hình thời gian cố định các giả định về giới hạn trên của thời gian gửi thông điệp và tốc độ xử lý tương đối, trong khi một mô hình lỗi cố định tập hợp các cách mà các tiến trình và kênh có thể sai lệch so với hành vi được chỉ định của chúng.

Scope

Chủ đề này bao gồm các mô hình thời gian đồng bộ, không đồng bộ và bán đồng bộ; phân loại lỗi từ sự cố (dừng lỗi) qua bỏ sót và thời gian đến các lỗi tùy ý (Byzantine); và sự trừu tượng hóa các bộ phát hiện lỗi bắc cầu giữa các hệ thống không đồng bộ và suy luận dựa trên thời gian chờ. Các mô hình này là các tiên đề mà từ đó cả kết quả khả thi và bất khả thi đều được suy ra.

Core questions

• Những giới hạn nào về độ trễ và tốc độ mà một thuật toán có thể giả định, và thời gian chờ phụ thuộc vào chúng như thế nào?
• Những lớp lỗi nào—sự cố, bỏ sót, thời gian, Byzantine—mà một giao thức phải che giấu?
• Làm thế nào các hệ thống không đồng bộ có thể được tăng cường bằng các bộ phát hiện lỗi để vượt qua các kết quả bất khả thi?

Key theories

Tính đồng bộ một phần

Các hệ thống thực tế không hoàn toàn đồng bộ cũng không hoàn toàn không đồng bộ; mô hình bán đồng bộ giả định các giới hạn về độ trễ và tốc độ cuối cùng sẽ đúng hoặc không xác định, điều này đủ để giải quyết sự đồng thuận trong khi vẫn giữ được tính thực tế.

Hệ thống phân cấp mô hình lỗi

Các lỗi bao gồm từ các sự cố dừng lỗi lành tính, qua các lỗi bỏ sót gửi/nhận và vi phạm thời gian, đến hành vi Byzantine tùy ý; mức độ nghiêm trọng của các lỗi mà một giao thức phải chịu đựng quyết định yếu tố sao chép và độ phức tạp thông điệp cần thiết.

Các bộ phát hiện lỗi không đáng tin cậy

Một bộ phát hiện lỗi trừu tượng cung cấp các gợi ý có thể không chính xác về các tiến trình đã gặp sự cố; việc đặc trưng hóa bộ phát hiện yếu nhất đủ để giải quyết sự đồng thuận dung hòa sự chặt chẽ không đồng bộ với các triển khai dựa trên thời gian chờ thực tế.

Clinical relevance

Các hệ thống sản xuất ngầm chọn một mô hình thời gian và lỗi bất cứ khi nào chúng đặt thời gian chờ, chọn một yếu tố sao chép, hoặc quyết định có nên phòng thủ chống lại những người tham gia độc hại hay không; việc đưa ra các giả định sai là một nguyên nhân gốc rễ phổ biến của các sự cố phân tách não (split-brain) và mất dữ liệu.

History

Sau khi mô hình không đồng bộ được chứng minh là quá yếu đối với sự đồng thuận chịu lỗi, Dwork, Lynch và Stockmeyer đã giới thiệu tính đồng bộ một phần vào năm 1988, và Chandra và Toueg đã chính thức hóa các bộ phát hiện lỗi không đáng tin cậy vào năm 1996, cùng nhau cung cấp các công cụ mô hình hóa giúp đạt được thỏa thuận chịu lỗi thực tế.

Debates

Thời gian chờ là một giả định về thời gian hay một bộ phát hiện lỗi?

Một quan điểm coi thời gian chờ là mã hóa một giới hạn đồng bộ (cuối cùng); một quan điểm khác coi chúng là một triển khai của một bộ phát hiện lỗi trừu tượng. Hai cách diễn giải này phần lớn là tương đương nhưng nhấn mạnh các ranh giới thiết kế khác nhau giữa mô hình mạng và thuật toán.

Key figures

• Cynthia Dwork
• Nancy Lynch
• Larry Stockmeyer
• Tushar Chandra
• Sam Toueg

Seminal works

• dwork1988
• chandra1996
• lynch1996

Frequently asked questions

Tại sao việc phát hiện lỗi đáng tin cậy không thể được triển khai trong một hệ thống hoàn toàn không đồng bộ?

Nếu không có giới hạn về độ trễ thông điệp, một tiến trình chậm tùy ý nhưng vẫn hoạt động không thể phân biệt được với một tiến trình đã gặp sự cố, vì vậy bất kỳ bộ phát hiện nào cũng đôi khi phải sai. Đây là lý do tại sao các hệ thống không đồng bộ được tăng cường bằng các giả định về thời gian hoặc các bộ phát hiện không đáng tin cậy.