C-5-44
Simple Local-information-based Self-optimizing
Algorithms in Grid Networks1

Fukuhito Ooshita 1

Shusuke Takatsu 1

f-oosita@ist.osaka-u.ac.jp

s-takatu@ist.osaka-u.ac.jp

Hirotsugu Kakugawa 1

Toshimitsu Masuzawa 1

kakugawa@ist.osaka-u.ac.jp

masuzawa@ist.osaka-u.ac.jp

Graduate school of information science and technology, Osaka University
Yamadaoka 1-5, Suita, Osaka 565-0871, Japan

Keywords: Distributed algorithm, Self-optimization, Grid network, Shortest path construction,
BFS tree construction
Recently molecular robotics, which uses molecules as robot components, has received a lot ofattention as a new paradigm for artifacts [1]. To realize molecular robots, it is necessary toassemble a large number of molecular devices in a self-organizing manner. That is, each moleculardevice operates autonomously based on local information (obtained with their sensors), but themolecular devices as a whole should work cooperatively as a robot. This behavior is similar to thatof large-scale distributed systems, where each computer operates based on local information butthe computers as a whole work cooperatively as a system.
For this reason, it is natural to apply distributed algorithms (i.e., algorithms for distributedsystems) to molecular robotics. Many distributed algorithms are proposed for many problems inliterature. However, since such distributed algorithms are designed for computers to achieve thehighest performance, the algorithms are complex and implementing them in molecular devices isdifficult. To apply distributed algorithms to molecular robotics, it is necessary to develop simple
distributed algorithms.
In this poster, we focus on grid networks, and introduce simple distributed algorithms for theshortest path construction [2] and the BFS (bread-first-search) tree construction. The shortest pathis useful to transmit a signal from the source to the destination quickly, and the BFS tree is usefulto transmit a signal from the source to all devices quickly. The algorithm for the shortest pathconstruction (resp., the BFS tree construction) constructs the shortest path (resp., the BFS tree)
from any initial path (resp., tree) in a self-optimizing manner. Both algorithms are simple: thealgorithm for the shortest path construction uses only three rules and that for the BFS tree
construction uses only four rules. These rules locally update a path or a tree with preserving theconnectivity and can be executed asynchronously.
While the characteristics of the above distributed algorithms are suitable for molecular robots, it
still requires some researches to implement them in molecular robots because the capability ofcurrent molecular devices is limited. As future work, we intend establishing a theoretical model formolecular robotics and developing distributed algorithms on the model.
[1] Murata, S., Konagaya, A., Kobayashi, S., Saito, H., and Hagiya, M., Molecular robotics: A newparadigm for artifacts, New Generation Computing, 31, 27-45, 2013.
[2] Takatsu, S., Ooshita, F., Kakugawa, H., and Masuzawa, T., Zigzag: Local-information-based
self-optimizing routing in virtual grid networks, Proc. of the 33rd International Conference onDistributed Computing Systems, 2013.