Gathering in dynamic ring

31^st May 2018, 14:00
Dr Giuseppe Di Luna
Aix-Marseille University

Abstract

Thanks to wireless communication technologies networks that continuously and frequently change their topologies are a reality. An example is a p2p network made with mobile smartphones. Such networks can be modelled using the formalism of time-varying graphs. The study of time-varying graphs has been, and it still is, a hot research topic.

In this talk we will focus on the specific application of Gathering. In the Gathering problem a set of mobile agents, initially dispersed on arbitrary locations, has to regroup on the same node. We consider weak agents that have only local view and are oblivious of network changes. We will discuss the Gathering problem on dynamic rings, investigating how and when our agents can solve the problem. We will show that the agreement on common orientation and the ability to detect agents crossing on edges are key assumptions that modify the solvability landscape of Gathering.