A Caltech Library Service

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


Schweizer, David Lawrence (1991) Combinatorial design of fault-tolerant communication structures, with applications to non-blocking switches. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/92k2-w943.


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.))
Subject Keywords:Computer Science
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Abu-Mostafa, Yaser S.
Thesis Committee:
  • Unknown, Unknown
Defense Date:24 May 1991
Record Number:CaltechETD:etd-07122007-092015
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2859
Deposited By: Imported from ETD-db
Deposited On:31 Jul 2007
Last Modified:19 Apr 2021 22:36

Thesis Files

PDF (Schweizer_dl_1991.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page