Counting in Dynamic Networks

11^th February 2014, 16:00 Ashton Lecture Theater
Dr Ioannis Chatzigiannakis
Computer Technology Institute & Press "Diophantus"
University of Patras Campus
Greece

Abstract

Counting is a fundamental problem of every distributed system as it represents a basic building block to implement high level abstractions. In this talk we focus on synchronous distributed systems where the network topology constantly changes (dynamic network). Changes are driven by a powerful adversary that can look at internal process states and add and remove edges in order to contrast the convergence of the algorithm to the correct count. We look into the case where the processes belonging to the distributed system may be completely anonymous (i.e., they execute identical code) or they may be identified through a set of labels L={1, 2 ... k} (with 1 < k < n). We present a set of counting algorithms that are based on a technique that mimics an energy-transfer between network nodes.