Paola Flocchini

Self-deployment Algorithms for Mobile Sensors on a Ring (2009)

We study the computability and complexity of the exploration problem in a class of highly dynamic graphs: periodically varying (PV) graphs, where the edges exist only at some (unknown) times defined...

Distributed Computation of All Node Replacements of a Minimum Spanning Tree ⋆ (2009)

Abstract. We consider the self-deployment problem in a ring for a network of identical sensors: starting from some initial random placement in the ring, the sensors in the network must move, in a...

Paola Flocchini, Toni Mesa Enriquez, Linda Pagli, Nicola Santoro

Abstract. In many network applications the computation takes place on the minimum-cost spanning tree (MST) of the network; unfortunately, a single link or node failure disconnects the tree. In this...

ORIGINAL ARTICLE (2009)

Stefan Dobrev, Paola Flocchini, Nicola Santoro, P. Flocchini, G. Prencipe, N. Santoro

Searching for a black hole in arbitrary networks: optimal mobile agents protocols

Chapter 1 Pattern Formation by Autonomous Mobile Robots (2009)

153 EFFICIENT PROTOCOLS FOR COMPUTING THE OPTIMAL SWAP EDGES OF A SHORTEST PATH TREE (2009)

A group of mobile autonomous robots, each with very limited capabilities, can form (complex) patterns in the space it occupies. These patterns can be used to program the robots to accomplish...

Paola Flocchini, Antonio Mesa Enriques, Linda Pagli, Nicola Santoro

Keywords: We consider the problem of computing the optimal swap edges of a shortest-path tree. This theoretical problem arises in practice in systems that offer point-offailure shortest-path...

Multiple Agents RendezVous in a Ring in Spite of a (2009)

Black Hole, Stefan Dobrev, Paola Flocchini, Nicola Santoro

Abstract. The Rendezvous of anonymous mobile agents in a anonymous network is an intensively studied problem; it calls for k anonymous, mobile agents to gather in the same site. We study this problem...

Arbitrary Pattern Formation by Asynchronous, Anonymous, Oblivious Robots ∗ (2009)

Abstract. In this paper we address the problem of mobile agents searching for a highly harmful item (called a black hole) in a ring network. The black hole is a stationary process that destroys...

Dynamic Monopolies in Tori \Lambda (2008)

From an engineering point of view, the problem of coordinating a set of autonomous, mobile robots for the purpose of cooperatively performing a task has been studied extensively over the past decade....

Paola Flocchini, Elena Lodi, Fabrizio Luccio, Linda Pagliz, Nicola Santoro

1 1 Introduction In majority-based distributed systems and communication networks, faulty elements can induce a faulty behavior in their neighbors.

Exploring an Unknown Graph to Locate a Black Hole Using Tokens (2008)

Stefan Dobrev, Paola Flocchini, Rastislav Královič, Nicola Santoro

Abstract. Consider a team of (one or more) mobile agents operating in a graph G. Unaware of the graph topology and starting from the same node, the team must explore the graph. This problem, known as...

Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots (2008)

Paola Flocchini, David Ilcinkas, Andrzej Pelc, Nicola Santoro

Abstract. We consider the problem of exploring an anonymous unoriented ring by a team of k identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This...

Self-Deployment Algorithms for Mobile Sensors on a Ring (2008)

Radial View: Observing Fuzzy Cellular Automata with a New Visualization Method ∗ (2008)

We consider the self-deployment problem in a ring for a network of identical sensors: starting from some initial random placement in the ring, the sensors in the network must move, in a purely...

Paola Flocchini, Vladimir Cezar

Fuzzy Cellular Automata (FCA) are special couple map lattices that generalize Boolean cellular automata by allowing continuous values for the cell states. The local transition rule of a FCA is the...

International Journal of Foundations of Computer Science c ○ World Scientific Publishing Company DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS (2008)

Paola Flocchini, Miao Jun Huang, Flaminia L. Luccio

Communicated by Editor’s name In this paper we consider a network where an intruder is moving “contaminating ” the nodes it passes by, and we focus on the problem of decontaminating such a...

Fault-Tolerant Simulation of Message-Passing Algorithms by Mobile Agents (2008)

Shantanu Das, Paola Flocchini, Nicola Santoro, Masafumi Yamashita, Submission To Sirocco

