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) Short URL: ia.cr/2010/392 Discussion forum: Show discussion | Start new discussion