Cryptology ePrint Archive: Report 2010/392

Interplay between (Im)perfectness, Synchrony and Connectivity: The Case of Reliable Message Transmission

Abhinav Mehta, Shashank Agrawal, Kannan Srinathan

Abstract: For unconditionally reliable message transmission (URMT) in synchronous directed networks of n nodes, a subset of which may be Byzantine faulty, it is well-known that the minimum connectivity requirements for zero-error (perfect) protocols to exist is strictly higher than those where a negligible yet non-zero error probability is allowed (Monte Carlo protocols).

In this work, we study the minimum connectivity requirements for the existence of (a) synchronous Las Vegas protocols, (b) asynchronous Monte Carlo protocols, and (c) asynchronous Las Vegas protocols for URMT. Interestingly, we prove that in any network, synchronous Las Vegas URMT protocol exists if and only if asynchronous Monte Carlo URMT protocol exists too. We further show that asynchronous Las Vegas URMT protocols exist if and only if synchronous perfect protocols exist. We conclude with another interesting result: there exists networks where the number of critical edges for the ‘easier’ randomized variants are asymptotically higher than that for the perfect variant. Thus, our results establish an interesting interplay between (im)perfectness, synchrony and connectivity for the case of URMT.

Category / Keywords: Fault-tolerant Distributed Computing, unbounded adversary, directed graphs, reliable communication, unconditional security

Publication Info: The theorem establishing equivalence between the connectivity requirements for the possibility of synchronous Las Vegas URMT and that of asynchronous Monte Carlo URMT appears without proof as a brief announcement in the proceedings of DISC 2010. Detailed proofs of this result appear in this paper (alongwith several other important results).

Date: received 11 Jul 2010, last revised 8 Aug 2011

Contact author: abhinavmehta14 at gmail com

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20110808:183337 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]