The recently established computational equivalence between the traditional message-passing model and the mobile-agents model is based on the existence of a mobile-agents algorithm that simulates the...

Efficient protocols for computing optimal swap edges (2008)

Paola Flocchini, Antonio Mesa Enriques, Linda Pagli, Nicola Santoro

Abstract We consider the problem of computing the optimal swap edges of a shortest-path tree. This theoretical problem arises in practice in systems that offer point-offailure shortest-path rerouting...

Radial View: Observing Fuzzy Cellular Automata with a New Visualization Method ∗ (2008)

Paola Flocchini, Vladimir Cezar

In this paper we consider a new way to visualize the evolution of Fuzzy Cellular Automata that reveals interesting dynamics not observable with the classical space-time diagram. We classify the...

Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots (2008)

Paola Flocchini, David Ilcinkas, Andrzej Pelc, Nicola Santoro

We consider the problem of exploring an anonymous unoriented ring by a team of identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This weak...

Can (2008)

Lali Barrière, Paola Flocchini, Pierre Fraigniaud, Nicola Santoro

we elect if we cannot compare?

Distributed Exploration of Anonymous Graphs by Multiple Agents ∗ (2008)

Shantanu Das, Paola Flocchini, Shay Kutten, Amiya Nayak, Nicola Santoro

We consider the problem of exploration and mapping of an unknown environment modelled as a graph, by multiple identical mobile agents that are dispersed among the nodes of the graph. The objective is...

Distributed Computation of All Node Replacements of a Minimum Spanning Tree (2008)

Paola Flocchini, T. Mesa Enriquez, Linda Pagli, Nicola Santoro

Abstract. In many network applications the computation takes place on the minimum-cost spanning tree (MST) of the network G; unfortunately, a single link or node failure disconnects the tree. The All...

ABSTRACT Capture of an Intruder by Mobile Agents (2008)

Lali Barrière, Paola Flocchini, Pierre Fraigniaud, Nicola Santoro

Consider a team of mobile software agents deployed to capture a (possibly hostile) intruder in a network. All agents, including the intruder move along the network links; the intruder could be...

Distributed Exploration of Unlabelled Graphs by Multiple Agents ∗ (2008)

Shantanu Das, Paola Flocchini, Shay Kutten, Amiya Nayak, Nicola Santoro

We consider a distributed version of the typical graph exploration problem where a mobile agent has to traverse the edges of an unlabelled (i.e., anonymous) graph and return to its starting point,...

Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens (2008)

Remembering without Memory: Tree Exploration by Asynchronous Oblivious Robots (2008)

We prove that, for the black hole search problem, the pure token model is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove...

Flocchini, Paola, Ilcinkas, David, Pelc, Andrzej, Santoro, Nicola

In the effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the...

Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens (2008)

Remembering without Memory: Tree Exploration by Asynchronous Oblivious Robots (2008)

We prove that, for the black hole search problem, the pure token model is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove...

Flocchini, Paola, Ilcinkas, David, Pelc, Andrzej, Santoro, Nicola

In the effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the...

Recherche optimale de trou noir avec cailloux (2008)

Recherche optimale de trou noir avec cailloux (2008)

Un trou noir est un noeud d'un réseau qui détruit tout agent (ou robot) y entrant sans laisser de trace détectable. L'emplacement du trou noir doit \^etre déterminé par une une équipe d'agents...

Sense of Direction: Definitions, Properties and Classes (2007)

Un trou noir est un noeud d'un réseau qui détruit tout agent (ou robot) y entrant sans laisser de trace détectable. L'emplacement du trou noir doit \^etre déterminé par une une équipe d'agents...

Distance Routing: a New Compact Routing Technique on Series Parallel Networks (2007)

An extensive body of evidence exists of the impact that specific edge labelings have on the communication complexity of distributed problems. It has been long suspected that these very different...

Paola Flocchini, Flaminia L. Luccio

We consider the problem of routing messages on networks modeled by Series Parallel Graphs (SPGs), and we introduce a new technique, called Distance Routing (DR). We first present an algorithm that...

Finding the Extrema of a Distributed Multiset (2007)

Paola Alimonti, Paola Flocchini, Nicola Santoro

We consider the problem of finding the extrema of a distributed multiset in a ring; that is, of determining the minimum and the maximum values, x min and x max , of a multiset X = fx 0 ; x 2 ; :::; x...

