  The design of distributed gathering and convergence algorithms for tiny
robots has recently received much attention. In particular, it has been shown
that convergence problems can even be solved for very weak, \emph{oblivious}
robots: robots which cannot maintain state from one round to the next. The
oblivious robot model is hence attractive from a self-stabilization
perspective, where state is subject to adversarial manipulation. However, to
the best of our knowledge, all existing robot convergence protocols rely on the
assumption that robots, despite being "weak", can measure distances.
  We in this paper initiate the study of convergence protocols for even simpler
robots, called \emph{monoculus robots}: robots which cannot measure distances.
In particular, we introduce two natural models which relax the assumptions on
the robots' cognitive capabilities: (1) a Locality Detection ($\mathcal{LD}$)
model in which a robot can only detect whether another robot is closer than a
given constant distance or not, (2) an Orthogonal Line Agreement
($\mathcal{OLA}$) model in which robots only agree on a pair of orthogonal
lines (say North-South and West-East, but without knowing which is which).
  The problem turns out to be non-trivial, and simple median and angle
bisection strategies can easily increase the distances among robots (e.g., the
area of the enclosing convex hull) over time. Our main contribution are
deterministic self-stabilizing convergence algorithms for these two models,
together with a complexity analysis. We also show that in some sense, the
assumptions made in our models are minimal: by relaxing the assumptions on the
\textit{monoculus robots} further, we run into impossibility results.

Distributed, Parallel, and Cluster Computing