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?