# Overflow of integer counter in distributed systems

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.

• 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? – Raphael Jul 24 '16 at 9:16
• 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. – Jukka Suomela Jul 24 '16 at 10:45
• 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 – Jukka Suomela Jul 24 '16 at 10:51

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.