Bounded time-stamps

Time-stamps are numerical labels which enable a system to keep track of temporal precedence relation among its data elements. Traditionally time-stamps are used as unbounded numbers and inevitable overflows cause a loss of this precedence relation. In this paper we develop a complete theory of bounded time-stamps. Time-stamp systems are defined and the complexity of their implementation is fully analyzed. This theory gives a very general tool for converting timestamp based protocols to bounded protocols. The generality of this theory is demonstrated by novel, conceptually simple, protocols for a multiuser atomic registers, as well as by proving for the first time a non-trivial lower bound for such a register.