Paper 2008/393
How Far Must You See To Hear Reliably
Pranav K Vasishta, Anuj Gupta, Prasant Gopal, Piyush Bansal, Rishabh Mukherjee, Poornima M, Kannan Srinathan, and Kishore Kothapalli
Abstract
We consider the problem of probabilistic reliable communication (PRC) over synchronous networks modeled as directed graphs in the presence of a Byzantine adversary when players' knowledge of the network topology is not complete. We show that possibility of PRC is extremely sensitive to the changes in players' knowledge of the topology. This is in complete contrast with earlier known results on the possibility of perfectly reliable communication over undirected graphs where the case of each player knowing only its neighbours gives the same result as the case where players have complete knowledge of the network. Specifically, in either case, $(2t+1)$vertex connectivity is necessary and sufficient, where $t$ is the number of nodes that can be corrupted by the adversary \cite{DDWY93:PSMT,SKR05}. We introduce a novel model for quantifying players' knowledge of network topology, denoted by {$\mathcal TK$}. Given a directed graph $G$, influenced by a Byzantine adversary that can corrupt up to any $t$ players, we give a necessary and sufficient condition for possibility of PRC over $G$ for any arbitrary topology knowledge {$\mathcal TK$}. It follows from our main characterization theorem that knowledge of up to $d = \lfloor \frac{n  2t}{3} \rfloor + 1$ levels is sufficient for the solvability of honest player to honest player communication over any network over which PRC is possible when each player has complete knowledge of the topology. We also show the existence of networks where PRC is possible when players have complete topology knowledge but it is not possible when the players do not have knowledge of up to $d = \lfloor \frac{n  2t}{3} \rfloor + 1$ levels.
Note: The paper has been updated with Corollaries that justify the distance measure in the title.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 reliable communicationtopology knowledgesynchronous networksdirected graphsByzantine adversary
 Contact author(s)
 vasishta @ research iiit ac in
 History
 20091130: last of 3 revisions
 20080916: received
 See all versions
 Short URL
 https://ia.cr/2008/393
 License

CC BY
BibTeX
@misc{cryptoeprint:2008/393, author = {Pranav K Vasishta and Anuj Gupta and Prasant Gopal and Piyush Bansal and Rishabh Mukherjee and Poornima M and Kannan Srinathan and Kishore Kothapalli}, title = {How Far Must You See To Hear Reliably}, howpublished = {Cryptology ePrint Archive, Paper 2008/393}, year = {2008}, note = {\url{https://eprint.iacr.org/2008/393}}, url = {https://eprint.iacr.org/2008/393} }