5
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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". $\endgroup$
    – Martin B.
    Commented Mar 8, 2012 at 11:00
  • $\begingroup$ 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". $\endgroup$
    – evnu
    Commented Mar 9, 2012 at 8:55

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – evnu
    Commented Mar 19, 2012 at 12:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.