# Special Track on "Distributed Computing with Mobile Agents"

The concept of Mobile Agents in Distributed Computing has been studied a lot, especially during the last 15 years. A mobile agent is an autonomous, goal-oriented software entity that can migrate from one host to the next, while executing its orders and interacting with the environment. Mobile agents have proved to be a powerful tool for designing and analyzing distributed algorithms for applications in network maintenance, electronic commerce, robotic exploration, wireless mobile ad-hoc networks, and networks of mobile sensors.

Although many applications one has in mind for mobile agents can generally be solved by more traditional distributed computing approaches (i.e., message passing), often the use of mobile agents offers a number of advantages including efficiency, fault-tolerance, flexibility and ease of use. Many algorithmic models for the agents (usually modelled
as automata) and their working environment have appeared in the
literature in an effort to study and evaluate theoretically and also
practically the above claims in the exploration of an unknown and
possibly hostile environment. The complexity and computability of more
basic tasks have also been studied, like the gathering of agents at a
point, the discovering of harmful nodes or agents, building a map or
verifying some global property of the environment etc.

The goal of this session is to bring together researchers working in this area in order to present their work and exchange new ideas and results, to identify new outstanding open problems and to foster new collaborations. Apart from regular submissions and presentations we plan to have a couple of invited talks on current research topics and open problems. We encourage the participation of PhD students and post-doctoral fellows willing to be exposed to important problems in this growing field.

The topics of the session focus on the algorithmic aspects in mobile agent computing and include (but are not limited to):

Topics of Interest

• Distributed algorithms, computability and complexity

• Fault tolerance, reliability and security

• Game-theoretic approaches to distributed computing

• Cryptographic techniques in distributed computing

• Distributed computing issues in social networks

• Autonomous robots in terrains

• Graph searching

Important Dates

• Paper submission deadline: February 20, 2015

• Notification of acceptance: March 23, 2015

• Camera-ready due: April 10, 2015

The proceedings of the special track will be published by Springer-Verlag,
as part of the Lecture Notes in Computer Science (LNCS) series. High-quality articles may
be invited for submission to a special issue of Ad Hoc & Sensor Wireless Networks at the
International Journal of Parallel, Emergent and Distributed Systems. Submission will be
through the OCS system used for the main workshop, in a separate track.
Upon submission the authors should choose the appropriate track label for their papers.
Submitted papers should not exceed 14 pages.
For more information please contact Dr. Euripides Markou (emarkou@ucg.gr).
More details on the submission guidelines and the electronic submission can be found here:
http://www.netmode.ntua.gr/adhocnow2015/index.html

#### Invited Speakers

- Paola Flocchini, University of Ottawa, Canada

- Pierre Fraigniaud, CNRS and University Paris Diderot, France

- Shay Kutten, Technion - Israel Institute of Technology, Israel

- David Peleg, Weizmann Institute of Science, Israel

- Nicola Santoro, Carleton University, Canada

- Shmuel Zaks, Technion - Israel Institute of Technology, Israel

