A Caltech Library Service

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

Schweizer, David Lawrence (1991) Combinatorial Design of Tolerant Communicaiton Structures, with Applications to Non-Blocking Switches. California Institute of Technology . (Unpublished)

See Usage Policy.

Other (Adobe PDF (2.6MB))
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Technical Report)
Group:Computer Science Technical Reports
Record Number:CaltechCSTR:1991.cs-tr-91-09
Persistent URL:
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26742
Deposited By: Imported from CaltechCSTR
Deposited On:25 Apr 2001
Last Modified:03 Oct 2019 03:17

Repository Staff Only: item control page