Download report - Distributed Computing Group

Chapter 1
Introduction
1.1
Motivation
A distributed computing environment can often be described with a graph,
where the vertices represent the computing devices and the edges represent the
connections between them. One first approach to solve a problem on such a
graph is to gather all necessary information at a single device, compute the
solution, and send it back to the nodes. However, for many problems, we can
achieve much better performance if each vertex computes the solution based on
its local view.
An algorithm that computes the solution (or an approximation) based on
partial information of the problem is called local. Developing and analyzing
such local algorithms is a non-trivial task, mostly intuit. Such algorithms are
often ’executed’ with paper and pencil on small graphs to verify the correctness
or understand certain properties. This paperwork is very vulnerable to errors
and very slow. Additionally it is not possible to execute huge simulations with
1000s of nodes by hand. In order to facilitate this work, we built this simulation
tool.
1.2
Assignment
The task of this thesis is to develop a simulation framework for local algorithms
that runs on graphs. We are looking for a generic tool that allows us to quickly
implement algorithms and run it on several distinct graphs, rendering unnecessary the tedious and error-prone paper and pencil work. As we want to simulate
the algorithms not only on small graphs of about 10 to 100 nodes but also on
graphs of the size of 10’000s or even 100’000s of nodes, performance is also an
important issue.
To test the algorithms in a more realistic model we want the algorithms not
only to run on static graphs but also in a dynamic environment. Another important point is to have an easy way of specifying the graphs and their behavior.
This behavior could be the mobility of the nodes, the connectivity of the graph
and so on. We want the framework to allow the user to specify the environment in a plug-in-style where one can run the same algorithm with different
configurations by combining different behavior models.
5