Concerning the size of logical clocks in distributed systems (Q1182109)

\textit{C. Fidge} [Timestamps in message passing systems that preserve the partial ordering in Proc. 11th Australian Computer Science Conf., 55-66 (1988)] and \textit{F. Mattern} [Virtual time and global states of distributed systems in Parallel and Distributed Algorithms, Amsterdam: North-Holland, 215-226 (1988)] improve \textit{L. Lamport}'s [Commun. ACM 21, 558-565 (1978; Zbl 0378.68027)] logical time with a clock that entirely reflects the partial order defined by the causality relation. The events are timestamped by vectors of \(\mathbb{N}^ n\), where \(n\) is the number of processes. The use of such vectors may seem very heavy as soon as one is concerned with a distributed system on a large number of processes. We prove that vectors of this length are necessary to characterize causality, by constructing an appropriate distributed computation. Then we use classical theorems from the theory of partially ordered sets to give a mathematical interpretation of this result.