
Computer networks have become a critical infrastructure. In fact, networks
should not only meet strict requirements in terms of correctness, availability,
and performance, but they should also be very flexible and support fast
updates, e.g., due to policy changes, increasing traffic, or failures. This
paper presents a structured survey of mechanism and protocols to update
computer networks in a fast and consistent manner. In particular, we identify
and discuss the different desirable consistency properties that should be
provided throughout a network update, the algorithmic techniques which are
needed to meet these consistency properties, and the implications on the speed
and costs at which updates can be performed. We also explain the relationship
between consistent network update problems and classic algorithmic optimization
ones. While our survey is mainly motivated by the advent of SoftwareDefined
Networks (SDNs) and their primary need for correct and efficient update
techniques, the fundamental underlying problems are not new, and we provide a
historical perspective of the subject as well.

The Virtual Network Embedding Problem (VNEP) captures the essence of many
resource allocation problems of today's infrastructure providers, which offer
their physical computation and networking resources to customers. Customers
request resources in the form of Virtual Networks, i.e. as a directed graph
which specifies computational requirements at the nodes and communication
requirements on the edges. An embedding of a Virtual Network on the shared
physical infrastructure is the joint mapping of (virtual) nodes to physical
servers together with the mapping of (virtual) edges onto paths in the physical
network connecting the respective servers.
This work initiates the study of approximation algorithms for the VNEP.
Concretely, we study the offline setting with admission control: given multiple
request graphs the task is to embed the most profitable subset while not
exceeding resource capacities. Our approximation is based on the randomized
rounding of Linear Programming (LP) solutions. Interestingly, we uncover that
the standard LP formulation for the VNEP exhibits an inherent structural
deficit when considering general virtual network topologies: its solutions
cannot be decomposed into valid embeddings. In turn, focusing on the class of
cactus request graphs, we devise a novel LP formulation, whose solutions can be
decomposed into convex combinations of valid embedding. Proving performance
guarantees of our rounding scheme, we obtain the first approximation algorithm
for the VNEP in the resource augmentation model.
We propose two types of rounding heuristics and evaluate their performance in
an extensive computational study. Our results indicate that randomized rounding
can yield good solutions (even without augmentations). Specifically, heuristic
rounding achieves 73.8% of the baseline's profit, while not exceeding
capacities.

We initiate the study of a fundamental combinatorial problem: Given a
capacitated graph $G=(V,E)$, find a shortest walk ("route") from a source $s\in
V$ to a destination $t\in V$ that includes all vertices specified by a set
$\mathscr{W}\subseteq V$: the \emph{waypoints}. This waypoint routing problem
finds immediate applications in the context of modern networked distributed
systems. Our main contribution is an exact polynomialtime algorithm for graphs
of bounded treewidth. We also show that if the number of waypoints is
logarithmically bounded, exact polynomialtime algorithms exist even for
general graphs. Our two algorithms provide an almost complete characterization
of what can be solved exactly in polynomialtime: we show that more general
problems (e.g., on grid graphs of maximum degree 3, with slightly more
waypoints) are computationally intractable.

Many resource allocation problems in the cloud can be described as a basic
Virtual Network Embedding Problem (VNEP): the problem of finding a mapping of a
request graph (describing a workload) onto a substrate graph (describing the
physical infrastructure). Applications range from mapping testbeds (from where
the problem originated), over the embedding of batchprocessing workloads
(virtual clusters) to the embedding of service function chains. The different
applications come with their own specific requirements and constraints,
including node mapping constraints, routing policies, and latency constraints.
While the VNEP has been studied intensively over the last years, complexity
results are only known for specific models and we lack a comprehensive
understanding of its hardness.
This paper charts the complexity landscape of the VNEP by providing a
systematic analysis of the hardness of a wide range of VNEP variants, using a
unifying and rigorous proof framework. In particular, we show that the problem
of finding a feasible embedding is NPcomplete in general, and, hence, the VNEP
cannot be approximated under any objective, unless P=NP holds. Importantly, we
derive NPcompleteness results also for finding approximate embeddings, which
may violate, e.g., capacity constraints by certain factors. Lastly, we prove
that our results still pertain when restricting the request graphs to planar or
degreebounded graphs.

