Actively Dynamic Networks

14^th October 2021, 13:00
Paul Spirakis

Abstract

We discuss here systems of (distributed) entities that can actively modify their communication network. We focus on two broad issues : (a) distributed algorithms that can reconfigure a network to carry out a given task efficiently, (b) creating a desired network starting from a single entity and allowing entities (nodes) to self-replicate (and thus expand) the network and its size. Such issues lead to a natural balance between how fast (time) and how efficiently (number of link activations, number of excess links to be eventually deleted) a target network can be generated. Our results include lower bounds and algorithms that try to balance speed and efficiency.