Concerning the size of clocks

By Fidge and Mattern's algorithm, it was already known that it is sufficient to use n-tuple as timestamps of events for a system distributed over n processes if causal independence is to be characterized. In this paper we have shown that smaller clocks do not work if we just know the number of processes. Then using theorems about the dimension of partially ordered sets we have given a mathematical interpretation of this result. Finally we would like to mention that these combinatorial notions allow to rephrase our result about the “necessity of size n” in a way which does not give any special role to the partially ordered sets (Rⁿ, <) or (Nⁿ, <). Indeed, causality can be characterized by using other reference partially ordered sets than these ones. For instance we can allot q₁, …, q_n to the processes P₁, …, P_n and we can use the numbers ∏_i=1 ⁿq_i ^u[i] instead of the vectors u = Θ(a) ∈ Rⁿ (“Gödel coding”). Then the causality between the events a is detected by the divisibility of these numbers. However, whatever reference partial order is used to define a clock, the example of Section 4 shows that its dimension must be at least n if this clock has to characterize concurrency of systems distributed over n processes.