DYNAMO 2008
2nd Training School on Algorithmic Aspects of Dynamic Networks
Content of the lectures
Online Algorithms for Network Problems by Susanne Albers (Freiburg University)
In this lecture series we will study online problems that arise in large
communication networks. The design and analysis of algorithms for these
problems has received considerable research interest over the past
years. In an online problem the input arrives incrementally over time.
Whenever a new input portion comes in, an algorithm has to react and
compute partial output not knowing future input. This lecture series
will focus on a number of fundamental and challenging online problems.
These include network design, memory management in web servers and
browser, resource management in routers and switches, algorithmic
problems arising in network protocols as well as broadcast and data
aggregation problems.
Peer-to-Peer by Christian Scheideler (Technical University of Munich) and Stefan Schmid (ETH Zurich)
This lecture will be split into two parts, one dedicated to the fundamental aspects of P2P, and the other dedicated to some practical aspects of systems.
First, this series of lectures provides an introduction to basic notation in graph theory as well
as basic network topologies and basic parameters to measure the quality of
network topologies.
Afterwards, general concepts are presented for overlay networks for distributed
systems over the Internet. We will discuss concepts for supervised overlay
networks (the network topology is managed by a supervisor) as well as
peer-to-peer overlay networks (the network topology is managed by its peers).
Central techniques presented in the course are consistent hashing, the
continuous-discrete approach, and skip graphs.
Applications of the principles developed in the first part of the lecture will be presented, including present aspects of Gnutella, BitTorrent, Kad, etc.
Game Theory - mechanisms by Elias Koutsoupias (University of Athens)
This lecture will address some fundamental problems at the
intersection of computer science and game theory and in particular
mechanisms for selfish environments. Traditional algorithm design
assumed that either the components of the system are coordinating
towards a common goal or they are malicious trying to harm the system.
The onset of internet and web computing raised problems in which the
users are neither cooperative nor malicious but they have their own
objective and act selfishly. The traditional game-theoretical approach
to these problems is mechanism design. We will study algorithmic
issues of classical mechanism design and we will expand on directions
brought forward by the computer science point of view: online
mechanism design, coordination mechanisms, cost sharing protocols.
Graph Searching by Fedor Fomin (University of Bergen)
Graph searching is a kind of game where one part is a set of vicious
mobile agents, called robbers (or fugitives), that
hide in a graph representing the network, and the other part is a
number of ``virtuous" agents, called cops (or searchers), that move systematically in the graph and aim at capturing the robbers. The game may vary significantly according to
the capabilities of the robbers and the cops in terms of relative
speed, sensor capabilities, visibility, etc. The variants are either application driven motivated by problems in practice, or are inspired by
foundational issues in Computer Science and Discrete Mathematics.
In this talk we discuss some basic models and properties of graph searching.
Self-Stabilizing and Self-Organizing Dynamic Networks by Shlomi Dolev (Ben-Gurion University of the Negev)
Self-Stabilizing dynamic networks converge to operate as required in
the presence
of dynamic changes. Self-organizing algorithms are a class of
self-stabilizing dynamic algorithms that converge in sub-linear time
and overcome network changes even faster.
The lecture will summarize several recent self-organizing algorithms
including ones
that are based on:
(a) defining virtual communication infrastructure based on geographic
polygons, (b) defined on the fly hyperlinks, and (c) spanders which
are spanning expanders.
Algorithms for the IP traffic by Philippe Robert (INRIA Rocquencourt)
In this talk, we will discuss the problem of designing on line algorithms capable of, for example, estimating the various characteristics of the IP traffic or of detecting attacks. If, for the estimation, classical algorithms can address these problems, it is often the case that these algorithms cannot reasonably cope with the order of magnitude of the IP trafic resulting in bad performances (if not no performance at all). Through some examples, we will review some of the key aspects of these questions and how they can, sometimes, be solved via some simple mechanisms provided that the intrisic variability of the IP trafic has been taken into account. Specifically, counting, estimating statistics and attack detection problems will be discussed.
This talk introduces network coding, an emerging area that re-examines
fundamental principles of network information flow. The main idea is that
we allow intermediate nodes in a network to not only forward but also to
process the incoming information flows. The network code is the set of the
operations that intermediate nodes perform. This modern application of
coding to the theory and practice of communication networks raises novel
and exciting research problems, and promises to have a significant impact
in diverse areas that include multicasting, network monitoring, reliable
delivery, resource sharing, efficient flow control and security.