Gene (Yevgeny Y.) ITKIS
PhD Thesis
Boston University, Graduate School, 1996

Major Professor: Leonid A. Levin, Professor of Computer Science


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