# Item

ITEM ACTIONSEXPORT

Released

Thesis

#### Pulse Propagation, Graph Cover, and Packet Forwarding

##### External Resource

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Wiederhake, B. (2022). Pulse Propagation, Graph Cover, and Packet Forwarding. PhD Thesis, Universität des Saarlandes, Saarbrücken. doi:10.22028/D291-36608.

Cite as: https://hdl.handle.net/21.11116/0000-000A-CEBE-9

##### 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.

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.