3
$\begingroup$

I've just been introduced to Paxos. There is notion of the of value that is incremented each time a new proposal is send. To provide order for proposals, something like time. What happens when this long or integer value overflows and starts from zero again. The proposed sequence number will become lower than the old one and every proposal will be rejected.

Thank you.

$\endgroup$
  • 1
    $\begingroup$ It seems you already answered your own question. Note that you may have reached the border between "algorithm" and "program"; such rather arbitrary limitations of real machines are rarely considered when you talk about algorithms but have of course been taken care of when actually implementing them. This is important (and apparently quite often overlooked, even by the best) but I don't think it's a computer science issue per se. Community votes, please: offtopic? $\endgroup$ – Raphael Jul 24 '16 at 9:16
  • 4
    $\begingroup$ I think this is very well on-topic for this site. There are lots of papers related to the theory of distributed computing that explicitly address the question of whether something can be done with bounded registers. This is not just an implementation issue; it is a fundamental question in computer science, and directly connected to e.g. fault-tolerant algorithms. $\endgroup$ – Jukka Suomela Jul 24 '16 at 10:45
  • 1
    $\begingroup$ I don't have time to write a proper answer, but e.g. this paper + references there is probably highly relevant (search for the keywords "bounded" and "unbounded" to find discussion related to this topic): arxiv.org/pdf/1305.4263.pdf $\endgroup$ – Jukka Suomela Jul 24 '16 at 10:51
3
$\begingroup$

In general:

Paxos algorithm uses unbounded integers to tag data. In practice, however, every integer handled by the processors is bounded by some constant $2^b$ where $b$ is the integer memory size. Yet, if every integer variable is initialized to a very low value, the time needed for any such variable to reach the maximum value $2^b$ is actually way larger than any reasonable system’s timescale. For instance, counting from $0$ to $2^{64}$ by incrementing every nanosecond takes roughly 500 years to complete. Such a long sequence is said to be practically infinite.

Self-stabilizing systems:

One particular aspect of self-stabilizing systems is the need to re-examine the assumption concerning the use of (practically) unbounded time-stamps. While in practice it is reasonable for Paxos to assume that a bounded value, represented by 64 bits, is a natural (unbounded) number, for all practical considerations, in the scope of self-stabilization the 64 bits value may be corrupted by a transient fault to its maximal value at once, and still recovery following such a transient fault must be guaranteed.

Source: Self-Stabilizing Paxos

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