|
Published Articles >> Table of Contents >> Abstract
International Conference on Dependable Systems and Networks (DSN'06)
pp. 166-178
Eventual Leader Election with Weak Assumptions on Initial Knowledge, Communication Reliability, and Synchrony
Antonio Fernandez, LADyR, GSyC, Universidad Rey Juan Carlos, 28933 M´ostoles, Spain
Ernesto Jimenez, EUI, Universidad Polit´ecnica de Madrid, 28031 Madrid, Spain
Michel Raynal, IRISA, Universite de Rennes, Campus de Beaulieu 35 042 Rennes, France
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DSN.2006.34
Send link to a friend
| Abstract |
|
This paper considers the eventual leader election problem
in asynchronous message-passing systems where an arbitrary
number t of processes can crash (t \lt n, where n
is the total number of processes). It considers weak assumptions
both on the initial knowledge of the processes
and on the network behavior. More precisely, initially, a
process knows only its identity and the fact that the process
identities are different and totally ordered (it knows neither
n nor t). Two eventual leader election protocols are presented.
The first protocol assumes that a process also knows
the lower bound on the number of processes that do not
crash. This protocol requires the following behavioral properties
from the underlying network: the graph made up of
the correct processes and fair lossy links is strongly connected,
and there is a correct process connected to t - f
other correct processes (where f is the actual number of
crashes in the considered run) through eventually timely
paths (paths made up of correct processes and eventually
timely links). This protocol is not communication-efficient
in the sense that each correct process has to send messages
forever. The second protocol is communication-efficient: after
some time, only the final common leader has to send
messages forever. This protocol does not require the processes
to know, but requires stronger properties from the
underlying network: each pair of correct processes has to
be connected by fair lossy links (one in each direction), and
there is a correct process whose output links to the rest of
correct processes have to be eventually timely. This protocol
enjoys also the property that each message is made up
of several fields, each of which taking values from a finite
domain.
|
 Additional Information
|
Citation:
Antonio Fernandez, Ernesto Jimenez, Michel Raynal,
"Eventual Leader Election with Weak Assumptions on Initial Knowledge, Communication Reliability, and Synchrony,"
dsn,
pp. 166-178,
International Conference on Dependable Systems and Networks (DSN'06),
2006
|
|
