Masters Thesis Defense: Aria Adibi

Broadcasting in computer networking means the dissemination of information, which is originally known only at some nodes, to all members of the network. The goal is to inform every node in the minimal time possible. There are few models for broadcasting, the simplest and the historic model is called the \emph{Classical model}. In the classical model, there is one originator, and dissemination happens at synchronous rounds. In each round, a node may only inform one of its neighbors but it can receive information from any number of neighbors. The question is what is the minimum number of rounds needed for broadcasting, and what broadcast scheme achieves it?

           For general graphs these questions are NP-hard and it is known to be at least 3-\epsilon inapproximable for any real \epsilon > 0. Even for some very restricted classes of graphs, the questions remain as an NP-hard problem. Little is known about broadcasting in restricted graphs, and only a few classes are known to have a polynomial solution.

           Parallel and distributed computing is one of the important domains which relies on efficient broadcasting. The most used network topology in this domain are Hypercube and torus; some papers have even argued that they are the best choice.  The widespread use is not only due to their simplicity, but also is for their efficiency and high robustness (e.g. fault tolerance) while having an acceptable number of links. In this thesis it is observed that the Cartesian product of a number of path and cycle graphs produces a useful set of topologies, we called \emph{hyper-cylinders}, which contain hypercube and torus as well. Any hyper-cylinder shares many of the beneficial features of hypercube and torus and might be a suitable substitution in some cases. Some hyper-cylinders are also similar to other practically used topologies such as Cube-connected cycles. In this thesis,
the effect of the Cartesian product on broadcasting and the Classical and Messy models of broadcasting for hyper-cylinders has been studied. In the end, some fundamental results relating to tree graphs are also provided which is missing from the literature.