Polynomial Time Synthesis of Byzantine Agreement
Sandeep S. Kulkarni, Anish Arora and Arun Chippada
Abstract
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.
Paper:
Return to the publication list
Return to the Sandeep's home page