MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Time Complexity of Link Reversal Routing

Matthias Függer
Max-Planck-Institut für Informatik - D1
Talk

Matthias Függer received his M.Sc. (2006) and his PhD (2010) in computer engineering from TU Wien, Austria. He is currently a post-doctoral researcher at LIX, Ecole polytechnique. His main research interest is the formal study of the fundamentals of computationally extremely restricted distributed devices manmade or models of natural systems). Specifically this includes (fault-tolerant) distributed algorithms in hardware and biology.
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
MPI Audience
English

Date, Time and Location

Thursday, 14 August 2014
13:00
30 Minutes
E1 4
019
Saarbrücken

Abstract

Link reversal is a versatile algorithm design paradigm, originally
proposed by Gafni and Bertsekas in 1981. The algorithms operate on
graphs, using local information only, to reverse some of a node's
incident links. Applications are in routing, mutual exclusion, leader
election, and resource allocation.

Although these algorithms are well-known, there have been only
preliminary results on time complexity, even for the simplest link
reversal algorithm for routing, called Full Reversal. Charron-Bost et
al. introduced a generalization, called LR, that includes Full
Reversal, and the more advanced Partial Reversal, as special cases.

In this talk an exact expression for the time complexity of LR is
presented. The expression is stated in terms of simple properties of
the initial graph. Having the exact formulas provides insight into the
behavior of Full and Partial Reversal on specific graph families.

Contact

Christoph Lenzen
--email hidden
passcode not visible
logged in users only

Christoph Lenzen, 08/11/2014 15:16
Christoph Lenzen, 08/11/2014 11:07
Christoph Lenzen, 08/11/2014 10:38 -- Created document.