Consensus in the Presence of Overlapping Faults and Total Omission

Summary

Understanding the fault tolerance of Byzantine Agreement protocols is an important question in distributed computing. While the setting of Byzantine faults has been thoroughly explored in the literature, the (arguably more realistic) omission fault setting is far less studied. In this paper, we revisit the recent work of Loss and Stern who gave the first protocol in the mixed fault model tolerating t Byzantine faults, s send faults, and r receive faults, when 2t + r + s 2, or a broadcast protocol for s + r = n and s > 1 even without overlapping faults.