BOUNDED TIME-STAMPS

Time-stamps are labels which a system adds to its data items. These la bels enable the system to keep track of the temporal precedence relati ons among its data elements. Many distributed protocols and some appli cations use the natural numbers as time-stamps. The natural numbers ho wever are not useful for bounded protocols. In this paper we develop a theory of bounded time-stamps. Time-stamp schemes are defined and the complexity of their implementation is analyzed. This indicates a dire ction for developing a general tool for converting time-stamp based pr otocols to bounded protocols.