Prize for Innovation in Distributed Computing 2016

Awarded to Masafumi (Mark) Yamashita at SIROCCO 2016

It is a pleasure to award the **2016 SIROCCO Prize for Innovation in distributed computing** to **Masafumi (Mark) Yamashita**. Mark presented many original ideas and important results that have enriched the theoretical computer science community, and the distributed computing community, such as his seminal work “Computing on Anonymous Networks” (with T. Kameda), which introduced the notion of “view” and has inspired all the subsequent investigations on computability in anonymous networks, and his work on coteries, on self stabilization, on polling games, etc.

The prize is awarded for these lifetime achievements of his, but especially for introducing the computational universe of Autonomous Mobile Robots to the algorithmic community, and to the distributed community in particular. This has opened a new and exciting research area that has now become an accepted mainstream topic in theoretical computer science (“mobile robots” papers now appear in all major theory conferences and journals) and clearly in distributed computing. The fascinating new area of research it opens is now under investigation by many groups worldwide.

The introduction of this area to the theory community was actually done in his SIROCCO paper [1]. The full version was then published in *SIAM J. on Computing* [2]. (This paper currently has more than 500 citations.)

This paper deals with the problem of coordination among autonomous robots moving on a plane. This paper and the subsequent papers on this topic provided the first indications about which tasks can be accomplished using multiple deterministic, autonomous and identical robots in a collaborative manner. The formal model for mobile robots introduced in this paper (called the Suzuki–Yamashita or SYM model) provides a nice abstraction which makes it easy to analyze algorithms but still captures many of the difficulties of coordination between the robots. Many of the recent results on distributed robotics are based on either this model or extensions of it. The paper provided the characterization (in terms of geometric pattern formation) of all tasks that can be performed by such teams of deterministic robots and provided some fundamental impossibility results including the impossibility of gathering two oblivious robots. A more recent paper [3] extends the characterization to the model where robots are memory-less, thus showing the exact difference between oblivious robots and robots having memory.

The 2015 award committee:

Thomas Moscibroda (Microsoft),

Guy Even (Tel Aviv University),

Magnús Halldórsson (Reykjavik University),

Shay Kutten (Technion) — chair,

Andrzej Pelc (Université du Québec en Outaouais).

We wish to thank the nominators for the nomination and for contributing heavily to this text.

Selected publications related to Masafumi (Mark) Yamashita’s contribution:

- I. Suzuki and M. Yamashita,
“Distributed anonymous mobile robots”,
*Proc. 3rd International Colloquium on Structural Information & Communication Complexity*, Siena, Italy, June 6–8, pp. 313–330, 1996. - I. Suzuki and M. Yamashita,
“Distributed anonymous mobile robots”,
*SIAM J. Comput.*28(4): 1347–1363 (1999). - M. Yamashita and I. Suzuki:
“Characterizing geometric patterns formable by oblivious anonymous mobile robots”,
*Theoretical Computer Science*411(26–28): 2433–2453 (2010). - A. Dumitrescu, I. Suzuki, and M. Yamashita:
“Motion planning for metamorphic systems: feasibility, decidability, and distributed reconfiguration”,
*IEEE Transactions on Robotics*20(3): 409–418 (2004). - S. Souissi, X. Defago and M. Yamashita:
“Using eventually consistent compasses to gather memory-less mobile robots with limited visibility”,
*ACM Transactions on Autonomous and Adaptive Systems*4(1): #9 (2009). - S. Das, P. Flocchini, N. Santoro, and M. Yamashita:
“Forming sequences of geometric patterns with oblivious mobile robots”,
*Distributed Computing*28(2): 131–145 (2015). - N. Fujinaga, Y. Yamauchi, H. Ono, Shuji K., M. Yamashita:
“Pattern formation by oblivious asynchronous mobile robots”,
*SIAM J. Comput.*44(3): 740–785 (2015).