Cayley networks: A group-theoretic approach to the design and analysis of parallel networks.
Item
-
Title
-
Cayley networks: A group-theoretic approach to the design and analysis of parallel networks.
-
Identifier
-
AAI9207048
-
identifier
-
9207048
-
Creator
-
Baumslag, Marc.
-
Contributor
-
Adviser: Michael Anshel
-
Date
-
1991
-
Language
-
English
-
Publisher
-
City University of New York.
-
Subject
-
Computer Science
-
Abstract
-
A Cayley network is defined to be a parallel network that has an underlying topology of a Cayley graph. Many families of parallel networks built in practice and proposed in the literature can be characterized as Cayley networks, and a multitude of structural and computational benefits ensue from their underlying group-theoretic structure. Also, the structural uniformity of Cayley networks can be exploited to attack many problems from within a single framework.;In the first part of this thesis we study Cayley networks with respect to the issues of communication, reliability and the mapping problem. We discuss several schemes for performing point-to-point routing in Cayley networks and present a general strategy for finding efficient permutation routes. The strategy applies to many familiar networks in the literature, including toroidal mesh networks, hypercube networks, butterfly networks, star networks and a large class of double-ring networks. Often, the routes we derive are the most efficient currently known to exist. On the topic of reliability, we study the connectivity of Cayley graphs and derive a general inductive tool for this purpose. Specific applications of this tool include new proofs of results by Godsil (49) and Akers and Krishnamurthy (3). With regard to the mapping problem, we present several methods for embedding a Cayley graph in a direct product graph. As a consequence, we describe work-preserving emulations of Cayley networks on a family of smaller networks, thereby exposing a processor-time tradeoff.;In the second part of this thesis we prove the following combinatorial results: (1) We present an embedding of the N-node deBruijn network into the N-node hypercube network with dilation {dollar}\lfloor{dollar}2/5 log {dollar}N\rfloor{dollar} and congestion 2. (2) We describe a deterministic algorithm for reconfiguring faulty hypercubes. This is the first deterministic solution to this problem. (3) We determine a generating set for iterated wreath products and semidirect products of cyclic groups that endows the corresponding directed Cayley graphs with directed Hamiltonian circuits, verifying a conjecture of Klerlein (68) for these classes of groups.
-
Type
-
dissertation
-
Source
-
PQT Legacy CUNY.xlsx
-
degree
-
Ph.D.
