Item

Abstract

We study distributed systems, with a particular focus on graph problems and fault
tolerance.
Fault-tolerance in a microprocessor or even System-on-Chip can be improved by using
a fault-tolerant pulse propagation design. The existing design TRIX achieves this goal
by being a distributed system consisting of very simple nodes. We show that even in
the typical mode of operation without faults, TRIX performs significantly better than a
regular wire or clock tree: Statistical evaluation of our simulated experiments show that
we achieve a skew with standard deviation of O(log log H), where H is the height of the
TRIX grid.
The distance-r generalization of classic graph problems can give us insights on how
distance affects hardness of a problem. For the distance-r dominating set problem, we
present both an algorithmic upper and unconditional lower bound for any graph class
with certain high-girth and sparseness criteria. In particular, our algorithm achieves a
O(r · f(r))-approximation in time O(r), where f is the expansion function, which correlates
with density. For constant r, this implies a constant approximation factor, in constant
time. We also show that no algorithm can achieve a (2r + 1 − δ)-approximation for any
δ > 0 in time O(r), not even on the class of cycles of girth at least 5r. Furthermore, we
extend the algorithm to related graph cover problems and even to a different execution
model.
Furthermore, we investigate the problem of packet forwarding, which addresses the
question of how and when best to forward packets in a distributed system. These packets
are injected by an adversary. We build on the existing algorithm OED to handle more
than a single destination. In particular, we show that buffers of size O(log n) are sufficient
for this algorithm, in contrast to O(n) for the naive approach.