Unconditionally reliable message transmission in directed networks

ABSTRACT

In the unconditionally reliable message transmission (URMT) problem, two non-faulty players, the sender S and the receiver R are part of a synchronous network modeled as a directed graph. S has a message that he wishes to send to R; the challenge is to design a protocol such that after exchanging messages as per the protocol, the receiver R should correctly obtain S's message with arbitrarily small error probability δ, in spite of the influence of a Byzantine adversary that may actively corrupt up to t nodes in the network (we denote such a URMT protocol as (t, (1 - δ))-reliable). While it is known that (2t + 1) vertex disjoint directed paths from S to R are necessary and sufficient for (t, 1)-reliable URMT (that is with zero error probability), we prove that a strictly weaker condition, which we define and denote as (2t, t)-special-connectivity, together with just (t+1) vertex disjoint directed paths from S to R, is necessary and sufficient for (t, (1' - δ))-reliable URMT with arbitrarily small (but non-zero) error probability, δ. Thus, we demonstrate the power of randomization in the context of reliable message transmission. In fact, for any positive integer k > 0, we show that there always exists a digraph G_k such that (k, 1)-reliable URMT is impossible over G_k whereas there exists a (2k, (1 - δ))-reliable URMT protocol, δ > 0 in G_k.

In a digraph G on which (t, (1 - δ))-reliable URMT is possible, an edge is called critical if the deletion of that edge renders (t, (1 - δ))-reliable URMT impossible. We give an example of a digraph G on n vertices such that G has Ω(n²) critical edges. This is quite baffling since no such graph exists for the case of perfect reliable message transmission (or equivalently (t, 1)-reliable URMT) or when the underlying graph is undirected. Such is the anomalous behavior of URMT protocols (when "randomness meet directedness") that it makes it extremely hard to design efficient protocols over arbitrary digraphs. However, if URMT is possible between every pair of vertices in the network, then we present efficient protocols for the same.

REFERENCES

• 1: Yvo Desmedt , Yongge Wang, Perfectly Secure Message Transmission Revisited, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.502-517, May 02, 2002
• 2: 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]
• 3: M. Franklin and R. N. Wright. Secure Communication in Minimal Connectivity Models. Journal of Cryptology, 13(1):9--30, 2000.
• 4: Kannan Srinathan , C. Pandu Rangan, Possibility and complexity of probabilistic reliable communication in directed networks, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146421]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems; Network problems
      G.2.3 Applications

General Terms:
Algorithms, Design, Theory