On the trade-off between network connectivity, round complexity, and communication complexity of reliable message transmission

• DOI: 10.1145/2371656.2371657
• Publication Date: 2012-11-13T15:03:58Z
• Authors: Ashwinkumar Badan...; Arpita Patra; Ashish Choudhury; Kannan Srinathan; C. Pandu Rangan
• Keywords: 330; 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology; 004

Perfectly reliable message transmission (PRMT) is one of the fundamental problems in distributed computing. It allows a sender to reliably transmit a message to a receiver in an unreliable network, even in the presence of a computationally unbounded adversary. In this article, we study the inherent trade-off between the three important parameters of the PRMT protocols, namely, the network connectivity ( n ), the round complexity ( r ), and the communication complexity by considering the following generic question (which can be considered as the holy grail problem) in the context of the PRMT protocols.

Given an n -connected network, a message of size ℓ (to be reliably communicated) and a limit c for the total communication allowed between the sender and the receiver, what is the minimum number of communication rounds required by a PRMT protocol to send the message, such that the communication complexity of the protocol is O( c )?

We answer this interesting question by deriving a nontrivial lower bound on the round complexity. Moreover, we show that the lower bound is tight in the amortized sense, by designing a PRMT protocol whose round complexity matches the lower bound. The lower bound is the first of its kind, that simultaneously captures the inherent tradeoff between the three important parameters of a PRMT protocol.