Crash-tolerant Consensus in Directed Graph Revisited

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

Paper 2018/436 Original: eprint.iacr.org/2018/436 ↗

Crash-tolerant Consensus in Directed Graph Revisited

Ashish Choudhury

Gayathri Garimella

Arpita Patra

Divya Ravi

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: Preprint.
History: 2018-05-14: last updated; 2018-05-14: published
Short URL: https://ia.cr/2018/436
License: https://creativecommons.org/licenses/by/4.0/

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}
}