
This paper poses a question about a simple localization problem. The question
is if an {\em oblivious} walker on a linesegment can localize the middle point
of the linesegment in {\em finite} steps observing the direction (i.e., Left
or Right) and the distance to the nearest end point. This problem is arisen
from {\em selfstabilizing} location problems by {\em autonomous mobile robots}
with {\em limited visibility}, that is a widely interested abstract model in
distributed computing. Contrary to appearances, it is far from trivial if this
simple problem is solvable or not, and unsettled yet. This paper is concerned
with three variants of the problem with a minimal relaxation, and presents
selfstabilizing algorithms for them. We also show an easy impossibility
theorem for bilaterally symmetric algorithms.

A set function $f$ on a finite set $V$ is {\em submodular} if $f(X) + f(Y)
\geq f(X \cup Y) + f(X \cap Y)$ for any pair $X, Y \subseteq V$. The {\em
symmetric difference transformation} ({\em SDtransformation}) of $f$ by a {\em
canonical set} $S \subseteq V$ is a set function $g$ given by $g(X) = f(X
\vartriangle S)$ for $X \subseteq V$,where $X \vartriangle S = (X \setminus S)
\cup (S \setminus X)$ denotes the symmetric difference between $X$ and $S$.
Submodularity and SDtransformations are regarded as the counterparts of
convexity and affine transformations in a discrete space, respectively.
However, submodularity is not preserved under SDtransformations, in contrast
to the fact that convexity is invariant under affine transformations. This
paper presents a characterization of SDstransformations preserving
submodularity. Then, we are concerned with the problem of discovering a
canonical set $S$, given the SDtransformation $g$ of a submodular function $f$
by $S$, provided that $g(X)$ is given by a function value oracle. A submodular
function $f$ on $V$ is said to be {\em strict} if $f(X) + f(Y) > f(X \cup Y) +
f(X \cap Y)$ holds whenever both $X \setminus Y$ and $Y \setminus X$ are
nonempty. We show that the problem is solved by using ${\rm O}(V)$ oracle
calls when $f$ is strictly submodular, although it requires exponentially many
oracle calls in general.

The Meeting problem for $k\geq 2$ searchers in a polygon $P$ (possibly with
holes) consists in making the searchers move within $P$, according to a
distributed algorithm, in such a way that at least two of them eventually come
to see each other, regardless of their initial positions. The polygon is
initially unknown to the searchers, and its edges obstruct both movement and
vision. Depending on the shape of $P$, we minimize the number of searchers $k$
for which the Meeting problem is solvable. Specifically, if $P$ has a
rotational symmetry of order $\sigma$ (where $\sigma=1$ corresponds to no
rotational symmetry), we prove that $k=\sigma+1$ searchers are sufficient, and
the bound is tight. Furthermore, we give an improved algorithm that optimally
solves the Meeting problem with $k=2$ searchers in all polygons whose
barycenter is not in a hole (which includes the polygons with no holes). Our
algorithms can be implemented in a variety of standard models of mobile robots
operating in LookComputeMove cycles. For instance, if the searchers have
memory but are anonymous, asynchronous, and have no agreement on a coordinate
system or a notion of clockwise direction, then our algorithms work even if the
initial memory contents of the searchers are arbitrary and possibly misleading.
Moreover, oblivious searchers can execute our algorithms as well, encoding
information by carefully positioning themselves within the polygon. This code
is computable with basic arithmetic operations, and each searcher can
geometrically construct its own destination point at each cycle using only a
compass. We stress that such memoryless searchers may be located anywhere in
the polygon when the execution begins, and hence the information they initially
encode is arbitrary. Our algorithms use a selfstabilizing map construction
subroutine which is of independent interest.

