PhD Thesis

Boston University, Graduate School, 1996

Abstract

The thesis considers two common models of distributed parallel computation.
It contains new protocols proven to allow the respective computing media to
organize themselves to be unexpectedly robust and efficient.

A computing media consists of a large number of interconnected computing
elements (processors). Those often need to be packed on a plane as densely as
possible, e.g. on a Very Large Scale Integration (VLSI) chip. The first protocol
of the thesis runs on fast media, where short connections work faster than long
ones. It allows such media of simple grid topology to simulate with
almost no delay arbitrary ``virtual'' wires which, unlike real wires, have
nearly zero width, can change in runtime, allow concurrent read, transmit many
bits at a time, etc. Using this protocol on VLSI chips eliminates the layout
problem and rigidity of the chip's connections. This contrasts with current
practices: hardwired connections are rigid and dominate the precious area of the
chip. Other flexible and area-efficient solutions were proposed, but none
applicable to fast, in the above sense, media.

Other media considered in the thesis, like distributed networks, have arbitrary
topology. They are also dynamic -- connections change during computation, often
sporadically. The media are asynchronous and unreliable, subject to worst-case
transient faults. As in the first media, the elements are identical and
independent of the media (chip or network) size. No previous work for such
general topology networks of constant elements existed.
Again, somewhat unexpectedly, these limitations appear more severe than they
really are: The thesis shows that they do not affect such media's computing
power which depends only on the natural resource bounds of space and
information. Namely, the thesis constructs self-stabilizing asynchronous
protocols, which enable the media to solve any problem solvable by any standard
sequential computer. The latter uses the same, within constant factors, space as
the combined memory of the media's elements and the read-only access to the
adjacency matrix representing the media topology.

Thus, the first two parts of the thesis develop self-organizing media which
minimize bad effects of their distributed nature. The third part addresses a
graph theoretical problem of achieving desired connectivity at the least cost.
It generalizes previous algorithms solving this problem and improves their
complexity.

*Download*: ps, gzipped
ps