Many resource allocation problems in the cloud can be described as a basic
Virtual Network Embedding Problem (VNEP): finding mappings of request graphs
(describing the workloads) onto a substrate graph (describing the physical
infrastructure). In the offline setting, the two natural objectives are profit
maximization, i.e., embedding a maximal number of request graphs subject to the
resource constraints, and cost minimization, i.e., embedding all requests at
minimal overall cost. The VNEP can be seen as a generalization of classic
routing and call admission problems, in which requests are arbitrary graphs
whose communication endpoints are not fixed. Due to its applications, the
problem has been studied intensively in the networking community. However, the
underlying algorithmic problem is hardly understood.
This paper presents the first fixedparameter tractable approximation
algorithms for the VNEP. Our algorithms are based on randomized rounding. Due
to the flexible mapping options and the arbitrary request graph topologies, we
show that a novel linear program formulation is required. Only using this novel
formulation the computation of convex combinations of valid mappings is
enabled, as the formulation needs to account for the structure of the request
graphs. Accordingly, to capture the structure of request graphs, we introduce
the graphtheoretic notion of extraction orders and extraction width and show
that our algorithms have exponential runtime in the request graphs' maximal
width. Hence, for request graphs of fixed extraction width, we obtain the first
polynomialtime approximations.
Studying the new notion of extraction orders we show that (i) computing
extraction orders of minimal width is NPhard and (ii) that computing
decomposable LP solutions is in general NPhard, even when restricting request
graphs to planar ones.

Softwaredefined networking is considered a promising new paradigm, enabling
more reliable and formally verifiable communication networks. However, this
paper shows that the separation of the control plane from the data plane, which
lies at the heart of SoftwareDefined Networks (SDNs), introduces a new
vulnerability which we call \emph{teleportation}. An attacker (e.g., a
malicious switch in the data plane or a host connected to the network) can use
teleportation to transmit information via the control plane and bypass critical
network functions in the data plane (e.g., a firewall), and to violate security
policies as well as logical and even physical separations. This paper
characterizes the design space for teleportation attacks theoretically, and
then identifies four different teleportation techniques. We demonstrate and
discuss how these techniques can be exploited for different attacks (e.g.,
exfiltrating confidential data at high rates), and also initiate the discussion
of possible countermeasures. Generally, and given today's trend toward more
intentbased networking, we believe that our findings are relevant beyond the
use cases considered in this paper.

Modern computer networks support interesting new routing models in which
traffic flows from a source s to a destination t can be flexibly steered
through a sequence of waypoints, such as (hardware) middleboxes or
(virtualized) network functions, to create innovative network services like
service chains or segment routing. While the benefits and technological
challenges of providing such routing models have been articulated and studied
intensively over the last years, much less is known about the underlying
algorithmic traffic routing problems. This paper shows that the waypoint
routing problem features a deep combinatorial structure, and we establish
interesting connections to several classic graph theoretical problems. We find
that the difficulty of the waypoint routing problem depends on the specific
setting, and chart a comprehensive landscape of the computational complexity.
In particular, we derive several NPhardness results, but we also demonstrate
that exact polynomialtime algorithms exist for a wide range of practically
relevant scenarios.

Distributed evacuation of mobile robots is a recent development. We consider
the evacuation problem of two robots which are initially located at the center
of a unit disk. Both the robots have to evacuate the disk through the exits
situated on the perimeter of the disk at an unknown location. The distance
between two exits along the perimeter $d$ is given. We consider two different
communication models. First, in the wireless model, the robots can send a
message to each other over a long distance. Second, in facetoface
communication model, the robots can exchange information with each other only
when they touch each other. The objective of the evacuation problem is to
design an algorithm which minimizes the evacuation time of both the robots. For
the wireless communication model, we propose a generic algorithm for two robots
moving to two points on the perimeter with an initial separation of $\zeta \leq
d$. We also investigate evacuation problem for both unlabeled and labeled exits
in the wireless communication model. For the facetoface communication model,
we propose two different algorithms for $\zeta =0$ and $\zeta =d$ for unlabeled
exits. We also propose a generic algorithm for $\zeta \leq d$ for labeled
exits. We provide lower bounds corresponding to different $d$ values in the
facetoface communication model. We evaluate the performance our algorithms
with simulation for both of the communication models.

