CryptoDB
Topology Knowledge Versus Fault Tolerance: The Case of Probabilistic Communication Or: How Far Must You See to Hear Reliably?
| Authors: | |
|---|---|
| Download: | |
| 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 [1][2]. We use a novel model for quantifying players' knowledge of network topology, denoted by {$\mathcal K$}. 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 K$}. As a corollary, we answer the question: {\em Up to what neighbourhood level $\ell$ must the players know for the possibility of PRC} where, a player is said to know up to neighbourhood level: $1$ - if it knows only its neighbours; $2$ - if it knows its neighbours and its neighbours' neighbours and so on. [1] Subramanian, L., Katz, R. H., Roth, V., Shenker, S., and Stoica, I. 2005. Reliable broadcast in unknown fixed-identity networks. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing (Las Vegas, NV, USA, July 17 - 20, 2005). PODC '05. ACM, New York, NY, 342-351. [2] DOLEV, D. The byzantine generals strike again. In Journal of Algorithms (1982), pp. 1430. |
BibTeX
@misc{eprint-2008-18100,
title={Topology Knowledge Versus Fault Tolerance: The Case of Probabilistic Communication Or: How Far Must You See to Hear Reliably?},
booktitle={IACR Eprint archive},
keywords={foundations / Topology knowledge, Probabilistic Communication},
url={http://eprint.iacr.org/2008/393},
note={ vasishta@research.iiit.ac.in 14137 received 15 Sep 2008},
author={Pranav K. Vasishta and Prasant Gopal and Anuj Gupta and Piyush Bansal and Kannan Srinathan},
year=2008
}