Đang chuẩn bị liên kết để tải về tài liệu:
DESIGN AND ANALYSIS OF DISTRIBUTED ALGORITHMS phần 10

Thay vào đó, nó mô tả một loạt các tình huống. Rõ ràng nhất là khi đột ngột tiếng ồn trong các kênh truyền dẫn là nhầm lẫn với một tin nhắn. Tuy nhiên, sự xuất hiện quan trọng bổ sung trong sytems là khá tinh tế: Khi chúng ta nói rằng các tin nhắn nhận được "là không lây truyền", những gì chúng ta thực sự | 528 DETECTING STABLE PROPERTIES access to its own local clock cx so the value cx t of x s clock at real time t might be different from that of other entities at the same time and all of them different from t. Furthermore unless the additional restrictions of full synchronicity hold the local clocks might have different speeds the distance between consecutive ticks of the same clock might change over time there are no time bounds on communication delays and so forth. In other words within the system there is no common notion of time. Fortunately practically in all cases although useful a common notion of time is not needed. To understand what is sufficient for our purposes observe that real time gives a total order to all the events and the actions that occur in the system We can say whether two events occur at the same time whether an action is performed before an event takes place and so forth. In other words given any two actions or events that occurred in the system we external observers can say using real time whether one occurred before at the same time as or after the other. The entities in the system with just access to their local clocks have much less knowledge about the temporal relationships of actions and events however they do have some. In particular each entity has a complete temporal knowledge of the events and actions occurring locally when a message arrives it also knows that the action of transmitting this message happened before its reception. It turns out that this knowledge is indeed sufficient for obtaining a consistent snapshot. To see how let us first of all generalize the notion of snapshot and introduce that of a cut. Let t1 t2 . tn be instants of real time not necessarily distinct and let x0 x2 . xn be the entities then C xi tj denotes the state of entity xi in computation C at time ti. The set T t1 t2 . . . tn is called a time cut and the set C T C X1 t1 C X2 t2 . C Xn tn of the associated entities states is called the snapshot of C at