Changing a given configuration in a graph into another one is known as a re
configuration problem. Such problems have recently received much interest in
the context of algorithmic graph theory. We initiate the theoretical study of
the following reconfiguration problem: How to reroute $k$ unsplittable flows of
a certain demand in a capacitated network from their current paths to their
respective new paths, in a congestionfree manner? This problem finds immediate
applications, e.g., in traffic engineering in computer networks. We show that
the problem is generally NPhard already for $k = 2$ flows, which motivates us
to study rerouting on a most basic class of flow graphs, namely DAGs.
Interestingly, we find that for general $k$, deciding whether an unsplittable
multicommodity flow rerouting schedule exists, is NPhard even on DAGs. Both
NPhardness proofs are nontrivial. Our main contribution is a polynomialtime
(fixed parameter tractable) algorithm to solve the route update problem for a
bounded number of flows on DAGs. At the heart of our algorithm lies a novel
decomposition of the flow network that allows us to express and resolve
reconfiguration dependencies among flows.

The virtualization and softwarization of modern computer networks introduces
interesting new opportunities for a more flexible placement of network
functions and middleboxes (firewalls, proxies, traffic optimizers, virtual
switches, etc.). This paper studies approximation algorithms for the
incremental deployment of a minimum number of middleboxes at optimal locations,
such that capacity constraints at the middleboxes and length constraints on the
communication routes are respected. Our main contribution is a new, purely
combinatorial and rigorous proof for the submodularity of the function
maximizing the number of communication requests that can be served by a given
set of middleboxes. Our proof allows us to devise a deterministic approximation
algorithm which uses an augmenting path approach to compute the submodular
function. This algorithm does not require any changes to the locations of
existing middleboxes or the preemption of previously served communication pairs
when additional middleboxes are deployed, previously accepted communication
pairs just can be handed over to another middlebox. It is hence particularly
attractive for incremental deployments.We prove that the achieved
polynomialtime approximation bound is optimal, unless P = NP. This paper also
initiates the study of a weighted problem variant, in which entire groups of
nodes need to communicate via a middlebox (e.g., a multiplexer or a shared
object), possibly at different rates. We present an LP relaxation and
randomized rounding algorithm for this problem, leveraging an interesting
connection to scheduling.

The Minimum Dominating Set (MDS) problem is one of the most fundamental and
challenging problems in distributed computing. While it is wellknown that
minimum dominating sets cannot be approximated locally on general graphs, over
the last years, there has been much progress on computing local approximations
on sparse graphs, and in particular planar graphs.
In this paper we study distributed and deterministic MDS approximation
algorithms for graph classes beyond planar graphs. In particular, we show that
existing approximation bounds for planar graphs can be lifted to bounded genus
graphs, and present (1) a local constanttime, constantfactor MDS
approximation algorithm and (2) a local $\mathcal{O}(\log^*{n})$time
approximation scheme. Our main technical contribution is a new analysis of a
slightly modified variant of an existing algorithm by Lenzen et al.
Interestingly, unlike existing proofs for planar graphs, our analysis does not
rely on direct topological arguments.

We currently witness the emergence of interesting new network topologies
optimized towards the traffic matrices they serve, such as demandaware
datacenter interconnects (e.g., ProjecToR) and demandaware overlay networks
(e.g., SplayNets). This paper introduces a formal framework and approach to
reason about and design such topologies. We leverage a connection between the
communication frequency of two nodes and the path length between them in the
network, which depends on the entropy of the communication matrix. Our main
contribution is a novel robust, yet sparse, family of network topologies which
guarantee an expected path length that is proportional to the entropy of the
communication patterns.

Traditionally, networks such as datacenter interconnects are designed to
optimize worstcase performance under arbitrary traffic patterns. Such network
designs can however be far from optimal when considering the actual workloads
and traffic patterns which they serve. This insight led to the development of
demandaware datacenter interconnects which can be reconfigured depending on
the workload.
Motivated by these trends, this paper initiates the algorithmic study of
demandaware networks (DANs) designs, and in particular the design of
boundeddegree networks. The inputs to the network design problem are a
discrete communication request distribution, D, defined over communicating
pairs from the node set V , and a bound, d, on the maximum degree. In turn, our
objective is to design an (undirected) demandaware network N = (V,E) of
boundeddegree d, which provides short routing paths between frequently
communicating nodes distributed across N. In particular, the designed network
should minimize the expected path length on N (with respect to D), which is a
basic measure of the efficiency of the network.
We show that this fundamental network design problem exhibits interesting
connections to several classic combinatorial problems and to information
theory. We derive a general lower bound based on the entropy of the
communication pattern D, and present asymptotically optimal networkaware
design algorithms for important distribution families, such as sparse
distributions and distributions of locally bounded doubling dimensions.

