Combinatorial design of fault-tolerant communication structures, with applications to non-blocking switches

[摘要] 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 packets--amongst themselves.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 fan-out, 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 II is based on the observation that certain transformations of the graphs in Part I produce graphs that look like previously studied structures called non-blocking 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.

[发布机构] University:California Institute of Technology;Department:Engineering and Applied Science

[关键词] Computer Science