<p>I don't know of any results in distributed computing that state bounds on 
<em>average</em> message complexity that are independent of the network topology.</p>

<p>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 <em>and</em> unique id assignments, whereas 
worst/best-case bounds would still apply.</p>

CC BY-SA 3.0
2012-03-19T12:22:14.213Z
I am not a 100% sure if your statement about universal bounds is true. We can get better bounds for many algorithms using specific problem subsets, but are still interested in universal bounds as well. Is there a reason why this shouldn't apply for a distributed algorithm as well?
evnu
CC BY-SA 3.0
2012-03-12T08:37:07.707Z
2012-03-12T08:37:07.707Z
Peter
<p>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.</p>

<p>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.</p>

<p>Given an arbitrary topology and an algorithm like the one described above, is it possible to come up with a model to calculate the <em>average message complexity</em>? I apologize if I missed something obvious to answer this, but it seems to me that I am stuck with computing the <em>best</em> and <em>worst case</em> but cannot come up with an average case description without more knowledge on the actual topology. Is this conclusion true?</p>

CC BY-SA 3.0
2012-03-08T11:00:30.003Z
I guess for calculating the *best* and *worst* case you came up with different graphs, right? If not, I'm overlooking something in your question. If so I guess the answer to your question would be yes, unless you have some notion of "average graph".
Martin B.
CC BY-SA 3.0
2012-03-09T08:55:41.013Z
Yes, the best and worst case are different graphs. I think you are right by requiring some kind of "average graph", which seems useful to be able to compute the average complexity. So I think I'll go with "Yes, you need to know more about the used topologies".
evnu
<dc.distributed-comp><communication-complexity>
Average message complexity for the election problem on graphs
evnu
# Average message complexity for the election problem on graphs

(Asked by: username_0 on 2012-01-23)

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?

**Tags:** dc.distributed-comp, communication-complexity
> **Comments:**
> **username_1**: I guess for calculating the *best* and *worst* case you came up with different graphs, right? If not, I'm overlooking something in your question. If so I guess the answer to your question would be yes, unless you have some notion of "average graph".  
> **username_0**: Yes, the best and worst case are different graphs. I think you are right by requiring some kind of "average graph", which seems useful to be able to compute the average complexity. So I think I'll go with "Yes, you need to know more about the used topologies".  

---

## 1 answers

### Answer by username_2 on 2012-03-12. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: I am not a 100% sure if your statement about universal bounds is true. We can get better bounds for many algorithms using specific problem subsets, but are still interested in universal bounds as well. Is there a reason why this shouldn't apply for a distributed algorithm as well?  

---

