HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Overflow of integer counter in distributed systems

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
overflowsystemsdistributedcounterinteger

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#60904, answer score: 3

Revisions (0)

No revisions yet.