Returning to our original example of me ordering
a ticket to go to India via Expedia
and Delta. Let's now identify all the events
that are connected directly by the happened-before relationship.
So, if these are the events in my process, then we know that E happened before
H. And, we know that H happened before I. And, we know that I happened for L.
So that's the textual ordering, and we know the
process is sequential. This is the ordering of events, in
my process. And similarly, we can see that, if
these are the events in Expedia's process. Then all of
these events have to be sequentially ordered. SO, B
should have happened before C C should have happened before
F, F should have happened before G, and G
should have happened before M. So these are the orderings
of the events in Expedia's process and similarly
we can derive the order of events in
the delta process, as sequential. And these are
all the communication events that are directly relating
events happening between any two processes that I'm
showing you in this picture. So, for instance,
E to F is a message from Delta
back to Expedia confirming my reservation. So E is
the act of sending the message from Delta, and
F is the act of receiving the same message from
Delta on Expedia. So, those are all the communication
events. And now you can also look at transitive events,
so for instance. What is the relationship between, let's
say, event E and event A? Well, it turns out
that A must have happened before event E. And
the reason is, if you look at A, it happened
before B, B happened before C, C happened before D.
All of these are communication events, pretty straight forward. So
from here to here, it's not a communication event, but
since the process is sequential, B should have happened before
C, and of course C happened before D. So, since
it's a communication event, sequential process D should have happened
before E. And that's what gives a transitive relationship between
A and E, that A must have happened before E.
Similarly, we can identify other events that
are transitively connected to one another. Because of
the happen-before relationship. So, for instance, D and
M apparently don't have any direct connection. But,
through the transitivity of events that are happening
sequentially, and through the communication, and sequentiality of
a process, we know that D must have
happened before M. So those are transitive events.
And finally, let's look at concurrent events. If you
think about this event M that's happening in Expedia. Basically
Expedia has confirmed to me that I have the booking
that I want. Then it is doing some internal bookkeeping,
to record some information about me, maybe my preferences
in terms of airlines and so on and so forth.
And from that point of view, it is making some
internal bookkeeping and that's is event M. And now if
you look at this event M, it has no
relationship to any of the events that are happening here.
I'm showing G, this event H must have happened after
G, but what about H and M? There is no
relationship between these two guys. This could've happened much
later than, than this in wall clock time. Or it
could've happened much sooner than event M. So you can
see that, H is concurrent with M, and in fact,
all the events that you see here, are
going to be concurrent with M. And similarly, all the
events that you are seeing over here, they're
concurrent with So in fact, they're concurrent with M.
After this, if you look at the Delta
process, after Delta has sent this message to Expedia
confirming my booking, it may have done a whole
bunch of events, over here. All of those events
are concurrent with M, because there is
no ordering between these events, and the events
over here. But there is an ordering between the event, G and the event J here.
Because G happened before H, H happened before
I, I happened before J. So, you can
see that transitivity connects events across machines. But
they could be events that are happening in
the distributed system, that are unconnected to other
events. And those are concurrent events. That completes
discussion of the basics of distributed system. Next
we're going to start talking about Lampard's clock.