RELIABLE BROADCASTING AND SECURE DISTRIBUTING IN CHANNEL NETWORKS

Let T-1,...,T-n be n spanning trees rooted at node r of graph G. If fo r any node v, n paths from r to v, each path in each spanning tree of T-1,...,T-n, are internally disjoint, then T-1,...,T-n are said to be independent spanning trees rooted at r. A graph G is called an n-chann el 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 T-1,...,T-n, there are k internally disjoint paths, then T-1,...,T- n are said to be (k,n)-independent spanning trees rooted at r of G. A graph G is called a (k, n)-channel graph if G has (k,n)-independent sp anning trees rooted at each node of G. We study two fault-tolerant com munication tasks in (k, 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 sho uld keep each message secret from the nodes called adversaries. We giv e two message distribution schemes in (k,n)-channel graphs. The first scheme uses secret sharing, and it can tolerate up to t + k - n listen ing adversaries for any t < n if G is a (k,n)-channel graph. The secon d 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)-channe l graph.