| In many distributed systems, such as for example the internet network, ad hoc networks or sensor networks, there are many entities that operate in the system. Their processors are active at any moment and may perform some local computations. Moreover the entities have the ability to communicate with each other to achieve some goals. A simple model of computation, which is supposed to mimic the architecture of those systems, is the distributed model called LOCAL. Algorithms in this model are called distributed.
Most of the known distributed algorithms either work on general graphs, i.e. study the worst cases, or concentrate on a particular family of graphs, such as for example: trees, bounded growth graphs, planar graphs or bounded degree graphs. We want to analyse the performance of distributed algorithms on average graphs. To this end we use an Erdős--Rényi random graph \(G(n,p)\) with independent edges.
We develop techniques to construct very efficient algorithms on random graphs in the distributed model of computation. We will show how to solve efficiently the classical problems from the field of distributed algorithms such as: finding a maximal independent set, finding an approximation of a minimum spanning tree or an approximation of a minimum dominating set.
|
