Cheap and Secure Web Hosting Provider : See Now

[Answers] Overflow of integer counter in distributed systems

, , No Comments
Problem Detail: 

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.

Asked By : Ivan

Answered By : Ivan

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60904

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback