Polynomial Time Synthesis of Byzantine Agreement

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by S. Kulkarni Articles by A. Arora Articles by A. Chippada

20th IEEE Symposium on Reliable Distributed Systems (SRDS'01)

New Orleans, Louisiana

October 28-October 31

ISBN: 0-7695-1366-2

	ASCII Text	x
	S. Kulkarni, A. Arora, A. Chippada, "Polynomial Time Synthesis of Byzantine Agreement," Reliable Distributed Systems, IEEE Symposium on, pp. 0130, 20th IEEE Symposium on Reliable Distributed Systems (SRDS'01), 2001.

	BibTex	x
	@article{ 10.1109/RELDIS.2001.969767, author = {S. Kulkarni and A. Arora and A. Chippada}, title = {Polynomial Time Synthesis of Byzantine Agreement}, journal ={Reliable Distributed Systems, IEEE Symposium on}, volume = {0}, year = {2001}, isbn = {0-7695-1366-2}, pages = {0130}, doi = {http://doi.ieeecomputersociety.org/10.1109/RELDIS.2001.969767}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Reliable Distributed Systems, IEEE Symposium on TI - Polynomial Time Synthesis of Byzantine Agreement SN - 0-7695-1366-2 SP EP A1 - S. Kulkarni, A1 - A. Arora, A1 - A. Chippada, PY - 2001 KW - Fault-tolerance KW - Formal methods KW - Program synthesis KW - Program transformation KW - Distributed programs VL - 0 JA - Reliable Distributed Systems, IEEE Symposium on ER -

S. Kulkarni, Michigan State University

A. Arora, Ohio State University

A. Chippada, Michigan State University

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/RELDIS.2001.969767

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.

Index Terms:

Fault-tolerance, Formal methods, Program synthesis, Program transformation, Distributed programs

Citation:

S. Kulkarni, A. Arora, A. Chippada, "Polynomial Time Synthesis of Byzantine Agreement," srds, pp.0130, 20th IEEE Symposium on Reliable Distributed Systems (SRDS'01), 2001

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.