Average message complexity for the election problem on graphs I am currently studying the election problem in distributed algorithms. There, I stumpled over one approach to implement a Chang-Roberts-like message extinction algorithm on graphs without requiring a specific topology.

The idea is simple: each initiator starts an echo-algorithm to learn about the leader (so, to find the process with the biggest unique identifier). An initiator adds his unique id to the wave to mark the wave and allow wave extinction: if two waves "hit" each other, the one with the bigger id wins. Now, to my question, which is inspired by this problem but a little bit more abstract.

Given an arbitrary topology and an algorithm like the one described above, is it possible to come up with a model to calculate the average message complexity? I apologize if I missed something obvious to answer this, but it seems to me that I am stuck with computing the best and worst case but cannot come up with an average case description without more knowledge on the actual topology. Is this conclusion true?
I don't know of any results in distributed computing that state bounds on 
average message complexity that are independent of the network topology.

Let's assume you have an algorithm $A$ with average message complexity 
$\Theta(f(n))$, for some function $f(n)$. While such a universal bound 
sounds quite powerful, the problem (as I see it) is that this tells you 
very little about $A$. If someone implemented $A$ for a specific class of 
networks, the $\Theta(f(n))$ bound becomes meaningless, as it is the 
average over all network topologies and unique id assignments, whereas 
worst/best-case bounds would still apply.