Cryptology ePrint Archive: Report 2018/436

Crash-tolerant Consensus in Directed Graph Revisited

Ashish Choudhury and Gayathri Garimella and Arpita Patra and Divya Ravi and Pratik Sarkar

Abstract: Fault-tolerant distributed consensus is a fundamental problem in secure distributed computing. In this work, we consider the problem of distributed consensus in directed graphs tolerating crash failures. Tseng and Vaidya (PODC'15) presented necessary and sufficient condition for the existence of consensus protocols in directed graphs. We improve the round and communication complexity of their protocol. Moreover, we prove that our protocol requires the optimal number of communication rounds, required by any protocol belonging to a restricted class of crash-tolerant consensus protocols in directed graphs.

Category / Keywords: foundations /

Original Publication (with major differences): SIROCCO 2018

Date: received 11 May 2018

Contact author: ashish choudhury at iiitb ac in

Available format(s): PDF | BibTeX Citation

Version: 20180514:141141 (All versions of this report)

Short URL: ia.cr/2018/436


[ Cryptology ePrint archive ]