[an error occurred while processing this directive]




<table width="100%" border="0" cellpadding="0" cellspacing="0" style="border-collapse: collapse" bordercolor="#111111">
<tr>
<td align="left"> </td><td align=right><font class=title>Publication</font></td><td width=2></td>
</tr>
<tr>
<td valign="top" align=right colspan=3><img src="../pics/linetitle.gif" width="280" height="2"></td>
</tr>
<tr>


<td colspan=2><br>

<p align=center><b>Scalable Leader Election</b>
<br>by Valerie King and Erik Vee</p>
<p>
<b>Abstract</b>
<p>
In the leader election problem, there are n processors of which (1- b)
n are good. The problem is to design a distributed protocol to elect a
good leader from the set of all processors. In this paper, we present
a scalable leader election protocol. Our protocol is scalable in the
sense that each good processor sends and processes a number of bits
which is only polylogarithmic in n.  (We assume no limit on the number
of messages sent by bad processors.)  For b<1/3, our protocol elects a
good leader with constant probability and ensures that a 1-o(1)
fraction of the good processors know this leader.
<p>
To the best of our knowledge, we present the first leader election
protocol which ensures that each good processor sends and processes a
sublinear number of bits.  Having reduced the problem of leader
election to one of informing all good processors of a bit held by
1-o(1) fraction of good processors, we conjecture that the solution to
this problem is not possible within polylogarithmic message bounds.
<p>
Our techniques can be used to provide scalable solutions to Byzantine
agreement and other problems.
<p>
<BR><BR><BR><BR><BR><BR><br>

[an error occurred while processing this directive]