On the minimal information to encode timestamps in distributed computations

✍ Scribed by Roberto Baldoni; Giovanna Melideo

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 171 KB
• Volume: 84
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(02)00241-7

✦ Synopsis

Timestamping protocols are used to capture the causal order or the concurrency of events in asynchronous distributed computations. In this paper we give an answer to the open problem issued by Schwarz and Mattern [Distrib. Comput. 7 (3) (1994) 149-174] about the minimum amount of information managed by protocols which represent causality in an isomorphic way. We point out that to encode each timestamp an amount of non-structured information (i.e., the number of bits) of log 2 ((m + 1) nn k=3 n k 2k-3 k ) bits is necessary.