Series in Distributed Computing
edited by Roger Wattenhofer
Vol. 21


Jara Uitto

Collaboration in Multi-Agent Systems:

Adaptivity and Active Learning

1st edition / 1. Aufl. 2015. XII, 136 pages/Seiten, € 64,00.

ISBN 978-3-86628-549-1


Communication is a powerful tool that enables the operation of a variety of old and new systems, such as mobile networks, trade, and human relationships to name a few. Such systems consist of many actors that, in one way or another, communicate with each other to reach a common goal. In this dissertation, we study two rather different examples of such multi-agent systems, namely, we explore the realm of recommendation algorithms and networks of primitive models of computation.

In the case of recommendation algorithms, the agents are able to share their preferences on some items via a centralized entity that keeps track of the sharing history. The goal is to utilize the sharing history so that the agents can learn which items they could potentially like. In the case that the agents have many preferences in common, learning the preferences can be helpful in finding good items for the agents. However, if the agents do not have any preferences in common, it is hard to utilize the sharing information. With this in mind, we propose a new scheme for competitive analysis of recommendation algorithms, where we compare our online algorithms to offline algorithms, that have limited information about the input. In addition, we propose an online algorithm that finds a good item for every agent in the system that has, up to a polylogarithmic factor, an optimal competitive ratio in terms of our new scheme.

In the second part of the dissertation, we focus on the Stone Age model of computation, where the agents are modeled by finite state machines. First, we study the computation of a maximal independent set (MIS) motivated by observations from biology, where cells are known to solve this problem.  We extend the study to arbitrary networks, where the nodes are subject to crash failures. We propose a distributed algorithm that is, on top of solving the MIS problem in the presence of failures, able to contain the effects of the failures from the nodes of the network that are not directly connected to the failed nodes. Second, we study the Ants Nearby Treasure Search (ANTS) problem in a similar model, where the agents are mobile. Our problem setting is motivated by the foraging behavior of real world ants and the goal of our agents is to locate a treasure hidden in an infinite grid. The agents are faced by two different challenges in the environment. One of the challenges is unexpected deaths (failures) of the agents, which requires the agents to replace the dead agents to ensure that the treasure is eventually discovered. The other challenge considers obstructions, that is, the agents have to adapt to arbitrary obstacles in the environment. We show that by means of cooperation, the agents are able to deal with both challenges and only require a small overhead in the time complexity or in the number of agents required to solve the task.


About the Author


Jara Uitto received his M.Sc. in 2011 from the Department of Computer Science at the University of Helsinki. His doctoral studies took place from 2011 to 2015 in the Distributed Computing Group at ETH Zürich supervised by Prof. Dr. Roger Wattenhofer. He received his PhD degree from ETH Zürich in August 2015. His research interests include algorithms, distributed computing, and graph theory.


Keywords: Collaboration, Distributed Systems, robots, ants, matchings, Price of Anarchy (PoA), Price of Stability (PoS)


Direkt bestellen bei / to order directly from:
Series in Distributed Computing in

Direkt bestellen bei / to order directly from:

Hartung-Gorre Verlag

Hartung-Gorre Verlag / D-78465 Konstanz / Germany

Telefon: +49 (0) 7533 97227  Telefax: +49 (0) 7533 97228   eMail: