F. Bao et al., RELIABLE BROADCASTING AND SECURE DISTRIBUTING IN CHANNEL NETWORKS, IEICE transactions on fundamentals of electronics, communications and computer science, E81A(5), 1998, pp. 796-806
Citations number
33
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
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.