Coping with Byzantine Processes and a Message Adversary: Modularity Helps!
share
This paper explores how reliable broadcast can be implemented when facing a dual adversary that can both corrupt processes and remove messages.More precisely, we consider an asynchronous n-process message-passing systems in which up to t_b processes are Byzantine and where, at the network level, for each message broadcast by a correct process, an adversary can prevent up to t_m processes from receiving it (the integer t_m defines the power of the message adversary).So, differently from previous works, this work considers that not only computing entities can be faulty (Byzantine processes), but also that the network can lose messages.To this end, the paper first introduces a new basic communication abstraction denoted kℓ-cast, and studies its properties in this new bi-dimensional adversary context.Then, the paper deconstructs existing Byzantine-tolerant asynchronous broadcast algorithms and, with the help of the kℓ-cast communication abstraction, reconstructs versions of them that tolerate both Byzantine processes and message adversaries.Interestingly, these reconstructed algorithms are also more efficient than the Byzantine-tolerant-only algorithms from which they originate.The paper also shows that the condition n>3t_b+2t_m is necessary and sufficient (with signatures) to design such reliable broadcast algorithms.
READ FULL TEXT