Abstract

The exponential growth of interconnection networks transformed the communication primitives into an important area of research. One of these primitives is the one-to-all communication, i.e. broadcasting. Its presence in areas such as static and mobile networks, Internet messaging, supercomputing, multimedia, epidemic algorithms, replicated databases, rumors and virus spreading, to mention only a few, shows the relevance of this primitive. In this thesis we focus on the study of interconnection networks from the perspective of two main problems in broadcasting: the minimum broadcast time problem and the minimum broadcast graph problem. Both problems are discussed under the 1-port constant model, which assumes that each node of the network can communicate with only one other node at a time and the transmitting time is constant, regardless of the size of the message. In the first part we introduce the minimum broadcast time function and we present two new properties of this function. One of the properties yields an iterative heuristic for the minimum broadcast time problem, which is the first iterative approach in approximating the broadcast time of an arbitrary graph. In the second part we give exact upper and lower bounds for the number of broadcast schemes in graphs. We also propose an algorithm for enumerating all the broadcast schemes and a random algorithm for broadcasting. In the third part we present a study of the spectra of Knödel graph and their applications. This study is motivated by the fact that, among the three known infinite families of minimum broadcast graphs, namely the hypercube, the recursive circulant, and the Knödel graph, the last one has the smallest diameter. In the last part we introduce a new measure for the fault tolerance of an interconnection network, which we name the global fault tolerance. Based on this measure, we make a comparative study for the above mentioned classes of minimum broadcast graphs, along with other classes of graphs with good communication properties.