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 allegati a questo prodotto
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   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/47015
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact