Helsinki Algorithms Seminar: "Certification of Compact Low-Stretch Routing Schemes" Alkida Balliu
Weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design
Map © OpenStreetMap. Some rights reserved.
Speaker:
Alkida Balliu
Title:
Certification of Compact Low-Stretch Routing Schemes
Abstract:
On the one hand, the correctness of routing protocols in networks is an issue of utmost importance for guaranteeing the delivery of messages from any source to any target. On the other hand, a large collection of routing schemes have been proposed during the last two decades, with the objective of transmitting messages along short routes, while keeping the routing tables small. Regrettably, all these schemes share the property that an adversary may modify the content of the routing tables with the objective of, e.g., blocking the delivery of messages between some pairs of nodes, without being detected by any node.
In this work, we present a simple certification mechanism which enables the nodes to locally detect any alteration of their routing tables. (https://arxiv.org/abs/1704.06070)
**
Helsinki Algorithms Seminar is a weekly meeting of researchers in the Helsinki area interested in the art of algorithms and algorithm design, broadly interpreted to cover both theoretical ideas and algorithm engineering on concrete computing platforms. In most cases we have a presentation prepared for each meeting to communicate an idea, a recent result, work-in-progress, or demo, but this should not be at the expense of discussion and simply having fun with algorithms.
Our affiliations are with Aalto University and the University of Helsinki, and accordingly our activities alternate between the Otaniemi Campus of Aalto University and the Kumpula Campus of University of Helsinki, catalyzed by the Helsinki Institute for Information Technology HIIT, under the Algorithmic Data Analysis (ADA) programme.
For the season programme, please see the seminar webpage.