Reliable broadcasting and secure distributing in channel networks

Abstract

Let T1,-,Tn be n spanning trees rooted at node r of graph G. If for any node v, n paths from r to v, each path in each spanning tree of T1,-,Tn, are internally disjoint, then T1,-,Tn are said to be independent spanning trees rooted at r. A graph G is called an n-channel graph if G has n independent spanning trees rooted at each node of G. We generalize the definition of n-channel graphs. If for any node v of G, among the n paths from r to v, each path in each spanning tree of T1,-,Tn, there are k internally disjoint paths, then T\,-,Tn are said to be (fc, n)-independent spanning trees rooted at r of G. A graph G is called a (fc.n)-channel graph if G has (k, n)independent spanning trees rooted at each node of G. We study two fault-tolerant communication tasks in (fc,n)-channel graphs. The first task is reliable broadcasting. We analyze the relation between the reliability and the efficiency of broadcasting in (k, n)channel graphs. The second task is secure message distribution such that one node called the distributor attempts to send different messages safely to different nodes. We should keep each message secret from the nodes called adversaries. We give two message distribution schemes in (k, n)-channel graphs. The first scheme uses secret sharing, and it can tolerate up to t + k -n listening adversaries for any t < n if G is a (fc,n)-channel graph. The second scheme uses unverifiable secret sharing, and it can tolerate up to t + k -n disrupting adversaries for any t < n/3 if G is a (k, n)-channel graph.