ANY COMPUTING SYSTEM can be described as executing
sequences of actions, with an action being any relevant
change in the state of the system. For example, reading
a file to memory, modifying the contents of the file
in memory, or writing the new contents to the file are
relevant actions for a text editor. In a distributed
system, actions execute in multiple
locations; in this context, actions
are often called events. Examples of
events in distributed systems include
sending or receiving messages, or
changing some state in a node. Not
all events are related, but some events
can cause and influence how other,
later events occur. For example, a reply to a received email message is influenced by that message, and maybe
by prior messages received.
Events in a distributed system can
occur in a close location, with different processes running in the same
machine, for example; or at nodes
inside a datacenter; or geographically
spread across the globe; or even at a
larger scale in the near future. The relations of potential cause and effect
between events are fundamental to
the design of distributed algorithms.
These days hardly any service can
claim not to have some form of dis-
tributed algorithm at its core.
To make sense of these cause-and-effect relations, it is necessary to
limit their scope to what can be perceived inside the distributed system
itself—internal causality. Naturally, a
distributed system interacts with the
rest of the physical world outside of
it, and there are also cause-and-effect
relations in that world at large. For example, consider a couple planning a
night out using a system that manages reservations for dinner and a movie. One person makes a reservation
for dinner and lets the other person
know with a phone call. After receiving the phone call, the second person
goes to the system and reserves a movie. A distributed system has no way of
knowing the first reservation has actually caused the second one.
This external causality cannot be
detected by the system and can only
be approximated by physical time.
Why Logical
Clocks
Are Easy
DOI: 10.1145/2890782
Article development led by
queue.acm.org
Sometimes all you need
is the right language.
BY CARLOS BAQUERO AND NUNO PREGUIÇA