Polynomial Time Synthesis of Byzantine Agreement

Sandeep S. Kulkarni, Anish Arora and Arun Chippada


We present a polynomial time algorithm for automatic synthesis of fault-tolerant distributed programs starting from fault-intolerant versions of those programs. Since this synthesis problem is known to be NP-hard, our algorithm relies on heuristics to reduce the complexity. We demonstrate that our algorithm suffices to synthesize an agreement program that tolerates a byzantine fault.


Return to the publication list
Return to the Sandeep's home page