BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Othon Michail

Othon Michail appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Distributed, Parallel, and Cluster ComputingData Structures and AlgorithmsComputational GeometryRoboticsComputational ComplexityDiscrete MathematicsMultiagent Systems

Catalog footprint

What is connected

16works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2022arXiv

Centralised Connectivity-Preserving Transformations by Rotation: 3 Musketeers for all Orthogonal Convex Shapes

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 are interested in characterising the class of shapes which can be transformed into each other in such a scenario, under the additional constraint of maintaining global connectivity at all times. This was one of the main problems left open by $[$Michail et al., JCSS'19$]$. Note that the considered question is about structural feasibility of transformations, which we exclusively deal with via centralised constructive proofs. Distributed solutions are left for future work and form an interesting research direction. Past work made some progress for the special class of nice shapes. We here consider the class of orthogonal convex shapes, where for any two nodes $u, v$ in a horizontal or vertical line on the grid, there is no empty cell between $u$ and $v$. We develop a generic centralised transformation and prove that, for any pair $A$, $B$ of colour-consistent orthogonal convex shapes, it can transform $A$ into $B$. In light of the existence of blocked shapes in the considered class, we use a minimal 3-node seed to trigger the transformation. The running time of our transformation is an optimal $O(n^2)$ sequential moves, where $n=|A|=|B|$. We leave as an open problem the existence of a universal connectivity-preserving transformation with a small seed. Our belief is that the techniques developed in this paper might prove useful to answer this.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On Geometric Shape Construction via Growth Operations

In this work, we investigate novel algorithmic growth processes. In particular, we propose three growth operations, full doubling, RC doubling and doubling, and explore the algorithmic and structural properties of their resulting processes under a geometric setting. In terms of modeling, our system runs on a 2-dimensional grid and operates in discrete time-steps. The process begins with an initial shape $S_I=S_0$ and, in every time-step $t \geq 1$, by applying (in parallel) one or more growth operations of a specific type to the current shape-instance $S_{t-1}$, generates the next instance $S_t$, always satisfying $|S_t| > |S_{t-1}|$. Our goal is to characterize the classes of shapes that can be constructed in $O(\log n)$ or polylog $n$ time-steps and determine whether a final shape $S_F$ can be constructed from an initial shape $S_I$ using a finite sequence of growth operations of a given type, called a constructor of $S_F$. For full doubling, in which, in every time-step, every node generates a new node in a given direction, we completely characterize the structure of the class of shapes that can be constructed from a given initial shape. For RC doubling, in which complete columns or rows double, our main contribution is a linear-time centralized algorithm that for any pair of shapes $S_I$, $S_F$ decides if $S_F$ can be constructed from $S_I$ and, if the answer is yes, returns an $O(\log n)$-time-step constructor of $S_F$ from $S_I$. For the most general doubling operation, where up to individual nodes can double, we show that some shapes cannot be constructed in sub-linear time-steps and give two universal constructors of any $S_F$ from a singleton $S_I$, which are efficient (i.e., up to polylogarithmic time-steps) for large classes of shapes. Both constructors can be computed by polynomial-time centralized algorithms for any shape $S_F$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distributed Computation and Reconfiguration in Actively Dynamic Networks

In this paper, we study systems of distributed entities that can actively modify their communication network. This gives rise to distributed algorithms that apart from communication can also exploit network reconfiguration in order to carry out a given task. At the same time, the distributed task itself may now require global reconfiguration from a given initial network $G_s$ to a target network $G_f$ from a family of networks having some good properties, like small diameter. With reasonably powerful computational entities, there is a straightforward algorithm that transforms any $G_s$ into a spanning clique in $O(\log n)$ time. The algorithm can then compute any global function on inputs and reconfigure to any target network in one round. We argue that such a strategy is impractical for real applications. In real dynamic networks there is a cost associated with creating and maintaining connections. To formally capture such costs, we define three edge-complexity measures: the \emph{total edge activations}, the \emph{maximum activated edges per round}, and the \emph{maximum activated degree of a node}. The clique formation strategy highlighted above, maximizes all of them. We aim at improved algorithms that achieve (poly)log$(n)$ time while minimizing the edge-complexity for the general task of transforming any $G_s$ into a $G_f$ of diameter (poly)log$(n)$. We give three distributed algorithms. The first runs in $O(\log n)$ time, with at most $2n$ active edges per round, an optimal total of $O(n\log n)$ edge activations, a maximum degree $n-1$, and a target network of diameter 2. The second achieves bounded degree by paying an additional logarithmic factor in time and in total edge activations and gives a target network of diameter $O(\log n)$. Our third algorithm shows that if we slightly increase the maximum degree to polylog$(n)$ then we can achieve a running time of $o(\log^2 n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Gathering in 1-Interval Connected Graphs

We examine the problem of gathering $k \geq 2$ agents (or multi-agent rendezvous) in dynamic graphs which may change in every synchronous round but remain always connected ($1$-interval connectivity) [KLO10]. The agents are identical and without explicit communication capabilities, and are initially positioned at different nodes of the graph. The problem is for the agents to gather at the same node, not fixed in advance. We first show that the problem becomes impossible to solve if the graph has a cycle. In light of this, we study a relaxed version of this problem, called weak gathering. We show that only in unicyclic graphs weak gathering is solvable, and we provide a deterministic algorithm for this problem that runs in polynomial number of rounds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Efficient Connectivity-Preserving Transformations in a Grid

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. 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 \emph{line moves}. Our focus is on designing \emph{centralised} transformations aiming at \emph{minimising the total number of moves} subject to the constraint of \emph{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 \emph{associated graphs} of $ S_I $ and $ S_F $ are isomorphic to a Hamiltonian line. 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 \emph{universal transformation} that can transform any initial connected shape $ S_I $ into any target connected shape $ S_F $, through a sequence of $O(n\sqrt{n})$ moves. Finally, we establish $Ω(n \log n)$ lower bounds for two restricted sets of transformations. These are the first lower bounds for this model and are matching the best known $ O(n \log n) $ upper bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Distributed Construction of Stable Networks in Polylogarithmic Parallel Time

We study the class of networks which can be created in polylogarithmic parallel time by network constructors: groups of anonymous agents that interact randomly under a uniform random scheduler with the ability to form connections between each other. Starting from an empty network, the goal is to construct a stable network which belongs to a given family. We prove that the class of trees where each node has any k >= 2 children can be constructed in O(log n) parallel time with high probability. We show that constructing networks which are k-regular is Omega(n) time, but a minimal relaxation to (l, k)-regular networks, where l = k - 1 can be constructed in polylogarithmic parallel time for any fixed k, where k > 2. We further demonstrate that when the finite-state assumption is relaxed and k is allowed to grow with n, then k = log log n acts as a threshold above which network construction is again polynomial time. We use this to provide a partial characterisation of the class of polylogarithmic time network constructors.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

How Many Cooks Spoil the Soup?

In this work, we study the following basic question: "How much parallelism does a distributed task permit?" Our definition of parallelism (or symmetry) here is not in terms of speed, but in terms of identical roles that processes have at the same time in the execution. We initiate this study in population protocols, a very simple model that not only allows for a straightforward definition of what a role is, but also encloses the challenge of isolating the properties that are due to the protocol from those that are due to the adversary scheduler, who controls the interactions between the processes. We (i) give a partial characterization of the set of predicates on input assignments that can be stably computed with maximum symmetry, i.e., $Θ(N_{min})$, where $N_{min}$ is the minimum multiplicity of a state in the initial configuration, and (ii) we turn our attention to the remaining predicates and prove a strong impossibility result for the parity predicate: the inherent symmetry of any protocol that stably computes it is upper bounded by a constant that depends on the size of the protocol.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An Introduction to Temporal Graphs: An Algorithmic Perspective

A \emph{temporal graph} is, informally speaking, a graph that changes with time. When time is discrete and only the relationships between the participating entities may change and not the entities themselves, a temporal graph may be viewed as a sequence $G_1,G_2\ldots,G_l$ of static graphs over the same (static) set of nodes $V$. Though static graphs have been extensively studied, for their temporal generalization we are still far from having a concrete set of structural and algorithmic principles. Recent research shows that many graph properties and problems become radically different and usually substantially more difficult when an extra time dimension in added to them. Moreover, there is already a rich and rapidly growing set of modern systems and applications that can be naturally modeled and studied via temporal graphs. This, further motivates the need for the development of a temporal extension of graph theory. We survey here recent results on temporal graphs and temporal graph problems that have appeared in the Computer Science community.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Connectivity Preserving Network Transformers

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 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 plus a few other local and realistic assumptions 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 is to transform any initial connected topology to a less symmetric and detectable 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 that the model computes with termination any symmetric predicate computable by a Turing Machine of space $Θ(n^2)$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

NETCS: A New Simulator of Population Protocols and Network Constructors

Network Constructors are an extension of the standard population protocol model in which finite-state agents interact in pairs under the control of an adversary scheduler. In this work we present NETCS, a simulator designed to evaluate the performance of various network constructors and population protocols under different schedulers and network configurations. Our simulator provides researchers with an intuitive user interface and a quick experimentation environment to evaluate their work. It also harnesses the power of the cloud, as experiments are executed remotely and scheduled through the web interface provided. To prove the validity and quality of our simulator we provide an extensive evaluation of multiple protocols with more than 100000 experiments for different network sizes and configurations that validate the correctness of the theoretical analysis of existing protocols and estimate the real values of the hidden asymptotic coefficients. We also show experimentally (with more than 40000 experiments) that a probabilistic algorithm is capable of counting the actual size of the network in bounded time given a unique leader.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Terminating Distributed Construction of Shapes and Patterns in a Fair Solution of Automata

We consider a solution of automata similar to Population Protocols and Network Constructors. The automata (or nodes) move passively in a well-mixed solution and can cooperate by interacting in pairs. Every such interaction may result in an update of the local states of the nodes. Additionally, the nodes may also choose to connect to each other in order to start forming some required structure. We may think of such nodes as the smallest possible programmable pieces of matter. The model that we introduce here is a more applied version of Network Constructors, imposing physical (or geometrical) constraints on the connections. Each node can connect to other nodes only via a very limited number of local ports, therefore at any given time it has only a bounded number of neighbors. Connections are always made at unit distance and are perpendicular to connections of neighboring ports. We show that this restricted model is still capable of forming very practical 2D or 3D shapes. We provide direct constructors for some basic shape construction problems. We then develop new techniques for determining the constructive capabilities of our model. One of the main novelties of our approach, concerns our attempt to overcome the inability of such systems to detect termination. In particular, we exploit the assumptions that the system is well-mixed and has a unique leader, in order to give terminating protocols that are correct with high probability (w.h.p.). This allows us to develop terminating subroutines that can be sequentially composed to form larger modular protocols. One of our main results is a terminating protocol counting the size $n$ of the system w.h.p.. We then use this protocol as a subroutine in order to develop our universal constructors, establishing that the nodes can self-organize w.h.p. into arbitrarily complex shapes while still detecting termination of the construction.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Simple and Efficient Local Codes for Distributed Stable Network Construction

In this work, we study protocols so that populations of distributed processes can construct networks. In order to highlight the basic principles of distributed network construction we keep the model minimal in all respects. In particular, we assume finite-state processes that all begin from the same initial state and all execute the same protocol (i.e. the system is homogeneous). Moreover, we assume pairwise interactions between the processes that are scheduled by an adversary. The only constraint on the adversary scheduler is that it must be fair. In order to allow processes to construct networks, we let them activate and deactivate their pairwise connections. When two processes interact, the protocol takes as input the states of the processes and the state of the their connection and updates all of them. Initially all connections are inactive and the goal is for the processes, after interacting and activating/deactivating connections for a while, to end up with a desired stable network. We give protocols (optimal in some cases) and lower bounds for several basic network construction problems such as spanning line, spanning ring, spanning star, and regular network. We provide proofs of correctness for all of our protocols and analyze the expected time to convergence of most of them under a uniform random scheduler that selects the next pair of interacting processes uniformly at random from all such pairs. Finally, we prove several universality results by presenting generic protocols that are capable of simulating a Turing Machine (TM) and exploiting it in order to construct a large class of networks.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Causality, Influence, and Computation in Possibly Disconnected Dynamic Networks

In this work, we study the propagation of influence and computation in dynamic distributed systems. We focus on broadcasting models under a worst-case dynamicity assumption which have received much attention recently. We drop for the first time in worst-case dynamic networks the common instantaneous connectivity assumption and require a minimal temporal connectivity. Our temporal connectivity constraint only requires that another causal influence occurs within every time-window of some given length. We establish that there are dynamic graphs with always disconnected instances with equivalent temporal connectivity to those with always connected instances. We present a termination criterion and also establish the computational equivalence with instantaneous connectivity networks. We then consider another model of dynamic networks in which each node has an underlying communication neighborhood and the requirement is that each node covers its local neighborhood within any time-window of some given length. We discuss several properties and provide a protocol for counting, that is for determining the number of nodes in the network.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Naming and Counting in Anonymous Unknown Dynamic Networks

In this work, we study the fundamental naming and counting problems (and some variations) in networks that are anonymous, unknown, and possibly dynamic. In counting, nodes must determine the size of the network n and in naming they must end up with unique identities. By anonymous we mean that all nodes begin from identical states apart possibly from a unique leader node and by unknown that nodes have no a priori knowledge of the network (apart from some minimal knowledge when necessary) including ignorance of n. Network dynamicity is modeled by the 1-interval connectivity model, in which communication is synchronous and a worst-case adversary chooses the edges of every round subject to the condition that each instance is connected. We first focus on static networks with broadcast where we prove that, without a leader, counting is impossible to solve and that naming is impossible to solve even with a leader and even if nodes know n. These impossibilities carry over to dynamic networks as well. We also show that a unique leader suffices in order to solve counting in linear time. Then we focus on dynamic networks with broadcast. We conjecture that dynamicity renders nontrivial computation impossible. In view of this, we let the nodes know an upper bound on the maximum degree that will ever appear and show that in this case the nodes can obtain an upper bound on n. Finally, we replace broadcast with one-to-each, in which a node may send a different message to each of its neighbors. Interestingly, this natural variation is proved to be computationally equivalent to a full-knowledge model, in which unique names exist and the size of the network is known.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Passively Mobile Communicating Logarithmic Space Machines

We propose a new theoretical model for passively mobile Wireless Sensor Networks. We call it the PALOMA model, standing for PAssively mobile LOgarithmic space MAchines. The main modification w.r.t. the Population Protocol model is that agents now, instead of being automata, are Turing Machines whose memory is logarithmic in the population size n. Note that the new model is still easily implementable with current technology. We focus on complete communication graphs. We define the complexity class PLM, consisting of all symmetric predicates on input assignments that are stably computable by the PALOMA model. We assume that the agents are initially identical. Surprisingly, it turns out that the PALOMA model can assign unique consecutive ids to the agents and inform them of the population size! This allows us to give a direct simulation of a Deterministic Turing Machine of O(nlogn) space, thus, establishing that any symmetric predicate in SPACE(nlogn) also belongs to PLM. We next prove that the PALOMA model can simulate the Community Protocol model, thus, improving the previous lower bound to all symmetric predicates in NSPACE(nlogn). Going one step further, we generalize the simulation of the deterministic TM to prove that the PALOMA model can simulate a Nondeterministic TM of O(nlogn) space. Although providing the same lower bound, the important remark here is that the bound is now obtained in a direct manner, in the sense that it does not depend on the simulation of a TM by a Pointer Machine. Finally, by showing that a Nondeterministic TM of O(nlogn) space decides any language stably computable by the PALOMA model, we end up with an exact characterization for PLM: it is precisely the class of all symmetric predicates in NSPACE(nlogn).

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Passively Mobile Communicating Machines that Use Restricted Space

We propose a new theoretical model for passively mobile Wireless Sensor Networks, called PM, standing for Passively mobile Machines. The main modification w.r.t. the Population Protocol model 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 communication 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 on each agent. We provide a protocol that generates unique ids from scratch only by using O(log n) memory, and use it to provide an exact characterization for the classes PMSPACE(f(n)) when f(n)=Ω(log n): they are precisely the classes of all symmetric predicates in NSPACE(nf(n)). In this way, we provide a space hierarchy for the PM model when the memory bounds are Ω(log n). Finally, we explore the computability of the PM model when the protocols use o(loglog n) space per machine and prove that SEMILINEAR=PMSPACE(f(n)) when f(n)=o(loglog n), where SEMILINEAR denotes the class of the semilinear predicates. In fact, we prove that this bound acts as a threshold, so that SEMILINEAR is a proper subset of PMSPACE(f(n)) when f(n)=O(loglog n).

0 citations0 reviewsNo code linkedOpen access