Leader Election and Sorting in Anonymous Asynchronous Rings 1 (2007)

Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Flaminia L. Luccio, Nicola Santoro

In an anonymous ring of n processors, all processors are totally indistinguishable except for their input values. These values are not necessarily distinct, i.e., they form a multiset, and this makes...

2 (2007)

Abstract. We address the problem of mobile agents searching a ring network for a highly harmful item, a black hole, a stationary process destroying visiting agents upon their arrival. No observable...

2 (2007)

Dynamic Monopolies in Tori (2007)

Abstract. In this paper we aim at an understanding of the fundamental algorithmic limitations on what a set of autonomous mobile robots can or cannot achieve. We study a hard task for a set of weak...

Paola Flocchini, Elena Lodi, Fabrizio Luccio, Linda Pagli, Nicola Santoro

Let G be a simple connected graph where every node is colored either black or white. Consider now the following repetitive process on G: each node recolors itself, at each local time step, with the...

Distributed Mobile Computing with Incomparable Labels (2007)

Lali Barrière, Paola Flocchini, Pierre Fraigniaud, Nicola Santoro

An obvious focus of mobile computing is the issue of computability in a distributed mobile environment, in particular determining what minimal hypotheses allow a given problem to be solved by a set...

Exploration d'arbres par des équipes de robots asynchrones et sans mémoire (2007)

Flocchini, Paola, Ilcinkas, David, Pelc, Andrzej, Santoro, Nicola

Une équipe d'entités mobiles (robots), identiques et sans mémoire, doit explorer un arbre anonyme en visitant tous ses noeuds. Les robots démarrent depuis des noeuds différents et arbitraires de...

Exploration d'arbres par des équipes de robots asynchrones et sans mémoire (2007)

Flocchini, Paola, Ilcinkas, David, Pelc, Andrzej, Santoro, Nicola

Une équipe d'entités mobiles (robots), identiques et sans mémoire, doit explorer un arbre anonyme en visitant tous ses noeuds. Les robots démarrent depuis des noeuds différents et arbitraires de...

Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots (2007)

Flocchini, Paola, Ilcinkas, David, Pelc, Andrzej, Santoro, Nicola

We consider the problem of exploring an anonymous unoriented ring by a team of $k$ identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This weak...

Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots (2007)

Flocchini, Paola, Ilcinkas, David, Pelc, Andrzej, Santoro, Nicola

We consider the problem of exploring an anonymous unoriented ring by a team of $k$ identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This weak...

Distributed security algorithms by mobile agents (2006)

Effective elections for anonymous mobile agents (2006)

Abstract. Mobile Agents have been extensively studied for several years

Shantanu Das, Paola Flocchini, Amiya Nayak, Nicola Santoro

Abstract. We present distributed protocols for electing a leader among k mobile agents that are dispersed among the n nodes of a graph. While previous solutions for the agent election problem were...

Mobile search for a black hole in an anonymous ring. Algorithmica (2006)

Stefan Dobrev, Paola Flocchini, Nicola Santoro, Mobile Agents, Black Hole

In this paper we address the problem of mobile agents searching for a highly harmful item (called black hole) in a ring network. The black hole is a stationary process that destroys visiting agents...

Point-of-Failure Shortest-Path Rerouting: Computing the Optimal Swap Edges Distributively (2006)

FLOCCHINI, Paola, ENRIQUES, Antonio Mesa, PAGLI, Linda, PRENCIPE, Giuseppe, SANTORO, Nicola

We consider the problem of computing the optimal swap edges of a shortest-path tree. This problem arises in designing systems that offer point-of-failure shortest-path rerouting service in presence...

Mobile search for a black hole in an anonymous ring. Algorithmica (2006)

Gathering of asynchronous robots with limited visibility (2005)

Abstract. W e address the problem of mobile agents searching a ring network for a highly harmful item, a black hole, a stationary process destroying visiting agents upon their arrival. No observable...

Rendezvous and election of mobile agents: impact of sense of direction (2005)

In this paper we study the problem of gathering in the same location of the plane a collection of identical oblivious mobile robots. Previous investigations have focused mostly on the unlimited...

Lali Barrière, Paola Flocchini, Pierre Fraigniaud, Nicola Santoro

Consider a collection of r identical asynchronous mobile agents dispersed on an arbitrary anonymous network of size n. The agents all execute the same protocol and move from node to neighbouring...

