Distributed Mobile Computing in unsafe environments
At an abstract level, a distributed mobile system can be described as a collection of autonomous mobile entities located in a spatial universe. The entities have bounded storage and processing capabilities, exhibit the same behavior (i.e., execute the same protocol), and can move in their universe. Each entity has its own local clock and acts completely asynchronously with respect to the other entities. Each entity is autonomous in the sense that it has its own local memory and is able to perform computation. Typical examples of distributed mobile systems: a system of mobile software agents operating in a network, and a system of autonomous mobile robots whose spatial universe is the plane. In this project we consider the situation when the universe on which the entities operate is possibly unsafe, study the basic limitations to a correct and efficient operation of the entities, and develop algorithmic tools which can be successfully employed by the entities to overcome those limitations.
1) Black Holes: Locating harmful hosts.
In current and future networked environments supporting mobile software agents, a pressing security problem is the problem of protecting the agents from host attacks (i.e., harmful processes stored at visited sites). In this project we are concerned with the problem of operating in an environment that contains highly harmful items, located at some nodes, which destroy any incoming agents. We are interested in constructing software agents capable, as a team, to unambiguously and with as few losses as possible determine the location of the harmful items; a rescue activity can then take place once the location phase has been completed.
Some References
B. Balamohan, S. Dobrev, P. Flocchini, N. Santoro.
Exploring an unknown dangerous graph with a constant number of tokens. Theoretical Computer Science, 610:169-181, 2016.S. Dobrev, P. Flocchini, Rastislav Kralovic, N. Santoro.
Exploring an Unknown Dangerous Graph Using Tokens, Theoretical Computer Science, 472: 28-45, 2013.P. Flocchini, D. Ilcinkas, N. Santoro.
Ping pong in dangerous graphs: optimal black hole search with pebbles, Algorithmica 62 (3-4), pag. 1006-1033, 2012.S. Dobrev, P. Flocchini, G. Prencipe, N. Santoro
Mobile search for a black hole in an anonymous ring. Algorithmica, 48(1): 67-90, 2007.S. Dobrev, P. Flocchini, G. Prencipe, N. Santoro
Searching for a Black Hole in Arbitrary Networks: Optimal Mobile Agent Protocols. Distributed Computing, 19(1), 1-19, 2006.S. Dobrev, P. Flocchini, R. Kralovic, G. Prencipe, P. Ruzicka, N. Santoro
Black hole search in common interconnection networks , Networks , vol 47(2), 61-71, 2006.S. Dobrev, P. Flocchini, N. Santoro.
Cycling through a dangerous network: a simple efficient strategy for black hole search, Proc. of 26th International Conference on Distributed Computing Systems (ICDCS 2006).S. Dobrev, P. Flocchini, N. Santoro
Improved bounds for optimal black hole search in a network , In Proc. of 11st Int. Symposium on Structural Information and Communication Complexity (SIROCCO 2004)
2) Intruders: Surrounding harmless intruders.
An intruder is an alien but harmless process that moves on the network to sites unoccupied by the system's agents; the task of the agents is to immobilize it (i.e., to surround it occupying all the neighbours of the site where it currently resides). In this project we are concerned with the design of efficient algorithms for surrounding the intruders. In the current research there exist some solutions for specific networks and in the case of a single intruder; the research is open to develop new solutions in more general settings
Some References
L. Barriere, P. Flocchini, F. V. Fomin, P. Fraigniaud, N. Nisse, N. Santoro, D.M. Thilikos.
Connected Graph Searching, Information and Computation, 219: 1-16, 2012.P. Flocchini, M.J. Huang, F.L. Luccio.
Decontamination of hypercubes by mobile agents, Networks, 52(3), 167-178, 2008.P. Flocchini, F.L. Luccio, M. Huang
Decontamination of chordal rings and tori using mobile agents. International Journal of Foundation of Computer Science, 18(3), 547-564, 2007.
3) Mobile Robots: Coordinating a team of mobile robots.
The focus of this research is the study of the issues related to the development of a software "SWAT team” composed of autonomous mobile robots operating in a plane which contains dangerous objects. This setting models situations where mines are dispersed on the terrain, and the robots have either the task of finding them, or to avoid them to accomplish some global tasks. Also in this case, the objective is to minimize the loss of robots. This issue has become increasingly more important because of the current trend in robotic research, both from engineering and behavioral viewpoints, to move away from the design and deployment of few problem-specific robots, towards the design and use of a large number of generic robots which have minimal physical capabilities.
Some References
G.A. Di Luna, P. Flocchini, S.G. Chaudhuri, F. Poloni, N. Santoro, G. Viglietta.
Mutual visibility by luminous robots without collisions. Information and Computation, in press.S. Das, P. Flocchini, G. Prencipe, N. Santoro, M. Yamashita.
Autonomous mobile robots with lights Theoretical Computer Science, 609: 171-184, 2016.S. Das, P. Flocchini, G. Prencipe, N. Santoro, M. Yamashita.
Forming Sequences of Geometric Patterns with Oblivious Mobile Robots. Distributed Computing, 28(2): 131-145, 2015.P. Flocchini.
Computations by Luminous Robots. 14th International Conference on Ad-hoc, Mobile, and Wireless Networks, (ADHOC-NOW), 238-252, 2015.M. Cieliebak, P. Flocchini, G. Prencipe, N. Santoro.
Distributed Computing by Mobile Robots: Gathering, SIAM Journal on Computing, 41(4): 829-879, 2012.P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer
Gathering of asynchronous mobile robots with limited visibility, Theoretical Computer Science , vol 337: 1-3, 147-168, 2005.