We consider a distributed system consisting of autonomous mobile computing
entities, called robots, moving in a specified space. The robots are anonymous,
oblivious, and have neither any access to the global coordinate system nor any
explicit communication medium. Each robot observes the positions of other
robots and moves in terms of its local coordinate system. To investigate the
selforganization power of robot systems, formation problems in the two
dimensional space (2Dspace) have been extensively studied. Yamauchi et al.
(DISC 2015) introduced robot systems in the three dimensional space (3Dspace).
While existing results for 3Dspace assume that the robots agree on the
handedness of their local coordinate systems, we remove the assumption and
consider the robots without chirality. One of the most fundamental agreement
problems in 3Dspace is the plane formation problem that requires the robots to
land on a common plane, that is not predefined. It has been shown that the
solvability of the plane formation problem by robots with chirality is
determined by the rotation symmetry of their initial local coordinate systems
because the robots cannot break it. We show that when the robots lack
chirality, the combination of rotation symmetry and reflection symmetry
determines the solvability of the plane formation problem because a set of
symmetric local coordinate systems without chirality is obtained by rotations
and reflections. This richer symmetry results in the increase of unsolvable
instances compared with robots with chirality and a flaw of existing plane
formation algorithm. In this paper, we give a characterization of initial
configurations from which the robots without chirality can form a plane and a
new plane formation algorithm for solvable instances.

An oblivious mobile robot is a stateless computational entity located in a
spatial universe, capable of moving in that universe. When activated, the robot
observes the universe and the location of the other robots, chooses a
destination, and moves there. The computation of the destination is made by
executing an algorithm, the same for all robots, whose sole input is the
current observation. No memory of all these actions is retained after the move.
When the universe is a graph, distributed computations by oblivious mobile
robots have been intensively studied focusing on the conditions for feasibility
of basic problems (e.g., gathering, exploration) in specific classes of graphs
under different schedulers. In this paper, we embark on a different, more
general, type of investigation.
With their movements from vertices to neighboring vertices, the robots make
the system transition from one configuration to another. Viewing this
transition as the computation of an abstract function, we ask which functions
are computed by which systems. Our main interest is on identifying sets of
systems that are "universal", in the sense that they can collectively compute
all finite functions. We are able to identify several such classes of fully
synchronous systems. In particular, among other results, we prove the
universality of the set of all graphs with at least one robot, of any set of
graphs with at least two robots whose quotient graphs contain arbitrarily long
paths, and of any set of graphs with at least three robots and arbitrarily
large finite girths.
We then focus on the minimum size that a network must have for the robots to
be able to compute all functions on a given finite set. We are able to
approximate the minimum size of such a network up to a factor that tends to 2
as $n$ goes to infinity.

Motivated by a relaxed notion of the celebrated Hamiltonian cycle, this paper
investigates its variant, parity Hamiltonian cycle (PHC): A PHC of a graph is a
closed walk which visits every vertex an odd number of times, where we remark
that the walk may use an edge more than once. First, we give a complete
characterization of the graphs which have PHCs, and give a linear time
algorithm to find a PHC, in which every edge appears at most four times, in
fact. In contrast, we show that finding a PHC is NPhard if a closed walk is
allowed to use each edge at most z times for each z=1,2,3 (PHCz for short),
even when a given graph is twoedge connected. We then further investigate the
PHC3 problem, and show that the problem is in P when an input graph is
fouredge connected. Finally, we are concerned with three (or two)edge
connected graphs, and show that the PHC3 is in P for any C_>=5free or P6free
graphs. Note that the Hamiltonian cycle problem is known to be NPhard for
those graph classes.

We consider a swarm of autonomous mobile robots each of which is an anonymous
point in the threedimensional Euclidean space (3Dspace) and synchronously
executes a common distributed algorithm. We investigate the pattern formation
problem that requires the robots to form a given target pattern from an initial
configuration and characterize the problem by showing a necessary and
sufficient condition for the robots to form a given target pattern.
The pattern formation problem in the two dimensional Euclidean space
(2Dspace) has been investigated by Suzuki and Yamashita (SICOMP 1999, TCS
2010), and Fujinaga et al. (SICOMP 2015). The symmetricity $\rho(P)$ of a
configuration (i.e., the positions of robots) $P$ is intuitively the order of
the cyclic group that acts on $P$. It has been shown that fullysynchronous
(FSYNC) robots can form a target pattern $F$ from an initial configuration $P$
if and only if $\rho(P)$ divides $\rho(F)$.
We extend the notion of symmetricity to 3Dspace by using the rotation groups
each of which is defined by a set of rotation axes and their arrangement. We
define the symmetricity $\varrho(P)$ of configuration $P$ in 3Dspace as the
set of rotation groups that acts on $P$ and whose rotation axes do not contain
any robot. We show the following necessary and sufficient condition for the
pattern formation problem which is a natural extension of the existing results
of the pattern formation problem in 2Dspace: FSYNC robots in 3Dspace can form
a target pattern $F$ from an initial configuration $P$ if and only if
$\varrho(P) \subseteq \varrho(F)$. For solvable instances, we present a pattern
formation algorithm for oblivious FSYNC robots. The insight of this paper is
that symmetry of mobile robots in 3Dspace is sometimes lower than the symmetry
of their positions and the robots can show their symmetry by their movement.

