Define various way to event ordering in distributed os
Answers
Answered by
3
In a centralized system, we can always determine the order in which two events occurred, since the system has a single common memory and clock. Many applications may require us to determine order. For example, in a resourceallocation scheme, we specify that a resource can be used only after the resource has been granted. A distributed system, however, has no common memory and no common clock. Therefore, it is sometimes impossible to say which of two events occurred first. The liappened-before relation is only a partial ordering of the events in distributed systems.
Since the ability to define a total ordering is crucial in many applications, we present a distributed algorithm for exterfding the happened-before relation to a consistent total ordering of all the events in the system.
The Happened-Before Relation
Since we are considering only sequential processes, all events executed in a single process are totally ordered. Also, by the law of causality, a message can be received only after it has been sent. Therefore, we can define the happenedbefore relation (denoted by -») on a set of events as follows (assuming that sending and receiving a message constitutes an event):
1. If A and B are events in the same process, and A was executed before B, then A -» B.
2. If A is the event of sending a message by one process and B is the event of receiving that message by another process, then A —»• B. 3. If A -> B and B -» C then A -• C. Since an event cannot happen before itself, the -> relation is an irreflexive partial ordering.
If two events, A and B, are not related by the —> relation (that is, A did not happen before B, and B did not happen before A), then we say that these two events were executed concurrently. In this case, neither event can causally affect the other. If, however, A -> B, then it is possible for event A to affect event B causally.
Since the ability to define a total ordering is crucial in many applications, we present a distributed algorithm for exterfding the happened-before relation to a consistent total ordering of all the events in the system.
The Happened-Before Relation
Since we are considering only sequential processes, all events executed in a single process are totally ordered. Also, by the law of causality, a message can be received only after it has been sent. Therefore, we can define the happenedbefore relation (denoted by -») on a set of events as follows (assuming that sending and receiving a message constitutes an event):
1. If A and B are events in the same process, and A was executed before B, then A -» B.
2. If A is the event of sending a message by one process and B is the event of receiving that message by another process, then A —»• B. 3. If A -> B and B -» C then A -• C. Since an event cannot happen before itself, the -> relation is an irreflexive partial ordering.
If two events, A and B, are not related by the —> relation (that is, A did not happen before B, and B did not happen before A), then we say that these two events were executed concurrently. In this case, neither event can causally affect the other. If, however, A -> B, then it is possible for event A to affect event B causally.
Similar questions