research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Incollection
Entered by:
TitleComputing in Dynamic Networks
Bibtex cite IDRACTI-RU1-2015-5
Booktitle Computational Network Theory: Theoretical Foundations and Applications, First Edition
Year published 2015
Chapter 6
Publisher Wiley-VCH Verlag GmbH & Co. KGaA
Note To appear
Keywords dynamic graph,mobile computing,distributed computing,distributed algorithm,worst-case dynamicity,adversarial schedule,temporal connectivity,counting,naming,information dissemination,optimal protocol
In this chapter, our focus is on computational network analysis from a theoretical point of view. In particular, we study the \emphpropagation of influence and computation in dynamic distributed computing systems. We focus on a \emphsynchronous message passing communication model with bidirectional links. Our network dynamicity assumption is a \emphworst-case dynamicity controlled by an adversary scheduler, which has received much attention recently. We first study the fundamental \emphnaming and \emphcounting problems (and some variations) in networks that are \emphanonymous, \emphunknown, and possibly dynamic. Network dynamicity is modeled here by the \emph1-interval connectivity model, in which communication is synchronous and a (worst-case) adversary chooses the edges of every round subject to the condition that each instance is connected. We then replace this quite strong assumption by minimal \emphtemporal connectivity conditions. These conditions only require that \emphanother causal influence occurs within every time-window of some given length. Based on this basic idea we define several novel metrics for capturing the speed of information spreading in a dynamic network. We present several results that correlate these metrics. Moreover, we investigate \emphtermination criteria in networks in which an upper bound on any of these metrics is known. We exploit these termination criteria to provide efficient (and optimal in some cases) protocols that solve the fundamental \emphcounting and \emphall-to-all token dissemination (or \emphgossip) problems. Finally, we propose another model of worst-case temporal connectivity, called \emphlocal communication windows, that assumes a fixed underlying communication network and restricts the adversary to allow communication between local neighborhoods in every time-window of some fixed length. We prove some basic properties and provide a protocol for counting in this model.
Michail, Othon
Chatzigiannakis, Ioannis
Spirakis, Paul
MCS15-CNT.pdf (main file)
Publication ID1078