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

Abhinav Mehta; Shashank Agrawal; Kannan Srinathan

Paper 2010/392

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

Abhinav Mehta, Shashank Agrawal, and 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.

Metadata

Available format(s): PDF PS
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).
Keywords: Fault-tolerant Distributed Computing unbounded adversary directed graphs reliable communication unconditional security
Contact author(s): abhinavmehta14 @ gmail com
History: 2011-08-08: last of 14 revisions; 2010-07-11: received; See all versions
Short URL: https://ia.cr/2010/392
License: CC BY

BibTeX

@misc{cryptoeprint:2010/392,
      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},
      url = {https://eprint.iacr.org/2010/392}
}