We initiate the study of a natural and practically relevant new variant of
online caching where the tobecached items can have dependencies. We assume
that the universe is a tree T and items are tree nodes; we require that if a
node v is cached then the whole subtree T(v) rooted at v is cached as well.
This theoretical problem finds an immediate application in the context of
forwarding table optimization in IP routing and softwaredefined networks.
We present an elegant online deterministic algorithm TC for this problem, and
rigorously prove that its competitive ratio is O(height(T) *
k_ALG/(k_ALGk_OPT+1)), where k_ALG and k_OPT denote the cache sizes of an
online and the optimal offline algorithm, respectively. The result is optimal
up to a factor of O(height(T)).

Today's routing protocols critically rely on the assumption that the
underlying hardware is trusted. Given the increasing number of attacks on
network devices, and recent reports on hardware backdoors this assumption has
become questionable. Indeed, with the critical role computer networks play
today, the contrast between our security assumptions and reality is
problematic.
This paper presents SoftwareDefined Adversarial Trajectory Sampling
(SoftATS), an OpenFlowbased mechanism to efficiently monitor packet
trajectories, also in the presence of noncooperating or even adversarial
switches or routers, e.g., containing hardware backdoors. Our approach is based
on a secure, redundant and adaptive sample distribution scheme which allows us
to provably detect adversarial switches or routers trying to reroute, mirror,
drop, inject, or modify packets (i.e., header and/or payload). We evaluate the
effectiveness of our approach in different adversarial settings, report on a
proofofconcept implementation, and provide a first evaluation of the
performance overheads of such a scheme.

Ideally, by enabling multitenancy, network virtualization allows to improve
resource utilization, while providing performance isolation: although the
underlying resources are shared, the virtual network appears as a dedicated
network to the tenant. However, providing such an illusion is challenging in
practice, and over the last years, many expedient approaches have been proposed
to provide performance isolation in virtual networks, by enforcing bandwidth
reservations. We in this paper study another source for overheads and
unpredictable performance in virtual networks: the hypervisor.
The hypervisor is a critical component in multitenant environments, but its
overhead and influence on performance are hardly understood today. In
particular, we focus on OpenFlowbased virtualized Software Defined Networks
(vSDNs). Network virtualization is considered a killer application for SDNs: a
vSDN allows each tenant to flexibly manage its network from a logically
centralized perspective, via a simple API. For the purpose of our study, we
developed a new benchmarking tool for OpenFlow control and data planes,
enabling high and consistent OpenFlow message rates. Using our tool, we
identify and measure controllable and uncontrollable effects on performance and
overhead, including the hypervisor technology, the number of tenants as well as
the tenant type, as well as the type of OpenFlow messages.

The topological structure of complex networks has fascinated researchers for
several decades, resulting in the discovery of many universal properties and
reoccurring characteristics of different kinds of networks. However, much less
is known today about the network dynamics: indeed, complex networks in reality
are not static, but rather dynamically evolve over time.
Our paper is motivated by the empirical observation that network evolution
patterns seem far from random, but exhibit structure. Moreover, the specific
patterns appear to depend on the network type, contradicting the existence of a
"one fits it all" model. However, we still lack observables to quantify these
intuitions, as well as metrics to compare graph evolutions. Such observables
and metrics are needed for extrapolating or predicting evolutions, as well as
for interpolating graph evolutions.
To explore the many faces of graph dynamics and to quantify temporal changes,
this paper suggests to build upon the concept of centrality, a measure of node
importance in a network. In particular, we introduce the notion of centrality
distance, a natural similarity measure for two graphs which depends on a given
centrality, characterizing the graph type. Intuitively, centrality distances
reflect the extent to which (nonanonymous) node roles are different or, in
case of dynamic graphs, have changed over time, between two graphs.
We evaluate the centrality distance approach for five evolutionary models and
seven realworld social and physical networks. Our results empirically show the
usefulness of centrality distances for characterizing graph dynamics compared
to a nullmodel of random evolution, and highlight the differences between the
considered scenarios. Interestingly, our approach allows us to compare the
dynamics of very different networks, in terms of scale and evolution speed.

