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)(n) -Sigma(k=3)(n) ((n)(k)) ((2k-3)(k)))] bits is necessary. (C) 2002 Elsevier Science B.V. All rights reserved.
On the minimal information to encode timestamps in distributed computations / Baldoni, Roberto; Giovanna, Melideo. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 84:3(2002), pp. 159-166. [10.1016/s0020-0190(02)00241-7]
On the minimal information to encode timestamps in distributed computations
BALDONI, Roberto;
2002
Abstract
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)(n) -Sigma(k=3)(n) ((n)(k)) ((2k-3)(k)))] bits is necessary. (C) 2002 Elsevier Science B.V. All rights reserved.| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2002_11573-47015.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
171.29 kB
Formato
Adobe PDF
|
171.29 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
