Tag Archives: Distributed algorithms

12/12/2017 – Talk by Euripides Markou

Title:Exploration and graph searching problems in networks
Time: 13:00
Location: Meeting room, Building Zeta
Type: Research Result
Speaker: Talk by Euripides Markou
Abstract: In this seminar we will discuss different problems in networks: The Black Hole Search problem in synchronous trees and graphs; the Black Hole Search problem and the rendezvous problem for weak agents (e.g., memoryless). We will show algorithms and discuss impossibility results, new directions and open problems.
Short bio: Euripides Markou is an Assistant Professor at the University of Thessaly. He got his Ph.D. in Computer Science in 2003 from the National University of Athens. His area of interest are in the field of distributed and geometric computing.

28/01/2015 – Workshop on mobile agents and robots

Location

January, 28th 9.30-12.30, Room 1, Bulding Z, Campus Scientifico

Program

9.30-9.35 Workshop presentation.

9.35-10.20 Prof. Evangelos Kranakis Carleton University, Ottawa, Canada: “Evacuating Robots from an Unknown Exit in a Disk”.

Consider k mobile robots inside a circular disk of unit radius. The robots are required to evacuate the disk through an unknown exit point situated on its boundary. We assume all robots having the same (unit) maximal speed and starting at the centre of the disk. The robots may communicate in order to inform themselves about the presence (and its position) or the absence of an exit. The goal is for all the robots to evacuate through the exit in minimum time.

We consider two models of communication between the robots: in non-wireless (or localcommunication model robots exchange information only when simultaneously located at the same point, and wireless communication in which robots can communicate one another at any time. We study the following question for different values of k: what is the optimal evacuation time for k robots? We provide algorithms and show lower bounds in both communication models for k=2 and k=3 thus indicating a difference in evacuation time between the two models. We also obtain almost-tight bounds on the asymptotic relation between evacuation time and team size, for large k. We show that in the local communication model, a team of k robots can always evacuate in time 3 + (2Π)/k, whereas at least 3 + (2Π)/k – O(k^{-2}) time is sometimes required. In the wireless communication model, time 3 + Π/k + O(k^{-4/3}) always suffices to complete evacuation, and at least 3+ Π/k is sometimes required. This shows a clear separation between the local and the wireless communication models.

 

10.25-11.10 Prof. Danny Krizanc Wesleyan University, Middletown, CT, U.S.A.: “The Dynamic Map Visitation Problem: Foremost Coverage of Time-varying Graphs.”

We consider the Dynamic Map Visitation Problem (DMVP), in which a team of agents must visit a collection of critical locations as quickly as possible, in an environment that may change rapidly and unpredictably during the agents’ navigation. We apply recent formulations of time-varying graphs (TVGs) to DMVP, shedding new light on the computational hierarchy R ⊃ B ⊃ P of TVG classes by analyzing them in the context of graph navigation. We provide hardness results for all three classes, and for several restricted topologies, we show a separation between the classes by showing severe inapproximability in R, limited approximability in B, and tractability in P. We also give topologies in which DMVP in R is fixed parameter tractable, which may serve as a first step toward fully characterizing the features that make DMVP difficult.

11.10-11.40 coffee break (registration is required).

11.40-12.10 PhD students demos with LEGO MINDSTORMS Robots.

15/10/2013 – Talk by Euripides Markou

Title: Distributed Computing: An algorithmic theory framework for mobile agents and some interesting problems.
Time: 14:00
Location: Meeting room
Type: Tutorial
Speaker: Euripides Markou – University of Thessaly, Lamia, Greece
Abstract:

We focus on distributed algorithms for mobile agents. We define a mobile agent and discuss basic properties and models. We present some interesting problems in the area. We discuss advantages of using mobile agents as opposed to static agents and also discuss security issues. We focus on the gathering problem and present recent algorithms and related work.