Brief announcement: topology knowledge affects probabilistic reliable communication

ABSTRACT

We consider the problem of probabilistic reliable communication (PRC) over directed networks: Over a synchronous directed network N} = (P,E) where P is the set of vertices and E denotes the set of arcs/edges in the network, the sender S ∈ P wishes to send a message m to the receiver R ∈ P in a robust manner such that the message is correctly received by R with a very high probability, in spite of the presence of up to t Byzantine-faulty nodes in N. We ask the specific question if PRC is affected when the players have only partial knowledge of the network topology. 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, 3]. In this work, we show an example where partial knowledge of the topology results in the failure of PRC, whereas complete knowledge of the same, makes PRC possible.

REFERENCES

• 1: Danny Dolev , Cynthia Dwork , Orli Waarts , Moti Yung, Perfectly secure message transmission, Journal of the ACM (JACM), v.40 n.1, p.17-47, Jan. 1993 [doi>10.1145/138027.138036]
• 2: Bhavani Shankar , Prasant Gopal , Kannan Srinathan , C. Pandu Rangan, Unconditionally reliable message transmission in directed networks, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1048-1055, January 20-22, 2008, San Francisco, California
• 3: Lakshminarayanan Subramanian , Randy H. Katz , Volker Roth , Scott Shenker , Ion Stoica, Reliable broadcast in unknown fixed-identity networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073880]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications; Network topology
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability; Fault tolerance

General Terms:
Algorithms, Reliability, Theory

Keywords:
directed networks, probabilistic reliable communication, topology knowledge