Byzantine Reliable Broadcast with One Trusted Monotonic Counter
摘要
Byzantine Reliable Broadcast is one of the most popular communication primitives in distributed systems. Byzantine reliable broadcast ensures that processes agree to deliver a message from an initiator, even if some processes (possibly including the initiator) are Byzantine. In asynchronous settings, it is known since the prominent work of Bracha [4] that Byzantine reliable broadcast can be implemented deterministically if the total number of processes, denoted by n, satisfies \(n \ge 3t+1\) where t is an upper bound on the number of Byzantine processes. Here, we study Byzantine Reliable Broadcast when processes are equipped with trusted components, special software or hardware designed to prevent equivocation. Our contribution is twofold. First, we show that, despite common belief, when each process is equipped with a trusted component, Bracha’s algorithm still needs \(n \ge 3t+1\) . Second, we present a novel algorithm that uses a single trusted component (at the initiator) that implements Byzantine Reliable Asynchronous Broadcast with \(n \ge 2t+1\) .