Creating a swarm of mobile computing entities frequently called robots,
agents or sensor nodes, with selforganization ability is a contemporary
challenge in distributed computing. Motivated by this, we investigate the plane
formation problem that requires a swarm of robots moving in the three
dimensional Euclidean space to land on a common plane. The robots are fully
synchronous and endowed with visual perception. But they do not have
identifiers, nor access to the global coordinate system, nor any means of
explicit communication with each other. Though there are plenty of results on
the agreement problem for robots in the two dimensional plane, for example, the
point formation problem, the pattern formation problem, and so on, this is the
first result for robots in the three dimensional space. This paper presents a
necessary and sufficient condition for fullysynchronous robots to solve the
plane formation problem that does not depend on obliviousness i.e., the
availability of local memory at robots. An implication of the result is
somewhat counterintuitive: The robots cannot form a plane from most of the
semiregular polyhedra, while they can form a plane from every regular
polyhedron (except a regular icosahedron), whose symmetry is usually considered
to be higher than any semiregular polyhedrdon.

Motivated by a derandomization of Markov chain Monte Carlo (MCMC), this paper
investigates deterministic random walks, which is a deterministic process
analogous to a random walk. While there are several progresses on the analysis
of the vertexwise discrepancy (i.e., $L_\infty$ discrepancy), little is known
about the {\em total variation discrepancy} (i.e., $L_1$ discrepancy), which
plays a significant role in the analysis of an FPRAS based on MCMC. This paper
investigates upper bounds of the $L_1$ discrepancy between the expected number
of tokens in a Markov chain and the number of tokens in its corresponding
deterministic random walk. First, we give a simple but nontrivial upper bound
${\rm O}(mt^*)$ of the $L_1$ discrepancy for any ergodic Markov chains, where
$m$ is the number of edges of the transition diagram and $t^*$ is the mixing
time of the Markov chain. Then, we give a better upper bound ${\rm
O}(m\sqrt{t^*\log t^*})$ for nonoblivious deterministic random walks, if the
corresponding Markov chain is ergodic and lazy. We also present some lower
bounds.

The rotorrouter model is a deterministic process analogous to a simple
random walk on a graph. This paper is concerned with a generalized model,
functionalrouter model, which imitates a Markov chain possibly containing
irrational transition probabilities. We investigate the discrepancy of the
number of tokens at a single vertex between the functionalrouter model and its
corresponding Markov chain, and give an upper bound in terms of the mixing time
of the Markov chain.

We study the impact that persistent memory has on the classical rendezvous
problem of two mobile computational entities, called robots, in the plane. It
is well known that, without additional assumptions, rendezvous is impossible if
the entities are oblivious (i.e., have no persistent memory) even if the system
is semisynchronous (SSynch). It has been recently shown that rendezvous is
possible even if the system is asynchronous (ASynch) if each robot is endowed
with O(1) bits of persistent memory, can transmit O(1) bits in each cycle, and
can remember (i.e., can persistently store) the last received transmission.
This setting is overly powerful.
In this paper we weaken that setting in two different ways: (1) by
maintaining the O(1) bits of persistent memory but removing the communication
capabilities; and (2) by maintaining the O(1) transmission capability and the
ability to remember the last received transmission, but removing the ability of
an agent to remember its previous activities. We call the former setting
finitestate (FState) and the latter finitecommunication (FComm). Note that,
even though its use is very different, in both settings, the amount of
persistent memory of a robot is constant.
We investigate the rendezvous problem in these two weaker settings. We model
both settings as a system of robots endowed with visible lights: in FState, a
robot can only see its own light, while in FComm a robot can only see the other
robot's light. We prove, among other things, that finitestate robots can
rendezvous in SSynch, and that finitecommunication robots are able to
rendezvous even in ASynch. All proofs are constructive: in each setting, we
present a protocol that allows the two robots to rendezvous in finite time.

