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

Content Provider	ACM Digital Library
Author	Badanidiyuru, Ashwinkumar Patra, Arpita Choudhury, Ashish Srinathan, Kannan Rangan, C Pandu
Copyright Year	2012
Abstract	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 $(\textit{n}),$ the round complexity $(\textit{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 $\textit{n}-connected$ network, a message of size ℓ (to be reliably communicated) and a limit $\textbf{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(\textbf{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.
Starting Page	1
Ending Page	35
Page Count	35
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2371656.2371657
Journal	Journal of the ACM (JACM)
Volume Number	59
Issue Number	5
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-11-05
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Distributed computing Computationally unbounded Message transmission
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Perfectly secure message transmission

A trade-off between information and communication in broadcast protocols

Bit complexity of breaking and achieving symmetry in chains and rings

A trade-off between space and efficiency for routing tables

On the communication complexity of distributed algebraic computation

Reliable communication over unreliable channels

Lower bounds on communication complexity in distributed computer networks

On the average communication complexity of asynchronous distributed algorithms

A Time-Space Trade-Off

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

Similar Documents

Perfectly secure message transmission

A trade-off between information and communication in broadcast protocols

Bit complexity of breaking and achieving symmetry in chains and rings

A trade-off between space and efficiency for routing tables

On the communication complexity of distributed algebraic computation

Reliable communication over unreliable channels

Lower bounds on communication complexity in distributed computer networks

On the average communication complexity of asynchronous distributed algorithms

A Time-Space Trade-Off

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