Virtual switches have become popular among cloud operating systems to
interconnect virtual machines in a more flexible manner. However, this paper
demonstrates that virtual switches introduce new attack surfaces in cloud
setups, whose effects can be disastrous. Our analysis shows that these
vulnerabilities are caused by: (1) inappropriate security assumptions
(privileged virtual switch execution in kernel and user space), (2) the logical
centralization of such networks (e.g., OpenStack or SDN), (3) the presence of
bidirectional communication channels between data plane systems and the
centralized controller, and (4) nonstandard protocol parsers.
Our work highlights the need to accommodate the data plane(s) in our threat
models. In particular, it forces us to revisit today's assumption that the data
plane can only be compromised by a sophisticated attacker: we show that
compromising the data plane of modern computer networks can actually be
performed by a very simple attacker with limited resources only and at low cost
(i.e., at the cost of renting a virtual machine in the Cloud). As a case study,
we fuzzed only 2\% of the codebase of a production quality virtual switch's
packet processor (namely OvS), identifying serious vulnerabilities leading to
unauthenticated remote code execution. In particular, we present the "rein
worm" which allows us to fully compromise testsetups in less than 100 seconds.
We also evaluate the performance overhead of existing mitigations such as ASLR,
PIEs, and unconditional stack canaries on OvS. We find that while applying
these countermeasures in kernelspace incurs a significant overhead, in
userspace the performance overhead is negligible.

Programmability and verifiability lie at the heart of the softwaredefined
networking paradigm. While OpenFlow and its matchaction concept provide
primitive operations to manipulate hardware configurations, over the last
years, several more expressive network programming languages have been
developed. This paper presents WNetKAT, the first network programming language
accounting for the fact that networks are inherently weighted, and
communications subject to capacity constraints (e.g., in terms of bandwidth)
and costs (e.g., latency or monetary costs). WNetKAT is based on a syntactic
and semantic extension of the NetKAT algebra. We demonstrate several relevant
applications for WNetKAT, including cost and capacityaware reachability, as
well as qualityofservice and fairness aspects. These applications do not only
apply to classic, splittable and unsplittable (s; t)flows, but also generalize
to more complex network functions and service chains. For example, WNetKAT
allows to model flows which need to traverse certain waypoint functions, which
may change the traffic rate. This paper also shows the relation between the
equivalence problem of WNetKAT and the equivalence problem of the weighted
finite automata, which implies undecidability of the former. However, this
paper also succeeds to prove the decidability of another useful problem, which
is sufficient in many practical scnearios: whether an expression equals to 0.
Moreover, we initiate the discussion of decidable subsets of the whole
language.

In this work, we propose utilizing the rich connectivity between IXPs and
ISPs for interdomain path stitching, supervised by centralized QoS brokers. In
this context, we highlight a novel abstraction of the Internet topology, i.e.,
the interIXP multigraph composed of IXPs and paths crossing the domains of
their shared member ISPs. This can potentially serve as a dense Internetwide
substrate for provisioning guaranteed endtoend (e2e) services with high path
diversity and global IPv4 address space reach. We thus map the IXP multigraph,
evaluate its potential, and introduce a rich algorithmic framework for path
stitching on such graph structures.

This paper presents the vision of the Control Exchange Point (CXP)
architectural model. The model is motivated by the inflexibility and
ossification of today's interdomain routing system, which renders critical
QoSconstrained endtoend (e2e) network services difficult or simply
impossible to provide. CXPs operate on slices of ISP networks and are built on
basic Software Defined Networking (SDN) principles, such as the clean
decoupling of the routing control plane from the data plane and the consequent
logical centralization of control. The main goal of the architectural model is
to provide e2e services with QoS constraints across domains. This is achieved
through defining a new type of business relationship between ISPs, which
advertise partial paths (socalled pathlets) with specific properties, and the
orchestrating role of the CXPs, which dynamically stitch them together and
provision e2e QoS. Revenue from valueadded services flows from the clients of
the CXP to the ISPs participating in the service. The novelty of the approach
is the combination of SDN programmability and dynamic path stitching techniques
for interdomain routing, which extends the value proposition of SDN over
multiple domains. We first describe the challenges related to e2e service
provision with the current interdomain routing and peering model, and then
continue with the benefits of our approach. Subsequently, we describe the CXP
model in detail and report on an initial feasibility analysis.

