bild
School of
Computer Science
and Communication
KTH / CSC / TCS / projects / Autonomous networks

Autonomous Networks and P2P systems

Researchers

Ph.D. Students

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]
Published by: Mads Dam <mfd@kth.se>
Updated 2008-03-31