3
$\begingroup$

I was studying Paxos from the paper by Lamport called "Paxos Made Simple".

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

On page 3, it says

Since all numbers are totally ordered, condition P2 guarantees the crucial safety property that only a single value is chosen.

where P2 is the following

If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

What does it mean for numbers to be totally ordered? How is this property essential for condition P2 to guarantee safety?

$\endgroup$
  • 4
    $\begingroup$ When applied to elements of a set, "totally ordered" means that there is an order relation between the elements of that set such that you can always compare 2 elements taken in the set. Integers, or reals are totally ordered sets. Given 2 distinct integers, there is always one that is greater than the other. Such relations are useful when they obey some properties w.r.t. operations on the elements of the set. $\endgroup$ – babou Mar 28 '14 at 17:13
5
$\begingroup$

Totally ordered means that there exists an order relation such that given any two elements, one is greater than the other. In other words, there are no incomparable elements. For example, the real numbers are totally ordered: either $x \le y$ or $y \le x$. Counter-example: set inclusion $\subseteq$ is an order relation, but $\{0\}$ and $\{1\}$ are incomparable.

Intuitively, a total order is one where you can lay all the elements on a line, where moving along the line always increases the value. (This is not mathematically true because some orders are too “dense” to fit.)

Suppose that two proposals numbered $n_1$ and $n_2$ are chosen, with values $v_1$ and $v_2$ respectively. The desired safety property is that the values are in fact the same: $v_1 = v_2$. By condition P2, if $n_1 \le n_2$, then proposal $n_2$ is higher-numbered than proposal $n_1$, so its value $v_2$ is equal to $v_1$. Similarly, if $n_2 \le n_1$ then $v_1 = v_2$. The fact that the integers are totally ordered implies that at least one of the propositions $n_1 \le n_2$ and $n_2 \le n_1$ is true, and therefore either way $v_1 = v_2$.

What condition P2 means in some idealized way is that if a choice is made, all subsequent choices will be for the same value. However, “subsequent” doesn't quite work out, because the numbering of the proposals doesn't necessarily correspond with the order in which they are made in real time: different nodes in the network can make proposals before they are aware of each other, so numbers can't be assigned to proposals in chronological order. Solving this problem is a large part of working out a consensus algorithm.

$\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.