In many distributed systems, such as for example internet network, ad hoc networks or sensor networks, there are many entities which operate in the system. Their processors are active at any moment and may perform some local computations. Moreover the entities have ability to communicate with each other to achieve some goals. A theoretical model of computation which uses the architecture of those systems is so--called distributed LOCAL model. Algorithms in this model are called distributed.

Interesting questions arise when we ask about the performance of the classical distributed algorithms in the average case. So far the studies in this field evolved around constructing algorithms which with probability close to 1 are very efficient on a random input. In contrast, we want to analyse the performance of known algorithms in this setting. We will present some partial results and concentrate on interesting open questions which appear naturally in the context of distributed algorithms on random graphs. We will mention problems of constructing: the minimum spanning tree, colouring, maximal independent set.