The timestamp problem captures a fundamental aspect of asynchronous distributed computing. It allows processes to label events with timestamps that provide information about the real-time ordering of those events. We consider the space complexity of wait-free implementations of timestamps from shared registers in a system of n processes.
We prove an $\Omega(\sqrt{n})$ lower bound on the number of registers required. If the timestamps are elements of a nowhere dense set, for example the integers, we prove a stronger, and tight, lower bound of $n$. However, if timestamps can be from an arbitrary set, we show how this bound can be beaten.
This work is joint with Panagiota Fatourou and Eric Ruppert.