The Broadcasting Problem For Bounded-Degree Directed Networks

Abstract

Increasingly, the design of computer networks and multi-processor configurations are now considered critical applications of computer science. Communication supported by network design between different nodes are important for many applications. There are some constraints in network design which usually created by economic and physical limitations. One constraint is the bounded degree, which is the limited number of connections between one node to others. Another possible constraint is a bound on the time that a message can afford to take during a “broadcast”. The topic of this thesis will apply group theory, already used in network design, to design bounded-degree communication-efficient directed networks. We present, for the first time, the largest-known directed networks satisfied special bounds on node degree and broadcast time. The thesis also presents a family of optimal (∆, ∆+1) broadcast digraphs. That is, digraphs with a proven maximum number of nodes, having degree ∆ and broadcast time at most ∆+1