Modern Internet applications, from HD videoconferencing to health monitoring
and remote control of powerplants, pose stringent demands on network latency,
bandwidth and availability. An approach to support such applications and
provide interdomain guarantees, enabling new avenues for innovation, is using
centralized interdomain routing brokers. These entities centralize routing
control for missioncritical traffic across domains, working in parallel to
BGP. In this work, we propose using IXPs as natural points for stitching
interdomain paths under the control of interdomain routing brokers. To
evaluate the potential of this approach, we first map the global substrate of
interIXP pathlets that IXP members could offer, based on measurements for 229
IXPs worldwide. We show that using IXPs as stitching points has two useful
properties. Up to 91 % of the total IPv4 address space can be served by such
interdomain routing brokers when working in concert with just a handful of
large IXPs and their associated ISP members. Second, path diversity on the
interIXP graph increases by up to 29 times, as compared to current BGP
valleyfree routing. To exploit the rich path diversity, we introduce
algorithms that interdomain routing brokers can use to embed paths, subject to
bandwidth and latency constraints. We show that our algorithms scale to the
sizes of the measured graphs and can serve diverse simulated path request
mixes. Our work highlights a novel direction for SDN innovation across domains,
based on logically centralized control and programmable IXP fabrics.

The topological structure of complex networks has fascinated researchers for
several decades, resulting in the discovery of many universal properties and
reoccurring characteristics of different kinds of networks. However, much less
is known today about the network dynamics: indeed, complex networks in reality
are not static, but rather dynamically evolve over time.
Our paper is motivated by the empirical observation that network evolution
patterns seem far from random, but exhibit structure. Moreover, the specific
patterns appear to depend on the network type, contradicting the existence of a
"one fits it all" model. However, we still lack observables to quantify these
intuitions, as well as metrics to compare graph evolutions. Such observables
and metrics are needed for extrapolating or predicting evolutions, as well as
for interpolating graph evolutions.
To explore the many faces of graph dynamics and to quantify temporal changes,
this paper suggests to build upon the concept of centrality, a measure of node
importance in a network. In particular, we introduce the notion of centrality
distance, a natural similarity measure for two graphs which depends on a given
centrality, characterizing the graph type. Intuitively, centrality distances
reflect the extent to which (nonanonymous) node roles are different or, in
case of dynamic graphs, have changed over time, between two graphs.
We evaluate the centrality distance approach for five evolutionary models and
seven realworld social and physical networks. Our results empirically show the
usefulness of centrality distances for characterizing graph dynamics compared
to a nullmodel of random evolution, and highlight the differences between the
considered scenarios. Interestingly, our approach allows us to compare the
dynamics of very different networks, in terms of scale and evolution speed.

Computer networks today typically do not provide any mechanisms to the users
to learn, in a reliable manner, which paths have (and have not) been taken by
their packets. Rather, it seems inevitable that as soon as a packet leaves the
network card, the user is forced to trust the network provider to forward the
packets as expected or agreed upon. This can be undesirable, especially in the
light of today's trend toward more programmable networks: after a successful
cyber attack on the network management system or SoftwareDefined Network (SDN)
control plane, an adversary in principle has complete control over the network.
This paper presents a lowcost and efficient solution to detect misbehaviors
and ensure trustworthy routing over untrusted or insecure providers, in
particular providers whose management system or control plane has been
compromised (e.g., using a cyber attack). We propose
RoutingVerificationasaService (RVaaS): RVaaS offers clients a flexible
interface to query information relevant to their traffic, while respecting the
autonomy of the network provider. RVaaS leverages key features of
OpenFlowbased SDNs to combine (passive and active) configuration monitoring,
logical data plane verification and actual inband tests, in a novel manner.

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 selfstabilization
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 NorthSouth and WestEast, but without knowing which is which).
The problem turns out to be nontrivial, 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 selfstabilizing 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.