Cleaning an arbitrary regular network with mobile agents (2005)

Paola Flocchini, Amiya Nayak, Arno Schulz

Abstract. In this paper, we consider a contaminated network with an intruder. The task for the mobile agents is to decontaminate all hosts while preventing a recontamination and to do so as...

Improved bounds for optimal black hole search in a network with a map (2004)

Abstract. A black hole is a harmful host that destroys incoming agents without leaving any observable trace of such a destruction. The black hole search problem is to unambiguously determine the...

Sense of direction is a property of labeled graphs which has been shown to have a definite impact on computability and complexity in systems of communicating entities, and whose applicability ranges...

Sense of direction is a property of labeled graphs which has been shown to have a definite impact on computability and complexity in systems of communicating entities, and whose applicability ranges...

Sense of direction is a property of labeled graphs which has been shown to have a definite impact on computability and complexity in systems of communicating entities, and whose applicability ranges...

Mobile agent rendezvous in a ring (2003)

Sense of direction is a property of labeled graphs which has been shown to have a definite impact on computability and complexity in systems of communicating entities, and whose applicability ranges...

Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Nicola Santoro, Cindy Sawchuk

We study the rendezvous search problem for k 2 mobile agents in an n node ring. Rather than using randomized algorithms or dierent deterministic algorithms to break the symmetry that often arises in...

Solving the robots gathering problem (2003)

Mark Cieliebak, Paola Flocchini, Nicola Santoro

