|
Progress - Overlay Networks - Decentralized Aggregation
As computer networks increase in size, become more heterogenous and span
greater geographic distances, applications must be designed to cope with
the very large scale, poor reliability, and often, with the extreme dynamism
of the underlying network.
Aggregation is a key functional building block for
such applications: it refers to a set of functions that provide each
individual node with access to statistical information about distributed
data, in order to simplify the task of controlling, monitoring and optimizing
distributed applications.
Examples of aggregate values that can be obtained include network size, total
free storage, maximum load, average uptime, location and description of hotspots,
etc.
Simple aggregation functions can be used as building blocks to support more
complex protocols. For example, the knowledge of the average load in a system
can be exploited to implement near-optimal
load-balancing
schemes [JMB04].
So far, the BISON project has developed two decentralized aggregation protocols:
OverStat and T-Rank.
OverStat is a gossip-based decentralized protocol aimed at computing aggregate
functions such as average, generalized means (including harmonic, quadratic and
geometric), sums and products, counting, extremal values, variance and other moments.
The main characteristics of OverStat are:
- full decentralization: all nodes participate in the
protocol in a "democratic" way.
- extreme robustness:
up to 75% of the nodes can fail during the execution of a protocol
instance
- scalability:
the rate of convergence towards the correct aggregate value is
independent of network size.
Two papers have been published so far: one on ICDCS'04 focusing on the
theoretical
properties
of the protocol [JM04] and another in DSN'04
on more practical
aspects
[MJB04a].
A journal version of the two papers has been accepted for publication in
ACM TOCS (Transactions on Computer Systems).
Some of the security aspects related to aggregation have been discussed
in a Technical Report of the University of Bologna [JMB03].
T-Rank is aimed at computing rank-based statistical functions;
over the set of values hosted by nodes. This, combined with the
counting function of OverStat can provide the median and any
percentile of the distribution.
T-Rank starts from an ordered topology built by
T-Man, and builds up the position
of the node in such topology by discovering long-distance links (fingers).
The resulting protocol is characterized by:
- extreme robustness: up to 30% of the nodes may fail
during the execution of the protocol
- scalability: the number of steps needed to complete
the protocol grows logarithmically with the size of the network.
The T-Rank protocol is presented in a technical report
[MJB04b] (submitted for publication).
Both OverStat and T-Rank have been simulated using
Peersim.
The code for reproducing our results is available here:
- JMB04
-
Márk Jelasity, Alberto Montresor, and Ozalp Babaoglu.
A modular paradigm for building self-organizing peer-to-peer
applications.
In Giovanna Di Marzo Serugendo, Anthony Karageorgos, Omer F. Rana,
and Franco Zambonelli, editors, Engineering Self-Organising Systems:
Nature-Inspired Approaches to Software Engineering, number 2977 in Lecture
Notes in Artificial Intelligence, pages 265-282. Springer-Verlag, April
2004.
[PDF],
[Bibtex].
- JM04
-
Márk Jelasity and Alberto Montresor.
Epidemic-style proactive aggregation in large overlay networks.
In Proceedings of the 24th International Conference on
Distributed Computing Systems (ICDCS'04), pages 102-109, Tokyo, Japan,
March 2004. IEEE Computer Society.
[PDF],
[Bibtex].
- MJB04a
-
Alberto Montresor, Márk Jelasity, and Ozalp Babaoglu.
Robust aggregation protocols for large-scale overlay networks.
In Proceedings of the 2004 International Conference on
Dependable Systems and Networks (DSN'04), pages 19-28, Florence, Italy,
June 2004. IEEE Computer Society.
[PDF],
[Bibtex].
- JMB03
-
Márk Jelasity, Alberto Montresor, and Ozalp Babaoglu.
Towards secure epidemics: Detection and removal of malicious peers in
epidemic-style protocols.
Technical Report UBLCS-2003-14, University of Bologna, Department of
Computer Science, Bologna, Italy, November 2003.
[PDF],
[Bibtex].
- MJB04b
-
Alberto Montresor, Márk Jelasity, and Ozalp Babaoglu.
Decentralized ranking in large-scale overlay networks.
Technical Report UBLCS-2004-18, University of Bologna, Department of
Computer Science, Bologna, Italy, December 2004.
[PDF],
[Bibtex].
- JKvS04
-
Márk Jelasity, Wojtek Kowalczyk, and Maarten van Steen.
An approach to massively distributed aggregate computing on
peer-to-peer networks.
In Proceedings of 12th Euromicro Conference on Parallel,
Distributed and Network based Processing (PDP'04), Coruna, Spain, February
2004.
[PDF],
[Bibtex].
|