Design and Communication Complexity of Self-Stabilizing Protocols Resilient to Byzantine Faults

Fault-tolerance is one of the most important properties in designing distributed systems. Self-stabilization guarantees that the system eventually behaves according to its specification regardless of the initial configuration. Byzantine fault resilience guarantees that the system behaves according to its specification in the presence of unbounded number of arbitrary malicious actions at Byzantine faulty processes. There exist many works that shows combinations of these two fault tolerance properties. This paper surveys the strategies of existing Byzantine fault resilient and self-stabilizing distributed protocols and presents complexity issues introduced by recent works.