English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Pulse Propagation, Graph Cover, and Packet Forwarding

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

Item is

Files

show Files

Locators

show
hide
Description:
-
OA-Status:
Green

Creators

show
hide
 Creators:
Wiederhake, Ben1, Author           
Lenzen, Christoph1, Advisor           
Mehlhorn, Kurt1, Referee           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2022-02-1420222022
 Publication Status: Issued
 Pages: 83 p.
 Publishing info: Saarbrücken : Universität des Saarlandes
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: Wiederhakephd2021
DOI: 10.22028/D291-36608
URN: nbn:de:bsz:291--ds-366085
Other: hdl:20.500.11880/33316
 Degree: PhD

Event

show

Legal Case

show

Project information

show

Source

show