The Special Track (regular papers and invited talks) has been scheduled on Wednesday, July 1st, 2015 (except David Peleg's talk which is scheduled on Tuesday, June 30). For the complete program of the conference please see here.

#### Invited Talks' Details

- Paola Flocchini, University of Ottawa, Canada

Title: Computations by Luminous RobotsAbstract: The study of computability issues by a system of simple, autonomous, oblivious, mobile robots, operating in the plane in Look-Compute-Move cycles, has been the object of intensive investigations. These robots do not have explicit communication mechanisms, but they implicitly cooperate towards a common goal. This paper focuses on luminous robots, a recently introduced model where the robots are equipped with a light that can take a constant number of different colors. The light is visible to the observing robots and stays lit from a computation cycle to the next. The availability of lights, which provides little communication and memory, has clearly a great impact on the system of robots. We review the recent results, highlighting the many open problems and research directions.

Short CV: Paola Flocchini is Professor and University Research Chair in Distributed Computing at the School of Electrical Engineering and Computer Science (University of Ottawa). She is co-author of the book "Distributed Computing by Oblivious Mobile Robots". Her main research is on distributed algorithms, distributed computing, computations by mobile agents and robotic swarms; topics on which she has published extensively. Currently her research focus is especially on dynamic graphs and on autonomous mobile robots.

- Pierre Fraigniaud, CNRS and University Paris Diderot, France

Title: Decidability Classes for Mobile Agents ComputingAbstract: TBA

Short CV: Pierre Fraigniaud is ``Directeur de Recherche'' CNRS. Since 2010, he is director of the ``Laboratoire d'Informatique Algorithmique'' (LIAFA) at University Paris Diderot. His main research interest is parallel and distributed computing, and specifically the design and analysis of distributed algorithms and data structures for networks. He is member of the Editorial Boards of the journals Distributed Computing (DC), and Theory of Computing Systems (TOCS). He was Program Committee Chair for the 41st Int. Coll. on Automata, Languages and Programming (ICALP 2014, Track C), the 30th ACM Symp. on Principles of Distributed Computing (PODC 2011), the 19th Int. Symp. on Distributed Computing (DISC 2005) and the 13th ACM Symp.on Parallel Algorithms and Architectures (SPAA 2001). He was Management Committee Chair of the European COST Action 295 ``DYNAMO'' on Algorithmic Aspects of Dynamic Networks. In 2012, he received the Silver Medal from CNRS, and, in 2014, the Prize for Innovation in Distributed Computing.

- Shay Kutten, Technion - Israel Institute of Technology, Israel

Title: Moving the stationary, stopping the mobileAbstract: Sometimes, it is more convenient to view a stationary object as if it is mobile. Some other times, the converse is more convenient: viewing a mobile object as if it does not move. We demonstrate using some old and some new examples from distributed systems.

Short CV: Shay Kutten received his PhD in computer science from the Technion in 1987. His MSc work there pioneered the area of basing wireless protocols on graph theoretic models. His PhD was pioneering in suggesting the use of mobile agents for defining distributed algorithms. Till 2000 he was with IBM T.J. Watson Research Center. Among his positions there where the managing of the Network Architecture and Algorithms group and the founding of the Network and Distributed Systems Security group. Those developed the security architecture as well as network algorithms and protocols for various IBM products, various standards, and later, various products of other companies. He received various awards, including the IBM Outstanding Innovation Award (OIA) (twice), and various other awards. From 2000 he has been with the Information Systems area at the Faculty of IE&M at the Technion where he now holds the William M. Davidson Chair in IE&M and held various offices such as the head of the Information Systems area. Prof. Kutten contributed to the theory of distributed computing, mostly by introducing new theoretical subjects, many of them were inspired by his work on practical issues, and by giving well founded solutions to practical problems. In addition to the IBM awards, he won the Taub Award for excellence in research, and the Mitchner Award for research on Quality Sciences and Quality Management. He is an area editor (for security, reliability, and availability) of the ACM's journal on Selected Topics in Mobile Networks and Applications (MONET). He was also a member of the editorial board of the ACM's Wireless Networks and of the Elsevier journal Computer Networks. He served on program committees for several conferences and workshops, was the chair of the program committee of several conferences including the 1998 EATCS DISC conference and the 2004 ACM PODC and is the steering committee chair of SIROCCO.

- David Peleg, Weizmann Institute of Science, Israel

Title: Mobile Agents Rendezvous in the Presence of FaultsAbstract: The talk will consider fault-tolerant solutions to the rendezvous problem, where a team of mobile agents, starting from different nodes of an unknown synchronous network, have to meet at the same node, in the presence of up to f Byzantine (faulty) agents. The problem will be examined assuming different levels of Byzantine behavior and different levels of knowledge available to the agents, with a focus on bounds on the minimum number of non-faulty agents that guarantees deterministic gathering. (Based on joint work with Yoann Dieudonne and Andrzej Pelc.)

Short CV: David Peleg received the B.A. degree in 1980 from the Technion, Israel, the M.Sc. degree in 1982 from Bar-Ilan University, Israel, and the Ph.D. degree in 1985 from the Weizmann Institute, Israel, all in computer science. He then spent a post-doctoral period at IBM Almaden and at Stanford University. In 1988 he joined the Department of Computer Science and Applied Mathematics at The Weizmann Institute of Science, where he is the incumbent of the Norman D. Cohen Professorial Chair of Computer Sciences. He chaired the Weizmann Institute's Council of Professors in 2007-2008, and serves as Dean of the Faculty of Mathematics and Computer Science since 2010. His research interests include distributed network algorithms, fault-tolerant computing, communication network theory, approximation algorithms and graph theory, and he is the author of a book titled "Distributed Computing: A Locality-Sensitive Approach," as well as numerous papers in these areas. He received the ACM Edsger W. Dijkstra Prize in Distributed Computing in 2008 and the SIROCCO Prize for Innovation In Distributed Computing in 2011.

- Nicola Santoro, Carleton University, Canada

Title: Mobile Agents in Time-Varying NetworksAbstract: Distributed computing by mobile agents has been long investigated in the case of static networks. Changes in network topology have been usually limited to the context of fault-tolerance. However, the advent and rapid spread of highly-dynamic infractureless networks (e.g., wireless ad-hoc networks, vehicular networks, mobile sensor networks, etc.) has presented researchers with networks where changes are not due to failure but inherent in the system, possibly never ending, and such that connectivity of the network might not even exist at any time instant. These networks, modeled in a direct and natural way as time-varying graphs, are the object of studies both from an engineering and from a computational point-of-view, mostly focusing on (wireless) message-passing models. The aim of this talk is to describe the current investigations on distributed computing by mobile agents in these time-varying networks.

Short CV: Nicola Santoro is Distinguished Research Professor of Computer Science at Carleton University. He has been involved in distributed computing from the beginning of the field, authoring many seminal papers. He is a founder of the main theoretical conferences in the area, and the author of the book "Design and Analysis of Distributed Algorithms". He was the first recipient of the "Prize for Innovation in Distributed Computing". His current research is on distributed algorithms for mobile entities; as well as on time-varying graphs and dynamic networks.

- Shmuel Zaks, Technion - Israel Institute of Technology, Israel

Title: Online lower bounds and offline inapproximability in optical networksAbstract: We present lower bounds and inapproximability results for optimization problems that originated in studies of optical networks. They include offline and online scenarios, and concern problems that optimize the use of components in the optical networks, specifically Add-Drop Multiplexers (ADMs) and regenerators. First we discuss the online version of the problem of minimizing the number of ADMs in optical networks. In this case lightpaths need to be colored such that overlapping paths get different colors, path that share an endpoint can get the same color, and the cost is the total number endpoints (=ADMs); the key point is that an endpoint shared by two same-colored paths is counted only once. Following "M. Shalom, P. W. Wong, and S. Zaks, Optimal on-line colorings for minimizing the number of adms in optical networks, Journal of Discrete Algorithms, 8(2):174-188, June 2010" (where we showed tight competitive ratios for several networks), we present in this paper a 3/2 lower bound on the competitive ratio for a path network. We next present problems that deal with the use of regenerators in optical networks. Given a set of lightpaths in a network G and a positive integer d, regenerators must be placed in such a way that in any lightpath there are no more than d hops without meeting a regenerator. We first discuss the online version of the problem of optimizing the number of locations where regenerators are placed, following "G. B. Mertzios, M. Shalom, P. W. Wong, and S. Zaks, Online regenerator placement, In 15th International Conference on Principles of Distributed Systems (OPODIS), Toulouse, France, pages 4-17, December 2011". When there is a bound on the number of regenerators in a single node, there is not necessarily a solution for a given input. We distinguish between feasible inputs and infeasible ones. For the latter case our objective is to satisfy the maximum number of lightpaths. For a path topology we consider the case where d=2, and show a lower bound of square_root(l/2) for the competitive ratio (where l is the number of internal nodes of the longest lightpath) on infeasible inputs, and a tight bound of 3 for the competitive ratio on feasible inputs. Last we study the problem where we are given a finite set of p possible traffic patterns (each given by a set of lightpaths), and our objective is to place the minimum number of regenerators at the nodes so that each of the traffic patterns is satisfied (that is, regenerators are placed such that in any lightpath there are no more than d hops without meeting a regenerator). We prove - following "G. B. Mertzios, I. Sau, M. Shalom, and S. Zaks, Placing regenerators in optical networks to satisfy multiple sets of requests, IEEE Transactions on Networking, 20(6):1870-1879, December 2012" - that the problem does not admit a PTAS for any d,p >= 2. Some of these problems have interesting implications to problems stated within scheduling theory.

Short CV: Shmuel Zaks received his BSc (cum laude) and MSc in Mathematics from the Technion-Israel Institute of Technology, Haifa, Israel, in 1971 and 1972, respectively, and PhD in Computer Science from the University of Illinois at Urbana-Champaign in 1979. He is a Professor with the Department of Computer Science, Technion, and is the incumbent of the Joan Callner-Miller Chair in Computer Science. He is the author of over 180 journal and conference publications, and was a member of 40 Program Committees of international conferences. His research areas include graph and combinatorial algorithms, distributed computing, discrete mathematics, and theory of networking (especially optical networks).

#### Special Session Program Committee

Evangelos Bampas, LaBRI, University of Bordeaux, France

Shantanu Das, LIF, Aix-Marseille University, France

Stefan Dobrev, Slovak Academy of Sciences, Slovakia

Panagiota Fatourou, FORTH, Univ. of Crete, Greece

Loukas Georgiadis, University of Ioannina, Greece

David Ilcinkas, CNRS & University of Bordeaux, France

Ralf Klasing, CNRS & University of Bordeaux, France

Rastislav Kralovic, Comenius University, Slovakia

Evangelos Kranakis, Carleton University, Canada

Danny Krizanc, Wesleyan University, USA

Arnaud Labourel, LIF, Aix-Marseille University, France

Flaminia Luccio, Universita Ca Foscari Venezia, Italy

Euripides Markou, University of Thessaly, Greece (co-chair)

Nicolas Nisse, INRIA Sophia Antipolis, France

Katerina Potika, Santa Clara University, USA

Peter Widmayer, ETH Zurich, Switzerland (co-chair)

#### Special Session Organizing Committee

Evangelos Bampas, LaBRI, University of Bordeaux, France

Euripides Markou, University of Thessaly, Greece

Katerina Potika, Santa Clara University, USA