Laudatio

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.

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

References

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

1. 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.
2. I. Suzuki and M. Yamashita, “Distributed anonymous mobile robots”, SIAM J. Comput. 28(4): 1347–1363 (1999).
3. M. Yamashita and I. Suzuki: “Characterizing geometric patterns formable by oblivious anonymous mobile robots”, Theoretical Computer Science 411(26–28): 2433–2453 (2010).
4. 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).
5. 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).
6. 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).
7. 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).