In infrastructureless highly dynamic networks, computing and performing even
basic tasks (such as routing and broadcasting) is a very challenging activity
due to the fact that connectivity does not necessarily hold, and the network
may actually be disconnected at every time instant. Clearly the task of
designing protocols for these networks is less difficult if the environment
allows waiting (i.e., it provides the nodes with storecarryforwardlike
mechanisms such as local buffering) than if waiting is not feasible. No
quantitative corroborations of this fact exist (e.g., no answer to the
question: how much easier?). In this paper, we consider these qualitative
questions about dynamic networks, modeled as timevarying (or evolving) graphs,
where edges exist only at some times.
We examine the difficulty of the environment in terms of the expressivity of
the corresponding timevarying graph; that is in terms of the language
generated by the feasible journeys in the graph. We prove that the set of
languages $L_{nowait}$ when no waiting is allowed contains all computable
languages. On the other end, using algebraic properties of quasiorders, we
prove that $L_{wait}$ is just the family of regular languages. In other words,
we prove that, when waiting is no longer forbidden, the power of the accepting
automaton (difficulty of the environment) drops drastically from being as
powerful as a Turing machine, to becoming that of a FiniteState machine. This
(perhaps surprisingly large) gap is a measure of the computational power of
waiting.
We also study bounded waiting; that is when waiting is allowed at a node only
for at most $d$ time units. We prove the negative result that $L_{wait[d]} =
L_{nowait}$; that is, the expressivity decreases only if the waiting is finite
but unpredictable (i.e., under the control of the protocol designer and not of
the environment).

Anonymous mobile robots are often classified into synchronous,
semisynchronous and asynchronous robots when discussing the pattern formation
problem. For semisynchronous robots, all patterns formable with memory are
also formable without memory, with the single exception of forming a point
(i.e., the gathering) by two robots. However, the gathering problem for two
semisynchronous robots without memory is trivially solvable when their local
coordinate systems are consistent, and the impossibility proof essentially uses
the inconsistencies in their coordinate systems. Motivated by this, this paper
investigates the magnitude of consistency between the local coordinate systems
necessary and sufficient to solve the gathering problem for two oblivious
robots under semisynchronous and asynchronous models. To discuss the magnitude
of consistency, we assume that each robot is equipped with an unreliable
compass, the bearings of which may deviate from an absolute reference
direction, and that the local coordinate system of each robot is determined by
its compass. We consider two families of unreliable compasses, namely,static
compasses with constant bearings, and dynamic compasses the bearings of which
can change arbitrarily.
For each of the combinations of robot and compass models, we establish the
condition on deviation \phi that allows an algorithm to solve the gathering
problem, where the deviation is measured by the largest angle formed between
the xaxis of a compass and the reference direction of the global coordinate
system: \phi < \pi/2 for semisynchronous and asynchronous robots with static
compasses, \phi < \pi/4 for semisynchronous robots with dynamic compasses, and
\phi < \pi/6 for asynchronous robots with dynamic compasses. Except for
asynchronous robots with dynamic compasses, these sufficient conditions are
also necessary.

Selfstabilization is a strong property that guarantees that a network always
resume correct behavior starting from an arbitrary initial state. Weaker
guarantees have later been introduced to cope with impossibility results:
probabilistic stabilization only gives probabilistic convergence to a correct
behavior. Also, weak stabilization only gives the possibility of convergence.
In this paper, we investigate the relative power of weak, self, and
probabilistic stabilization, with respect to the set of problems that can be
solved. We formally prove that in that sense, weak stabilization is strictly
stronger that selfstabilization. Also, we refine previous results on weak
stabilization to prove that, for practical schedule instances, a deterministic
weakstabilizing protocol can be turned into a probabilistic selfstabilizing
one. This latter result hints at more practical use of weakstabilization, as
such algorthms are easier to design and prove than their (probabilistic)
selfstabilizing counterparts.