Abstract. Consider a set of n> 2 simple autonomous mobile robots (decentralized, asynchronous, no common coordinate system, no identities, no central coordination, no direct communication, no...

Multiple agents rendezvous in a ring in spite of a black hole (2003)

Can We Elect If We Cannot Compare? (2003)

The Rendezvous of anonymous mobile agents in a anonymous network is an intensively studied problem; it calls for k anonymous, mobile agents to gather in the same site. We study this problem when in...

Lali Barrière, Lali Barri Ere, Paola Flocchini, Pierre Fraigniaud, Nicola Santoro

The aim of this paper is to study the computational power of the qualitative model, where entities are given distinct labels which are however mutually incomparable; this model is opposed to the...

Multiple agents rendezvous in a ring in spite of a black hole (2003)

Solving the robots gathering problem (2003)

Abstract. The Rendezvous of anonymous mobile agents in a anonymous network is an intensively studied problem; it calls for k anonymous, mobile agents to gather in the same site. We study this problem...

Mark Cieliebak, Paola Flocchini, Nicola Santoro

Abstract. Consider a set of n> 2 simple autonomous mobile robots (decentralized, asynchronous, no common coordinate system, no identities, no central coordination, no direct communication, no...

Searching for a black hole in arbitrary networks (2002)

Searching for a black hole in arbitrary networks (2002)

Consider a networked environment, supporting mobile agents, where there is a black hole: a harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a...

Stefan Dobrev, Paola Flocchini

flocchin @ site. uottawa.ca Protecting agents from host attacks is a pressing security concern in networked environments supporting mobile agents. In this paper, we consider a black hole: a highly...

Electing a Leader Among Anonymous Mobile Agents in Anonymous Networks With Sense-of-Direction (2002)

Lali Barrière, Paola Flocchini, Pierre Fraigniaud, Nicola Santoro

We consider a collection of r anonymous asynchronous mobile agents dispersed on an arbitrary anonymous network of size n. Neither r nor n are known a priori by the agents. We examine the problem of...

Capture of an Intruder by Mobile Agents (2002)

Lali Barrière, Lali Barri Ere, Paola Flocchini, Pierre Fraigniaud, Nicola Santoro

Consider a team of mobile software agents deployed to capture a (possibly hostile) intruder in a network. All agents, including the intruder move along the network links; the intruder could be...

Pattern Formation by Autonomous Robots Without Chirality (2001)

Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Peter Widmayer

Consider a set of anonymous mobile robots, and the patterns they can collectively form in the plane. If each robot has a compass needle that indicates North but there is no agreement on East and West...

Gathering of Asynchronous Oblivious Robots with Limited Visibility (2001)

Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Peter Widmayer

We consider a collection of robots which are identical (anonymous) , have limited visibility of the environment, and no memory of the past (oblivious); furthermore, they are totally asynchronous in...

Backward Consistency and Sense of Direction in Advanced Distributed Systems (1999)

Paola Flocchini, Alessandro Roncato, Nicola Santoro

) Paola Flocchini Universit'e du Qu'ebec `a Hull (flocchini@uqah.uquebec.ca) Alessandro Roncato CDL Informatica - Universit`a di Venezia (roncato@dsi.unive.it) Nicola Santoro Carleton...

Sense of Direction in Distributed Computing (1998)

Sense of Direction in Distributed Computing (1998)

Sense of Direction is a property of labeled graphs which has been shown to have a definite impact on computability and complexity in systems of communicating entities, and whose applicability ranges...

Irreversible Dynamos in Tori (1998)

Introduction 1.1 Distributed Model There are numerous models for distributed systems, differing from one another on a large number of important factors and parameters. We shall restrict ourselves to...

Paola Flocchini, Elena Lodi, Fabrizio Luccio, Linda Pagli, Nicola Santoro

We study the dynamics of majority-based distributed systems in presence of permanent faults. In particular, we are interested in the patterns of initial faults which may lead the entire system to a...

On the Impact of Sense of Direction on Message Complexity (1997)

Minimal Sense of Direction in Regular Networks (1997)

In this paper, we prove a general result on the impact of sense of direction. We show that, in arbitrary graphs, any sense of direction has a dramatic effect on the communication complexity of...

Paola Flocchini

A network is said to have Sense of Direction when the port labeling satisfies a particular set of global consistency constraints. In this paper we study the link between the topology of a system and...

On the Impact of Sense of Direction on Communication Complexity (revised version) (1997)

Minimal Sense of Direction in Regular Networks (1997)

In this paper, we prove a general result on the impact of Sense of Direction. We show that, in arbitrary graphs, any Sense of Direction has a dramatic effect on the communication complexity of...

Paola Flocchini

A network is said to have Sense of Direction when the port labeling satisfies a particular set of global consistency constraints. In this paper we study the link between the topology of a system and...

CA-like error propagation in fuzzy CA (1997)

Paola Flocchini, Frédéric Geurts, Nicola Santoro

. We describe and analyze the surprising evolution of an overflow error which has occurred during the simulation of a class of continuous complex systems called "fuzzy cellular automata"....

On Systems with Sense of Direction (1996)

Paola Flocchini, Alessandro Roncato, Ro Roncato, Nicola Santoro

For a system with Sense of Direction, there are several possible consistent coding functions c and corresponding decoding functions d. Thus, it is desirable for a given system to identify, among all...

Computing on Anonymous Networks with Sense of Direction (1996)

Paola Flocchini, Alessandro Roncato, Nicola Santoro

Sense of direction refers to a set of global consistency constraints of the local labeling of the edges of a network. Sense of direction has a large impact on the communication complexity of many...

Optimal Elections in Labeled Hypercubes (1996)

Paola Flocchini

We study the message complexity of the Election Problem in Hypercube networks, when the processors have a "Sense of Direction", i.e., the capability to distinguish between adjacent...

Distance Routing on Series Parallel Networks (1996)

Paola Flocchini, Flaminia L. Luccio

In this paper we consider the problem of routing messages on Series Parallel Graphs (SPGs), and we introduce a new technique called Distance Routing. This technique is based on the idea of encoding...

Computing on Anonymous Networks with Sense of Direction (1996)

Paola Flocchini, Alessandro Roncato, Nicola Santoro

Sense of direction refers to a set of global consistency constraints of the local labeling of the edges of a network. Sense of direction has a large impact on the communication complexity of many...

Symmetries and Sense of Direction in Labeled Graphs (1996)

Paola Flocchini, Alessandro Roncato, Nicola Santoro

We consider distributed systems modeled by edge-labeled graphs. Properties of the labeling can be used in the design of efficient protocols; for example, sense of direction is known to have a strong...

Distance Routing on Series Parallel Networks (1996)

Paola Flocchini, Flaminia L. Luccio

In this paper we consider the problem of routing messages on Series Parallel Graphs (SPGs), and we introduce a new technique called Distance Routing. This technique is based on the idea of encoding...

Topological Constraints For Sense Of Direction (1995)

Sense of Direction: Definitions, Properties and Classes (1995)

In a distributed system, each entity has a label (port number) associated to each of its neighbors. It is well known that if the labeling satisfies a global consistency property called Sense of...