The purpose of this talk is to provide an introduction to "Distributed Computing by Mobile Entities", a wide and wild research field whose exploration has only recently begun. The focus will be in particular on computational models and exemplar problems, their origins, theoretical relevance, and current status.

Nicola Santoro is Professor of Computer Science at Carleton University. He has been involved in distributed computing from the beginning of the field, contributing extensively on the algorithmic aspects. He is a founder of the main theoretical conferences in the field (PODC, DISC, SIROCCO). He has recently authored the book "Design and Analysis of Distributed Algorithms" (Wiley 2007). His current research is on distributed algorithms for mobile agents, autonomous mobile robots, and mobile sensor systems.

• Gathering problem of two asynchronous mobile robots with semi-dynamic compasses
  Nobuhiro Inuzuka, Yuichi Tomida, Taisuke Izumi, Yoshiaki Katayama and Koichi Wada
• Locating and repairing faults in a network with mobile agents
  Colin Cooper, Ralf Klasing and Tomasz Radzik
• Remembering Without Memory: Tree Exploration by Asynchronous Oblivious Robots
  Paola Flocchini, David Ilcinkas, Andrzej Pelc and Nicola Santoro

• Average binary long-lived Consensus: quantifying the stabilization role played by memory
  Florent Becker, Rapaport Ivan, Éric Rémila and Sergio Rajsbaum
• Distributed Approximation Algorithm for Resource Clustering
  Olivier Beaumont, Nicolas Bonichon, Philippe Duchon and Hubert Larcheveque
• Sharpness: A tight condition for Throughput Scalability
  Augustin Chaintreau

• Discovery of Network Properties with All-Shortest-Paths Queries
  Davide Bilo, Thomas Erlebach, Matus Mihalak and Peter Widmayer
• Recovering the Long Range Links in Augmented Graphs
  Pierre Fraigniaud, Emmanuelle Lebhar and Zvi Lotker
• Computing Frequent Elements using Gossip
  Bibudh Lahiri and Srikanta Tirthapura

In recommendation systems (e.g., for books or movies), the system tracks which product each user liked in the past, and tries to deduce which other products the user is likely to be satisfied with. Recommendation systems can help users who share many preferences with many other users by means of "collaborative filtering." Most current approaches to on-line recommendation systems employ algebraic techniques such as Singular Value Decomposition (SVD), which are computationally intensive and, more important, often applicable only under some additional strong conditions. We overview a new approach which demonstrates that simple combinatorial algorithms can make good recommendations that guarantee that the cost per user is only polylogarithmic factor over optimal, without restricting the allowed inputs.

Boaz Patt-Shamir has received his BSc , MSc and PhD from Tel Aviv University, Weizmann Institute and MIT, respectively. He taught in Northeastern University and MIT, and since 1997 he is with the Department of Electrical Engineering in Tel Aviv University, where he directs the Laboratory of Advanced Communication. In 2002-2004 he spent an extended sabbatical in HP Labs in Cambridge (Mass.), where he developed an interest in recommendation systems. His other research interests include classical distributed algorithms, algorithms for communication networks, and self-stabilization.

• Maintaining Consistent Transactional States Without a Global Clock
  Hillel Avni and Nir Shavit
• Equal-Area Locus-Based Convex Polygon Decomposition
  David Adjiashvili and David Peleg
• On the power of local orientations
  Monika Steinová
• Best Effort and Priority Queuing Policies for Buffered Crossbar Switches
  Alex Kesselman, Kirill Kogan and Michael Segal

• Word-of-Mouth: Rumor Dissemination in Social Networks
  Jan Kostka, Yvonne Anne Oswald and Roger Wattenhofer
• Non-preemptive Coordination Mechanisms for Identical Machine Scheduling Games
  Konstantinos Kollias
• Computing Approximate Nash Equilibria in Network Congestion Games
  Andreas Emil Feldmann, Heiko Roeglin and Berthold Voecking

• On the Performance of Beauquier and Debas' Self-Stabilizing Algorithm for Mutual Exclusion
  Viacheslav Chernoy, Mordechai Shalom and Shmuel Zaks
• Self-stabilizing Cuts in Synchronous Networks
  Thomas Sauerwald and Dirk Sudholt
• Quiescence of Self-stabilizing Gossiping among Mobile Agents in Graphs
  Toshimitsu Masuzawa and Sebastien Tixeuil

• Gathering with Minimum Delay in Sensor Networks
  Jean-Claude Bermond, Luisa Gargano and Adele Rescigno
• Centralized communication in radio networks with strong interference
  František Galcík
• Fast Radio Broadcasting with Advice
  David Ilcinkas, Dariusz Kowalski and Andrzej Pelc