Reliable Broadcast in a Computational Hybrid Model with Byzantine Faults, Crashes, and Recoveries

Abstract

This paper presents a formal model for asynchronous distributed systems with parties that exhibit Byzantine faults or that crash and subsequently recover. Motivated by practical considerations, it represents an intermediate step between crash-recovery models for distributed computing and proactive security methods for tolerating arbitrary faults. The model is computational and based on complexity-theoretic techniques from modern cryptography, which allows for reasoning about cryptographic protocols in a formal way. One of the most important problems in fault-tolerant distributed computing, reliable broadcast, is then investigated in this hybrid model. A definition of reliable broadcast is presented and an implementation is given based on the protocol of Bracha (PODC '84).