| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 129.79 KB | Adobe PDF |
Advisor(s)
Abstract(s)
Determining the size of a network and its diameter
are important functions in distributed systems, as there are a
number of algorithms which rely on such parameters, or at least
on estimates of those values.
The Extrema Propagation technique allows the estimation of
the size of a network in a fast, distributed and fault tolerant
manner. The technique was previously studied in a simulation
setting where rounds advance synchronously and where there is
no message loss.
This work presents two main contributions. The first, is the
study of the Extrema Propagation technique under asynchronous
rounds and integrated in the Network Friendly Epidemic Multicast
(NeEM) framework. The second, is the evaluation of
a diameter estimation technique associated with the Extrema
Propagation. This study also presents a small enhancement to
the Extrema Propagation in terms of communication cost and
points out some other possible enhancements.
Results show that there is a clear trade-off between time and
communication that must be considered when configuring the
protocol—a faster convergence time implies a higher communication
cost. Results also show that its possible to reduce the total
communication cost by more than 18% using a simple approach.
The diameter estimation technique is shown to have a relative
error of less than 10% even when using a small sample of nodes.
Description
Keywords
Aggregation Network size estimation Network diameter Estimation Probabilistic estimation
Pedagogical Context
Citation
LADC - 4th AMERICAN SYMPOSIUM ON DEPENDABLE COMPUTING. Paraíba, Brasil,1-4 September, 2009. "Dependable Computing, 2009. LADC '09. Fourth Latin-American Symposium on". ISBN 978-0-7695-3760-3. pp.33-40
Publisher
Federal University of Campina Grande (UFCG)