Autonomous Networks and P2P systems
A basic problem in distributed systems is to obtain agreement among a
collection of nodes on some joint value, typically characterized as
a function on input values, each of which is localized to some node.
Examples are consensus, distributed averaging, counting, extremal values,
voting, and step functions as threshold crossing indicators. We are
particularly interested in scalable solutions where the load at each
node or link grows sublinearly with the size of the network, and we are
interested in understanding better which functions can be computed in
a scalable way, under given accuracy and performance constraints.
Existing approaches can be divided into those based on spanning trees,
and those based on iterative agreement (gossiping). We are interested
in comparing these approaches, and in extending them to address new
problems, for instance threshold crossing detection. A topic of particular
interest is to study the effect of node and link failures. Besides
simulation we are interested in analytic results in areas such as
convergence rates, convergence speeds, and behaviour under churn, i.e.
dynamic topology changes due to node failures and joins.
Our achievements so far are:
A proposal for a spanning tree state aggregation protocol, GAP
An extension of GAP to decentralized threshold detection, TCA-GAP
An adaptation and correctness analysis of gossiping extended to
networks with node failures, G-GAP
A new research topic is the development of aggregations protocols that
are secure in the sense of e.g.:
Privacy: No local information is leaked as part of state aggregation,
even in the presence of malicious nodes
Integrity and intrusion tolerance: A good approximation of the correct
aggregate is computed, irrespective of some portion of nodes being
Intrusion detection: We are interested in sufficient and necessary
conditions for which misbehaving or faulty nodes can be identified.
Modelling of P2P systems
We study techniques for the specification and verification
of peer-to-peer algorithms, such as the stabilization and
maintenance protocols of the Chord overlay network. Approaches
include bisimulation proofs of pi-calculus models, I/O automata
and temporal logic (TLA).
Projects and Funding
4WARD: EU FP7 project on future internet
Linneaus excellence centre funded by the Swedish Research Council
- Decentralized Detection of Global Threshold Crossings Using Aggregation Trees
F. Wuhib, M. Dam, R. Stadler, A. Clemm
- To appear in Computer Networks
- Robust Monitoring of Network-Wide Aggregates Using Gossiping
Fetahi Wuhib, Mads Dam, Rolf Stadler, Alexander Clemm
- In Proc. Integrated Management (IM) 2007.
Verification of Peer-to-peer Algorithms: A Case Study
- Rana Bakhshi, and Dilian Gurov
- In Proceedings of: MTCoord'06
Electronic Notes in Theoretical Computer Science, vol. 181,
pp. 35-47, 2007.
- Decentralized Computation of Threshold Crossing Alerts
Fetahi Wuhib, Mads Dam, Rolf Stadler, and Alexander Clemm
In Proc. DSOM'05.
A Generic Protocol for Network State Aggregation
M. Dam, R. Stadler
In Proc. Radiovetenskap och Kommunikation (RVK), 2005.
Verifying a Structured Peer-to-peer Overlay Network: The Static Case
- Johannes Borgström, Uwe Nestmann, Luc Onana Alima, and Dilian Gurov
- In Proceedings of: Global Computing'04
Lecture Notes in Computer Science, vol. 3267, pp. 250-265, 2004