Autonomous Networks and P2P systems

Researchers

Ph.D. Students

Gunnar Kreitz

Short description

Distributed aggregation

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

Secure aggregation

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 malicious
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
ACCESS: Linneaus excellence centre funded by the Swedish Research Council

Publications

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. [pdf]
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. [pdf.gz]
Decentralized Computation of Threshold Crossing Alerts: Fetahi Wuhib, Mads Dam, Rolf Stadler, and Alexander Clemm; In Proc. DSOM'05. [pdf]
A Generic Protocol for Network State Aggregation: M. Dam, R. Stadler; In Proc. Radiovetenskap och Kommunikation (RVK), 2005. [pdf]
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 [pdf.gz]