Istituto di Scienza e Tecnologie dell'Informazione     
Tulone D. On the efficiency of ordering operations with arbitrary failures. The document has been submitted to Conference SRDS 2003, Technical report, 2003.
In this paper we analyze the complexity of the first protocol based on Byzantine Quorum System, for ordering operations on a generic replicated object, and propose two efficient versions of such a protocol: a deterministic and a randomized one. Their improved efficiency, in terms of communication and computational complexity, is obtained by saving one phase of the protocol and introducing hash functions. Notice that the technique of identifying a serializable object by its message digest can be employed in other settings in which a process needs to detect a correct up--to--date copy among the corrupted ones. We also address the problem of collecting out--of--date data, issue related to the asynchronous message system and augmented by the Quorum System approach, and propose a garbage collection integrated with the protocol.
Subject Linearizability, Byzantine failures, Quorum Systems, complexity
C.2.4 Distributed Systems

Icona documento 1) Download Document PS

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional