Schweizer, David Lawrence (1991) Combinatorial design of fault-tolerant communication structures, with applications to non-blocking switches. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-07122007-092015
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.
|Item Type:||Thesis (Dissertation (Ph.D.))|
|Degree Grantor:||California Institute of Technology|
|Division:||Engineering and Applied Science|
|Major Option:||Computer Science|
|Thesis Availability:||Restricted to Caltech community only|
|Defense Date:||24 May 1991|
|Default Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Imported from ETD-db|
|Deposited On:||31 Jul 2007|
|Last Modified:||26 Dec 2012 02:55|
- Final Version
Restricted to Caltech community only
See Usage Policy.
Repository Staff Only: item control page