Crash-tolerant Consensus in Directed Graph Revisited

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

Paper 2018/436

Crash-tolerant Consensus in Directed Graph Revisited

Ashish Choudhury, Gayathri Garimella, Arpita Patra, 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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Major revision. SIROCCO 2018
Contact author(s): ashish choudhury @ iiitb ac in
History: 2018-05-14: received
Short URL: https://ia.cr/2018/436
License: CC BY

BibTeX

@misc{cryptoeprint:2018/436,
      author = {Ashish Choudhury and Gayathri Garimella and Arpita Patra and Divya Ravi and Pratik Sarkar},
      title = {Crash-tolerant Consensus in Directed Graph Revisited},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/436},
      year = {2018},
      url = {https://eprint.iacr.org/2018/436}
}