Author name cluster

Othon Michail

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

17 papers

2 author rows

TCS Journal 2025 Journal Article

All for one and one for all: An O(1)-musketeers generic transformation for rotating robots

Matthew Connor
Othon Michail
George Skretas

In this paper, we study the main open question of [Michail, Skretas, Spirakis, ICALP'17], asking what are the families of two-dimensional geometric shapes, drawn on a square grid, that can be transformed into each other by a sequence of rotation operations, none of which disconnects the shape. The model represents programmable matter systems consisting of interconnected robotic modules that perform the minimal mechanical operation of 90° rotations around each other. The goal is to transform an initial connected shape of modules A into a target connected shape B. Under the necessary assumption that the two shapes have identical colour cardinalities on a checkered colouring of the grid, and using at most a constant number of auxiliary modules to trigger the transformation, we prove that almost any pair of such shapes can be transformed into each other within an optimal O ( n 2 ) rotation operations none of which disconnects the shape.

Details DOI

NeurIPS Conference 2025 Conference Paper

Fair Minimum Labeling: Efficient Temporal Network Activations for Reachability and Equity

Lutz Oettershagen
Othon Michail

Balancing resource efficiency and fairness is critical in networked systems that support modern learning applications. We introduce the _Fair Minimum Labeling_ (FML) problem: the task of designing a minimum-cost temporal edge activation plan that ensures each group of nodes in a network has sufficient access to a designated target set, according to specified coverage requirements. FML captures key trade-offs in systems where edge activations incur resource costs and equitable access is essential, such as distributed data collection, update dissemination in edge-cloud systems, and fair service restoration in critical infrastructure. We show that FML is NP-hard and $\Omega(\log |V|)$-hard to approximate, where $V$ is the set of nodes, and we present probabilistic approximation algorithms that match this bound, achieving the best possible guarantee for the activation cost. We demonstrate the practical utility of FML in a fair multi-source data aggregation task for training a shared model. Empirical results show that FML enforces group-level fairness with substantially lower activation cost than baseline heuristics, underscoring its potential for building resource-efficient, equitable temporal reachability in learning-integrated networks.

PDF Details

TCS Journal 2025 Journal Article

On the exponential growth of geometric shapes

Nada Almalki
Siddharth Gupta
Othon Michail

In this paper, we explore the exponential growth of geometric structures starting from a single node, focusing on centralized growth operations. We identify a parameter k, representing the number of turning points within specific parts of a shape. We prove that, if edges can only be formed between a newly generated node and the node that created it and cannot be deleted, trees having at most k turning points on every root-to-leaf path can be grown in O ( k log ⁡ k + log ⁡ n ) time steps and spirals with O ( log ⁡ n ) turning points can be grown in O ( log ⁡ n ) time steps, n being the size of the final shape. For this model, we also show that the maximum number of turning points in a root-to-leaf path of a tree is a lower bound on the number of time steps to grow the tree and that there exists a class of paths such that any path in the class with k turning points requires Ω ( k log ⁡ k ) time steps to be grown. If nodes can additionally be connected as soon as they become adjacent, we prove that if a shape S has a spanning tree with at most k turning points on every root-to-leaf path, then the adjacency closure of S can be grown in O ( k log ⁡ k + log ⁡ n ) time steps. In the strongest version of the model, where, additionally, edges can be deleted and neighbors handed over to new nodes, we present a universal algorithm for growing any shape S exponentially fast.

Details DOI

TCS Journal 2024 Journal Article

On geometric shape construction via growth operations

Nada Almalki
Othon Michail

We study algorithmic growth processes under a geometric setting. Each process begins with an initial shape of nodes S I = S 0 and, in every time step t ≥ 1, by applying (in parallel) one or more growth operations of a specific type to the current shape, S t − 1, generates the next, S t, always satisfying | S t | > | S t − 1 |. We define three types of growth operations and explore the algorithmic and structural properties of their resulting processes. Our goal is to characterize the classes of shapes that can be constructed in O ( log ⁡ n ) or polylog n time steps, n being the size of the final shape S F. Moreover, we want to determine whether a given shape S F can be constructed from a given initial shape S I using a finite sequence of growth operations of a given type, called a constructor of S F. We give exact and partial characterizations of classes of shapes that can be constructed in polylog n time steps, polynomial-time centralized algorithms for deciding reachability between pairs of input shapes ( S I, S F ) and for generating constructors when S F can be constructed from S I, as well as some negative results.

Details DOI

TCS Journal 2023 Journal Article

Distributed transformations of Hamiltonian shapes based on line moves

Abdullah Almethen
Othon Michail
Igor Potapov

We consider a discrete system of n simple indistinguishable devices, called agents, forming a connected shape S I on a two-dimensional square grid. Agents are equipped with a linear-strength mechanism, called a line move, by which an agent can push a whole line of consecutive agents in one of the four cardinal directions in a single time-step. We study the problem of transforming an initial shape S I into a given target shape S F via a finite sequence of line moves in a distributed model, where each agent can observe the states of nearby agents in a Moore neighbourhood. We develop the first distributed connectivity-preserving transformation that exploits line moves. The transformation solves the line formation problem. That is, starting from any shape S I whose associated graph contains a Hamiltonian path known to them, the agents can form a final straight line S L. The complexity of the transformation is O ( n log 2 ⁡ n ) moves, which is asymptotically equivalent to that of the best-known centralised transformations.

Details DOI

I&C Journal 2023 Journal Article

Fault tolerant network constructors

Othon Michail
Paul G. Spirakis
Michail Theofilatos

We consider adversarial crash faults of nodes in the network constructors model [Michail and Spirakis, 2016]. We first show that, without further assumptions, the class of graph languages that can be (stably) constructed under crash faults is non-empty but small. On the positive side, linear waste enables the construction, on a fraction of the nodes, of any graph language that is constructible in the fault-free case and partial constructibility allows us to construct a large class of graph languages. We then extend the original model with a minimal form of fault notifications. Our main result under that model is a fault-tolerant universal constructor. Finally, we show that logarithmic local memories can be exploited for a no-waste fault-tolerant simulation of any network constructor.

Details DOI

TCS Journal 2022 Journal Article

Centralised connectivity-preserving transformations for programmable matter: A minimal seed approach

Matthew Connor
Othon Michail
Igor Potapov

We study a model of programmable matter systems consisting of n devices lying on a 2-dimensional square grid which are able to perform the minimal mechanical operation of rotating around each other. The goal is to transform an initial shape A into a target shape B. We investigate the class of shapes which can be constructed in such a scenario under the additional constraint of maintaining global connectivity at all times. We focus on the scenario of transforming nice shapes, a class of shapes consisting of a central line L where for all nodes u in S either u ∈ L or u is connected to L by a line of nodes perpendicular to L. We prove that by introducing a minimal 3-node seed it is possible for the canonical shape of a line of n nodes to be transformed into a nice shape of n − 1 nodes. We use this to show that a 4-node seed enables the transformation of nice shapes of size n into any other nice shape of size n in O ( n 2 ) time. We leave as an open problem the expansion of the class of shapes which can be constructed using such a seed to include those derived from nice shapes.

Details DOI

TCS Journal 2022 Journal Article

On efficient connectivity-preserving transformations in a grid

Abdullah Almethen
Othon Michail
Igor Potapov

We consider a discrete system of n devices lying on a 2-dimensional square grid and forming an initial connected shape S I. Each device is equipped with a linear-strength mechanism which enables it to move a whole line of consecutive devices in a single time-step, called a line move. We study the problem of transforming S I into a given connected target shape S F of the same number of devices, via a finite sequence of line moves. Our focus is on designing centralised transformations aiming at minimising the total number of moves subject to the constraint of preserving connectivity of the shape throughout the course of the transformation. We first give very fast connectivity-preserving transformations for the case in which the associated graphs of S I and S F contain a Hamiltonian path. In particular, our transformations make O ( n log ⁡ n ) moves, which is asymptotically equal to the best known running time of connectivity-breaking transformations. Our most general result is then a connectivity-preserving universal transformation that can transform any initial connected shape S I into any target connected shape S F, through a sequence of O ( n n ) moves.

Details DOI

I&C Journal 2022 Journal Article

Simple and fast approximate counting and leader election in populations

Othon Michail
Paul G. Spirakis
Michail Theofilatos

We study leader election and population size counting for population protocols: networks of finite-state anonymous agents that interact randomly. We provide simple protocols for approximate counting of the size of the population and for leader election. We show a protocol for leader election that terminates in O ( log 2 ⁡ n log ⁡ m ) parallel time, where m is a parameter that belongs to Ω ( log ⁡ n ) and O ( n ), using O ( max ⁡ { log ⁡ m, log ⁡ log ⁡ n } ) bits. By adjusting m between log ⁡ n and n, we obtain a leader election protocol whose time and space can be smoothly traded off between O ( log 2 ⁡ n log ⁡ log ⁡ n ) to O ( log ⁡ n ) time and O ( log ⁡ log ⁡ n ) to O ( log ⁡ n ) bits. We also give a protocol which provides a constant factor approximation of log ⁡ n of the population size n, or an upper bound n e which is at most n a for some constant a > 1. This protocol assumes the existence of a unique leader and stabilizes in Θ ( log ⁡ n ) parallel time.

Details DOI

TCS Journal 2020 Journal Article

Pushing lines helps: Efficient universal centralised transformations for programmable matter

Abdullah Almethen
Othon Michail
Igor Potapov

In this work, we study a discrete system of entities residing on a two-dimensional square grid. Each entity is modelled as a node occupying a distinct cell of the grid. The set of all n nodes forms initially a connected shape A. Entities are equipped with a linear-strength pushing mechanism that can push a whole line of entities in parallel in a single time-step on one position in a given (one of the four possible) direction of a grid. A target connected shape B is also provided and the goal is to transform A into B via a sequence of line moves. Existing models based on local movement of individual nodes, such as rotating or sliding a single node, can be shown to be special cases of the present model, therefore their (inefficient, Θ ( n 2 ) -time) universal transformations carry over. Our main goal is to investigate whether the parallelism inherent in this new type of movement can be exploited for efficient, i. e. , sub-quadratic worst-case, transformations. This paper provides several solutions for specific and universal centralised transformations in the context of the new model. In particular we first design O ( n log ⁡ n ) -time universal transformation without preserving the connectivity of original shape. Then we focus on transformations which preserve the connectivity of the shape throughout its course and develop an O ( n n ) -time transformation for the apparently hard instance of transforming a diagonal A into a straight line B.

Details DOI

TCS Journal 2017 Journal Article

Connectivity preserving network transformers

Othon Michail
Paul G. Spirakis

The Population Protocol model is a distributed model that concerns systems of very weak computational entities that cannot control the way they interact. The model of Network Constructors is a variant of Population Protocols capable of (algorithmically) constructing abstract networks. Both models are characterized by a fundamental inability to terminate. In this work, we investigate the minimal strengthenings of the latter model that could overcome this inability. Our main conclusion is that initial connectivity of the communication topology combined with the ability of the protocol to transform the communication topology and the ability of a node to detect when its degree is equal to a small constant, plus either a unique leader or the ability of detecting common neighbors, are sufficient to guarantee not only termination but also the maximum computational power that one can hope for in this family of models. The technique of our protocols is to transform any initial connected topology to a less symmetric (that can serve as a large ordered memory) and detectable (that the protocol can determine its successful construction) topology without ever breaking its connectivity during the transformation. The target topology of all of our transformers is the spanning line and we call Terminating Line Transformation the corresponding problem. We first study the case in which there is a pre-elected unique leader and give a time-optimal protocol for Terminating Line Transformation. We then prove that dropping the leader without additional assumptions leads to a strong impossibility result. In an attempt to overcome this, we equip the nodes with the ability to tell, during their pairwise interactions, whether they have at least one neighbor in common. Interestingly, it turns out that this local and realistic mechanism is sufficient to make the problem solvable. In particular, we give a very efficient protocol that solves Terminating Line Transformation when all nodes are initially identical. The latter implies the aforementioned strong characterization: the model, under a few minimal assumptions, computes with termination any symmetric predicate computable by a Turing Machine of space Θ ( n 2 ).

Details DOI

TCS Journal 2016 Journal Article

Traveling salesman problems in temporal graphs

Othon Michail
Paul G. Spirakis

In this work, we introduce the notion of time to some well-known combinatorial optimization problems. In particular, we study problems defined on temporal graphs. A temporal graph D = ( V, A ) may be viewed as a time-sequence G 1, G 2, …, G l of static graphs over the same (static) set of nodes V. Each G t = D ( t ) = ( V, A ( t ) ) is called the instance of D at time t and l is called the lifetime of D. Our main focus is on analogues of traveling salesman problems in temporal graphs. A sequence of time-labeled edges (e. g. a tour) is called temporal if its labels are strictly increasing. We begin by considering the problem of exploring the nodes of a temporal graph as soon as possible. In contrast to the positive results known for the static case, we prove that, it cannot be approximated within cn, for some constant c > 0, in a special case of temporal graphs and within ( 2 − ε ), for every constant ε > 0, in another special case in which D ( t ) is strongly connected for all 1 ≤ t ≤ l, both unless P = NP. We then study the temporal analogue of TSP ( 1, 2 ), abbreviated TTSP ( 1, 2 ), where, for all 1 ≤ t ≤ l, D ( t ) is a complete weighted graph with edge-costs from { 1, 2 } and the cost of an edge may vary from instance to instance. The goal is to find a minimum cost temporal TSP tour. We give several polynomial-time approximation algorithms for TTSP ( 1, 2 ). Our best approximation is ( 1. 7 + ε ) for the generic TTSP ( 1, 2 ) and ( 13 / 8 + ε ) for its interesting special case in which the lifetime of the temporal graph is restricted to n. In the way, we also introduce temporal versions of other fundamental combinatorial optimization problems, for which we obtain polynomial-time approximation algorithms and hardness results.

Details DOI

TCS Journal 2013 Journal Article

The computational power of simple protocols for self-awareness on graphs

Ioannis Chatzigiannakis
Othon Michail
Stavros Nikolaou
Paul G. Spirakis

We explore the capability of a network of extremely limited computational entities to decide properties about itself or any of its subnetworks. We consider that the underlying network of the interacting entities (devices, agents, processes etc.) is modeled by an interaction graph that reflects the network’s connectivity. We examine the following two cases: First, we consider the case where the input graph is the whole interaction graph and second where it is some subgraph of the interaction graph given by some preprocessing on the network. In each case, we devise simple graph protocols that can decide properties of the input graph. The computational entities, that are called agents, are modeled as finite-state automata and run the same global graph protocol. Each protocol is a fixed size grammar, that is, its description is independent of the size (number of agents) of the network. This size is not known by the agents. We present two simple models (one for each case), the Graph Decision Mediated Population Protocol (GDMPP) and the Mediated Graph Protocol (MGP) models, similar to the Population Protocol model of Angluin et al. , where each network link (edge of the interaction graph) is characterized by a state taken from a finite set. This state can be used and updated during each interaction between the corresponding agents. We provide some example protocols and some interesting properties for the two models concerning the computability of graph languages in various settings (disconnected input graphs, stabilizing input graphs). We show that the computational power within the family of all (at least) weakly-connected input graphs is fairly restricted. Finally, we give an exact characterization of the class of graph languages decidable by the MGP model in the case of complete interaction graphs: it is equal to the class of graph languages decidable by a nondeterministic Turing Machine of linear space that receives its input graph by its adjacency matrix representation.

Details DOI

TCS Journal 2011 Journal Article

Mediated population protocols

Othon Michail
Ioannis Chatzigiannakis
Paul G. Spirakis

We extend here the Population Protocol (PP) model of Angluin et al. (2004, 2006) [2, 4] in order to model more powerful networks of resource-limited agents that are possibly mobile. The main feature of our extended model, called the Mediated Population Protocol (MPP) model, is to allow the edges of the interaction graph to have states that belong to a constant-size set. We then allow the protocol rules for pairwise interactions to modify the corresponding edge state. The descriptions of our protocols preserve both the uniformity and anonymity properties of PPs, that is, they do not depend on the size of the population and do not use unique identifiers. We focus on the computational power of the MPP model on complete interaction graphs and initially identical edges. We provide the following exact characterization of the class MPS of stably computable predicates: a predicate is in MPS iff it is symmetric and is in NSPACE ( n 2 ).

Details DOI

TCS Journal 2011 Journal Article

Passively mobile communicating machines that use restricted space

Ioannis Chatzigiannakis
Othon Michail
Stavros Nikolaou
Andreas Pavlogiannis
Paul G. Spirakis

We propose a new theoretical model for passively mobile wireless sensor networks, called P M, standing for passively mobile machines. The main modification w. r. t. the population protocol model (Angluin et al. , 2006) [30] is that agents now, instead of being automata, are Turing Machines. We provide general definitions for unbounded memories, but we are mainly interested in computations upper-bounded by plausible space limitations. However, we prove that our results hold for more general cases. We focus on complete interaction graphs and define the complexity classes PMSPACE ( f ( n ) ) parametrically, consisting of all predicates that are stably computable by some PM protocol that uses O ( f ( n ) ) memory in each agent. We provide a protocol that generates unique identifiers from scratch only by using O ( log n ) memory, and use it to provide an exact characterization of the classes PMSPACE ( f ( n ) ) when f ( n ) = Ω ( log n ): they are precisely the classes of all symmetric predicates in NSPACE ( n f ( n ) ). As a consequence, we obtain a space hierarchy of the PM model when the memory bounds are Ω ( log n ). We next explore the computability of the PM model when the protocols use o ( log log n ) space per machine and prove that SEM = PMSPACE ( f ( n ) ) when f ( n ) = o ( log log n ), where SEM denotes the class of the semilinear predicates. Finally, we establish that the minimal space requirement for the computation of non-semilinear predicates is O ( log log n ).

Details DOI

MFCS Conference 2010 Conference Paper

All Symmetric Predicates in NSPACE ( n 2 ) Are Stably Computable by the Mediated Population Protocol Model

Ioannis Chatzigiannakis
Othon Michail
Stavros Nikolaou
Andreas Pavlogiannis
Paul G. Spirakis

Abstract This work focuses on the computational power of the Mediated Population Protocol model on complete communication graphs and initially identical edges ( SMPP ). In particular, we investigate the class MPS of all predicates that are stably computable by the SMPP model. It is already known that MPS is in the symmetric subclass of NSPACE ( n 2 ). Here we prove that this inclusion holds with equality, thus, providing the following exact characterization for MPS: A predicate is in MPS iff it is symmetric and is in NSPACE ( n 2 ).

Details

MFCS Conference 2009 Invited Paper

Recent Advances in Population Protocols

Ioannis Chatzigiannakis
Othon Michail
Paul G. Spirakis

Abstract The population protocol model (PP) proposed by Angluin et al. [2] describes sensor networks consisting of passively mobile finite-state agents. The agents sense their environment and communicate in pairs to carry out some computation on the sensed values. The mediated population protocol model (MPP) [13] extended the PP model by communication links equipped with a constant size buffer. The MPP model was proved in [13] to be stronger than the PP model. However, its most important contribution is that it provides us with the ability to devise optimizing protocols, approximation protocols and protocols that decide properties of the communication graph on which they run. The latter case, suggests a simplified model, the GDM model, that was formally defined and studied in [11]. GDM is a special case of MPP that captures MPP’s ability to decide properties of the communication graph. Here we survey recent advances in the area initiated by the proposal of the PP model and at the same time we provide new protocols, novel ideas and results.

Details