Combinatorial Design of Tolerant Communicaiton Structures, with Applications to Non-Blocking Switches

Abstract

This thesis is an investigation into structures and strategies for fault-tolerant communication. We assume the existence of some set of nodes -- people, telephones, processors -- with a need to pass messages -- telephone calls, signals on a wire, data packet-- amongstthemselves. In Part I, our goal is to create a structure, that is, a pattern of interconnection, in which a designated source node can broadcast a message to (and through) a group of recipient nodes. We seek a structure in which every node has tightly limited fanout, but which is nonetheless able to function reliably even when challenged with significant numbers of node failures. The structures are described only in terms of their connectivity, and we therefore use the language of graph theory. Part 11 is based on the observation that certain transformations of the graphs in Part I produce graphs that look like previously studied structures called nonblocking switches. We show that these transformations, when applied to other graphs, yield new, easier approaches to, and proofs of, some known theorems. Part III is an independent body of work describing some investigations into possible extensions of the theory of Kolmogorov-Chaitin complexity into the foundations of pattern recognition. We prove the existence of an information theoretic metric on strings in which the distance between two strings is a measure of the amount of specification required for a universal computer to interconvert the strings. We also prove two topological theorems about this metric.

Files

Additional details