On the Communication Complexity of Reliable and Secure Message Transmission in Asynchronous Networks

Date Added: Jun 2011
Format: PDF

In this paper, the authors study the communication complexity of Reliable Message Transmission (RMT) and Secure Message Transmission (SMT) protocols in asynchronous settings. They consider two variants of the problem, namely perfect (where no error is allowed in the protocol outcome) and statistical (where the protocol may output a wrong outcome with negligible probability). RMT and SMT protocols have been investigated rigorously in synchronous settings. But not too much attention has been paid to the asynchronous version of the problem. In a significant work, Choudhury et al. (ICDCN 2009 and JPDC 2011) have studied the network connectivity requirement for perfect and statistical SMT protocols in asynchronous setting.