1
$\begingroup$

In lamport's paper[1], he define two concept The partial ordering and The totally ordering.

  1. What does partial mean in partial ordering?

    assumption: this ordering only handle two cases, one is to order events happening in single process, second is communication events between two process. It can't handle concurrent events, so it's named as Partial ordering.

    Is my assumption correct?

  2. What does totally ordering mean?

    Does that mean it can handle all the events in a distributed system?

Reference

Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System.”

$\endgroup$
  • 4
    $\begingroup$ By any chance, does it refer to the set theoretical concepts of ordering? There's another explanation here which seems to imply so. $\endgroup$ – Gokul Oct 18 '18 at 3:39
  • 2
    $\begingroup$ Lamport‘s famous paper just revisits the standard definitions of partial ordering and total ordering that are well known from set theory. Just consult a basic math book or even Wikipedia for definitions. $\endgroup$ – datell Oct 18 '18 at 12:19
3
$\begingroup$

The "partial ordering" in the papar means partial order as in standard mathemtics theory. To be more rigorous, the "partial ordering" in that paper, also called "irreflexive parital ordering" in that paper, means strict partial order. (Yes, "strict" means "irreflexive".) (Yes, "order" can be used interchangeably with "ordering" sometimes. I prefer "order" in a mathematics environment and "ordering" in non-mathematics environment, since "order" is such a common English word.)

Informally, that "partial" means it is possible a "<" relation thereof is missing for some pairs of elements. Here is an example. Let $S=\{a,b,c\}$. We can define a relation $<_1$ on $S$ by $a<_1 b$ and $a<_1 c$. That is all. Note we did not say anything about the relationship between $a$ and $c$. In fact, we have specified that there should not be a relationship between $a$ and $c$. These two elements are incomparable. That is why we say $<_1$ is a "partial" relation on $S$.

In that paper, for example, $p_3$ and $q_3$ are two incomparable events. We cannot say $p_3\to q_3$ nor $q_3\to p_3$. The order relationship between $p_3$ and $q_3$ is missing. It is not defined. That is why it is referred as a "partial" ordering. "It can't handle concurrent events, so it's named as Partial ordering." That understanding is pretty good. However, I would phrase it as "It does not order concurrent events, ...". I mean, it does handle concurrent events, resulting in that concurrent events should be treated as incomparable.

In contrast, "a total ordering" or, a total order is a partial ordering under which every pair of elements are comparable. If you find these two math terms sound contradictory, think of them as square are also rectangles. In fact, the "total ordering" in the paper is the strict total order. Yes, you can understand that "total ordering" means "it can handle all the events in a distributed system", or "it can order every pair of events in a distributed system (as defined in the paper)".


You may find lots of terminologies in the theory of partially ordered set and order theory. It looks like overwhelming initially. However, most of the concepts are very easy to understand intuitively.

In your case, all you need to understand is how is $\to$ defined on the set of events of a system and that a total ordering is such a special $\to$ that for any two events $e_1$ and $e_2$, either $e_1\to e_2$ or $e_2\to e_1$ must hold. You could ignore all those formal concepts in math theory even though they might help understand more things later more clearly.

As mentioned by Gokul, here is a pretty good explanation about Lamports's logical clocks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.