An optimal CO algorithm stores in l

An optimal CO algorithm stores in local message logs and propagates on messages, information of the form “d is a destination of M” about a message M sent in the causal past, as long as and only as long as:
(Propagation Constraint I) it is not known that the message M is delivered to d, and
(Propagation Constraint II) it is not known that a message has been sent to d in the causal future of Send(M), and hence it is not guaranteed using a reasoning based on transitivity that the message M will be delivered to d in CO.

The Propagation Constraints also imply that if either (I) or (II) is false, the information “d ∈ M.Dests” must not be stored or propagated, even to
remember that (I) or (II) has been falsified. Stated differently, the information “d ∈ Mi,a.Dests” must be available in the causal future of event ei,a, but:
• not in the causal future of Deliverd(Mi,a), and
• not in the causal future of ek,c, where d ∈ Mk,c.Dests and there is no other
message sent causally between Mi,a and Mk,c to the same destination d.
In the causal future of Deliverd(Mi,a), and Send(Mk,c), the information is redundant; elsewhere, it is necessary. Additionally, to maintain optimality, no other information should be stored, including information about what messages have been delivered. As information about what messages have been delivered (or are guaranteed to be delivered without violating causal order) is necessary for the Delivery Condition, this information is inferred using a set-operation based logic.
The Propagation Constraints are illustrated with the help of Figure 6.12.
The message M is sent by process i at event e to process d. The information “d ∈ M.Dests”:
• must exist at e1 and e2 because (I) and (II) are true;
• must not exist at e3 because (I) is false;
• must not exist at e4, e5, e6 because (II) is false;
• must not exist at e7, e8 because (I) and (II) are false.
Information about messages (i) not known to be delivered and (ii) not guaranteed to be delivered in CO, is explicitly tracked by the algorithm using (source, timestamp, destination) information. The information must be deleted as soon as either (i) or (ii) becomes false. The key problem in designing an optimal CO algorithm is to identify the events at which (i) or (ii) becomes false. Information about messages already delivered and messages guaranteed to be delivered in CO is implicitly tracked without storing or propagating it, and is derived from the explicit information. Such implicit information is used for determining when (i) or (ii) becomes false for the explicit information being stored or carried in messages.

Kết quả (Việt) 2:

Một tối ưu các cửa hàng giải thuật CO trong nhật ký tin địa phương và tuyên truyền về các thông điệp, thông tin dạng "d là một điểm đến của M" về tin nhắn M gửi trong quá khứ quan hệ nhân quả, miễn là và chỉ khi:
(Tuyên truyền Constraint I) nó không được biết rằng thông điệp M là giao cho d và
(Tuyên truyền Constraint II) nó không được biết đến là một thông điệp đã được gửi đến d trong tương lai quan hệ nhân quả của Gửi (M), và do đó nó không được đảm bảo bằng một lý luận dựa trên transitivity rằng thông điệp M sẽ được chuyển giao cho d trong CO. Các ràng buộc Tuyên truyền cũng ngụ ý rằng nếu một trong hai (I) hoặc (II) là sai, những thông tin "d ∈ M.Dests" phải không được lưu trữ hoặc truyền, thậm chí để nhớ rằng (I) hoặc (II) đã bị làm giả. Nói cách khác, những thông tin "d ∈ Mi, a.Dests" phải có sẵn trong tương lai quan hệ nhân quả của ei sự kiện, một, nhưng: • không phải trong tương lai quan hệ nhân quả của deliverd (Mi, a), và • không phải trong tương lai quan hệ nhân quả của ek, c, d ∈ nơi Mk, c.Dests và không có khác nhắn gửi nhân quả giữa Mi, một và Mk, c để cùng một điểm đến d. Trong tương lai quan hệ nhân quả của deliverd (Mi, a), và Send ( Mk, c), các thông tin dư thừa; ở những nơi khác, nó là cần thiết. Ngoài ra, để duy trì tối ưu, không có thông tin khác cần được lưu giữ, bao gồm cả thông tin về những thông điệp đã được giao. Khi thông tin về những thông điệp đã được giao (hoặc được đảm bảo để được cung cấp mà không vi phạm trật tự nhân quả) là cần thiết cho các Điều kiện giao hàng, thông tin này được suy ra bằng cách sử dụng một logic set-hoạt động dựa. Các ràng buộc Tuyên truyền được minh họa với sự giúp đỡ của Hình 6.12 . Thông điệp M được gửi bởi quá trình tôi tại sự kiện điện tử để xử lý d. Các thông tin "d ∈ M.Dests": • phải tồn tại e1 và e2 vì (I) và (II) là đúng sự thật; • không phải tồn tại vì e3 (I) là sai; • không phải tồn tại e4, e5, e6 vì (II) là sai; • không phải tồn tại e7, e8 vì (I) và (II) là sai. Thông tin về các tin nhắn (i) không biết sẽ được chuyển giao và (ii) không được bảo đảm sẽ được giao trong CO, được theo dõi một cách rõ ràng bởi các thuật toán sử dụng (nguồn, dấu thời gian, địa điểm) thông tin. Các thông tin phải được xóa ngay sau khi một trong hai (i) hoặc (ii) trở thành sai. Các vấn đề quan trọng trong việc thiết kế một thuật toán tối ưu CO là xác định các sự kiện mà tại đó (i) hoặc (ii) trở thành sai. Thông tin về các tin nhắn đã được chuyển giao và các tin nhắn được bảo đảm sẽ được giao trong CO ngầm theo dõi mà không cần lưu trữ hoặc truyền bá nó, và bắt nguồn từ những thông tin rõ ràng. Thông tin ẩn như vậy được sử dụng để xác định khi (i) hoặc (ii) trở thành sai cho các thông tin rõ ràng được lưu trữ hoặc chuyển đi thông điệp.