Paper 2010/392

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

Abhinav Mehta, Shashank Agrawal, and Kannan Srinathan


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.

Available format(s)
Publication info
Published elsewhere. 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).
Fault-tolerant Distributed Computingunbounded adversarydirected graphsreliable communicationunconditional security
Contact author(s)
abhinavmehta14 @ gmail com
2011-08-08: last of 14 revisions
2010-07-11: received
See all versions
Short URL
Creative Commons Attribution


      author = {Abhinav Mehta and Shashank Agrawal and Kannan Srinathan},
      title = {Interplay between (Im)perfectness, Synchrony and Connectivity: The Case of Reliable Message Transmission},
      howpublished = {Cryptology ePrint Archive, Paper 2010/392},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.