Exploration of Periodically Varying Graphs (2009)
Flocchini, Paola, Mans, Bernard, Santoro, Nicola
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...
Self-deployment Algorithms for Mobile Sensors on a Ring (2009)
Paola Flocchini, Nicola Santoro
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...
Distributed Computation of All Node Replacements of a Minimum Spanning Tree ⋆ (2009)
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...
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)
Paola Flocchini, Nicola Santoro, Peter Widmayer
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...
153 EFFICIENT PROTOCOLS FOR COMPUTING THE OPTIMAL SWAP EDGES OF A SHORTEST PATH TREE (2009)
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...
Stefan Dobrev, Paola Flocchini, Nicola Santoro
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...
Arbitrary Pattern Formation by Asynchronous, Anonymous, Oblivious Robots ∗ (2009)
Paola Flocchini, Nicola Santoro, Peter Widmayer
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....
Santoro, Nicola, Cirillo, Grazia, Xiang, Zhimin, Tanas, Rita, Greggio, Nella, Morino, Giuseppe, ...
Abstract Background Melanocortin-4-receptor (MC4R) mutations represent the most frequent genetic cause of non-syndromic early onset obesity. Children carrying MC4R mutations seem to show a particular...
SUMMARY 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...
Network Decontamination in Presence of Local Immunity (2008)
Fabrizio Luccio, Linda Pagli, Nicola Santoro
We consider the problem of decontaminating a network infected by a mobile virus. The goal is to perform the task using as small a team of antiviral agents as possible, avoiding recontamination of...
Scattered Black Hole Search in an Oriented Ring using Tokens (2008)
Stefan Dobrev, Nicola Santoro, Wei Shi
A black hole is a highly harmful host that disposes of visiting agents upon their arrival without any observable trace of the destruction. The problem of locating the black hole in a asynchronous...
Dynamic Monopolies in Tori \Lambda (2008)
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...
On the longest increasing subsequence of a circular list (2008)
Jörg-rüdiger Sack, Nicola Santoro
The longest increasing circular subsequence (LICS) of a list is considered. A Monte-Carlo algorithm to compute it is given which has worst case execution time O(n 3/2 log n) and storage requirement...
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)
Paola Flocchini, Nicola Santoro
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...
Beat Gfeller, Nicola Santoro, Peter Widmayer
Communication in networks suffers if a link fails. When the links are edges of a tree that has been chosen from an underlying graph of all possible links, a broken link even disconnects the network....
On Fractional Dynamic Faults with Threshold ⋆ (2008)
Abstract. Unlike localized communication failures that occur on a fixed (although a priori unknown) set of links, dynamic faults can occur on any link. Known also as mobile or ubiquitous faults,...
On the longest increasing subsequence of a circular list (2008)
Jörg-rüdiger Sack, Nicola Santoro
The longest increasing circular subsequence (LICS) of a list is considered. A Monte-Carlo algorithm to compute it is given which has worst case execution time O(n 3/2 log n) and storage requirement...
Distributed Algorithms for Autonomous Mobile Robots (2008)
Summary. The distributed coordination and control of a team of autonomous mobile robots is a problem widely studied in a variety of fields, such as engineering, artificial intelligence, artificial...
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...
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...
Lali Barrière, Paola Flocchini, Pierre Fraigniaud, Nicola Santoro
we elect if we cannot compare?
Distributed Computing on Oriented Anonymous Hypercubes with Faulty Components ∗ (2008)
Evangelos Kranakis, Nicola Santoro
We give efficient algorithms for distributed computation on anonymous, labeled, asynchronous oriented hypercubes with possible faulty components (i.e. processors and links) and deterministic...
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...
Amos Israeli, Danny Krizanc, Evangelos Kranakis, Nicola Santoro
A set of anonymous processors is interconnected forming a complete synchronous network with sense of direction. Weak unison is the problem where all processors want to enter the same state (in our...
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...
Fault Classification in P2P Semantic Mapping (2008)
Abdul-rahman Mawlood, Michael Weiss, Nicola Santoro
An alternative to global ontology use in the semantic interoperability among heterogeneous information sources is the reaching of a consensus among distributed ontologies using local mapping and...
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)
Flocchini, Paola, Ilcinkas, David, Santoro, Nicola
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...
Remembering without Memory: Tree Exploration by Asynchronous Oblivious Robots (2008)
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)
Flocchini, Paola, Ilcinkas, David, Santoro, Nicola
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...
Remembering without Memory: Tree Exploration by Asynchronous Oblivious Robots (2008)
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)
Flocchini, Paola, Ilcinkas, David, Santoro, Nicola
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...
Recherche optimale de trou noir avec cailloux (2008)
Flocchini, Paola, Ilcinkas, David, Santoro, Nicola
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)
Paola Flocchini, Bernard Mans, Nicola Santoro
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...
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...
Stefan Dobrev, Paola Flocchini, Nicola Santoro
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...
Paola Flocchini, Nicola Santoro, Peter Widmayer
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...
Evangelos Kranakis, Danny Krizanc, Nicola Santoro, Cindy Sawchuk
In the rendezvous search problem, two mobile agents must move along the n nodes of a network so as to minimize the time required to meet or rendezvous. When the mobile agents are identical and the...
Contiguous and Internal Graph Searching (2007)
Pierre Fraigniaud, Nicola Santoro, Dimitrios M. Thilikos
Graph searching refers to a problem that has been throughly and extensively investigated in the literature, and that describes a variety of application scenarios ranging from \decontaminating a set...
Dynamic Monopolies in Tori (2007)
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...
Evangelos Kranakis, Danny Krizanc, Nicola Santoro, Cindy Sawchuk
In the rendezvous search problem, two mobile agents must move along the n nodes of a network so as to minimize the time required to meet or rendezvous. When the mobile agents are identical and the...
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...
Rendezvous of mobile agents in unknown graphs with faulty links (2007)
Jérémie Chalopin, Shantanu Das, Nicola Santoro
A group of mobile agents wandering among the nodes of a network have to gather together in a single node of the graph; This problem known as the Rendezvous problem has been studied extensively but...
Xu Li, Nicola Santoro, Ivan Stojmenovic
Abstract. Sensor relocation protocols can be employed as fault tolerance approach to offset the coverage loss caused by node failures. We introduce a novel localized structure, information mesh, for...
Abstract — Sensor relocation protocols can be employed as a fault-tolerance approach to reduce or complement coverage loss caused by node failures. In this paper, we introduce a novel localized...
Distributed security algorithms by mobile agents (2006)
Paola Flocchini, Nicola Santoro
Abstract. Mobile Agents have been extensively studied for several years
An Integrated Self-Deployment and Coverage Maintenance Scheme for Mobile Sensor Networks (2006)
Abstract. In mobile sensor networks, the coverage improvement problem, i.e., maximizing and/or maintaining overall sensing coverage, is a fundamental research issue attracting many researchers....
Effective elections for anonymous mobile agents (2006)
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)
Stefan Dobrev, Paola Flocchini, Nicola Santoro
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...
Gathering of asynchronous robots with limited visibility (2005)
Paola Flocchini, Nicola Santoro, Peter Widmayer
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...
Rendezvous and election of mobile agents: impact of sense of direction (2005)
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...
Improved bounds for optimal black hole search in a network with a map (2004)
Stefan Dobrev, Paola Flocchini, Nicola Santoro
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 in distributed computing (2003)
Flocchini, Paola, Mans, Bernard, Santoro, Nicola
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 in distributed computing (2003)
Flocchini, Paola, Mans, Bernard, Santoro, Nicola
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 in distributed computing (2003)
Flocchini, Paola, Mans, Bernard, Santoro, Nicola
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 in distributed computing (2003)
Flocchini, Paola, Mans, Bernard, Santoro, Nicola
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)
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...
Multiple Mobile Agent Rendezvous in a Ring Paola Flocchini \Lambda (2003)
Evangelos Kranakis, Danny Krizanc, Nicola Santoro, Cindy Sawchuk
y
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)
Stefan Dobrev, Paola Flocchini, Nicola Santoro
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...
Can We Elect If We Cannot Compare? (2003)
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...
Connected and Internal Graph Searching (2003)
Lali Barriere, Pierre Fraigniaud, Nicola Santoro, Dimitrios M. Thilikos
This paper is concerned with the graph searching game. The search number s(G) of a graph G is the smallest number of searchers required to "clear" G. A search strategy is monotone (m) if no...
Multiple agents rendezvous in a ring in spite of a black hole (2003)
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...
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...
Searching for a black hole in arbitrary networks (2002)
Stefan Dobrev, Paola Flocchini, Nicola Santoro
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...
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...
On finding minimum deadly sets for directed networks (2001)
Given a set S of elements in a directed network that are initially faulty, an element becomes (functionally) faulty if all its in-neighbors or all its outneighbors are (functionally) faulty. A set S...
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...
Optimal Elections in Faulty Loop Networks and Applications (1998)
Loop networks (or Hamiltonian circulant graphs) are a popular class of faulttolerant network topologies which include rings and complete graphs. For this class, the fundamental problem of Leader...
Sense of Direction in Distributed Computing (1998)
Paola Flocchini, Bernard Mans, Nicola Santoro
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 in Distributed Computing (1998)
Paola Flocchini, Bernard Mans, Nicola Santoro
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...
Irreversible Dynamos in Tori (1998)
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)
Paola Flocchini, Bernard Mans, Nicola Santoro
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...
On the Impact of Sense of Direction on Communication Complexity (revised version) (1997)
Paola Flocchini, Bernard Mans, Nicola Santoro
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...
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"....
Efficient Token-Based Control in Rings ∗† (1997)
Esteban Feuerstein, Stefano Leonardi, Alberto Marchetti-spaccamela, Nicola Santoro
In this paper we deal with the efficiency of token-based strategies for the basic problem of controlling the allocation of a shared resource in a ring of n processing entities. We propose new...
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...
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...
Topological Constraints For Sense Of Direction (1995)
Paola Flocchini, Nicola Santoro
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...
Sense of Direction: Definitions, Properties and Classes (1995)
Paola Flocchini, Bernard Mans, Nicola Santoro
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...
Efficient reconfiguration technique for redundant ring networks (1995)
Amiya Nayak, Nicola Santoro, Quanhu Xue
Consider a redundant ring network where each node is also connected to the nodes at distance d. In the presence of faulty nodes, the goal of a reconfiguration scheme is to construct the largest...
Experiences with the implementation of geometric algorithms (1995)
Mehlhorn, Kurt, Akl, Selim G., Dehne, Frank, Sack, Jörg-Rüdiger, Santoro, Nicola
Trade-offs in non-reversing diameter (1994)
Hans L. Bodlaender, Nicola Santoro
Consider a tree T with a number of extra edges (the bridges) added. We consider the notion of diameter, that is obtained by admitting only paths p with the property that for every bridge b in path p,...
Finding the Extrema of a Distributed Multiset (1994)
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, xmin and xmax , of a multiset X = fx 0 ; x 2 ; :::;...
A Complete and Efficient Algorithm for the Intersection of a General and a Convex Polyhedron (1993)
Dobrindt, Katrin, Mehlhorn, Kurt, Yvinec, Mariette, Sack, Jörg-Rüdiger, Santoro, Nicola, ...
Distributed computing on anonymous hypercubes with Faulty Components (1992)
Evangelos Kranakis, Nicola Santoro
We give ecient algorithms for distributed computation on anonymous, labeled, asynchronous hypercubes with possible faulty components (i.e. processors and links) and deterministic procoessors....
Una-May O'Reilly, Nicola Santoro
. We establish worst-case and average-case lower bounds on the trade-off between the time and bit complexity for two-party communication in synchronous networks. We prove that the bounds are tight by...
A Time-Randomness Tradeoff for Communication Complexity (1991)
Fleischer, Rudolf, Jung, Hermann, Mehlhorn, Kurt, Van Leeuwen, Jan, Santoro, Nicola
Symmetries and Sense of Direction in Labeled Graphs
Paola Flocchini, Alessandro Roncato, Nicola Santoro
We consider edge-labeled graphs which model distributed systems, focus on properties of edge-labelings, and study their impact on graph classes. In particular, we investigate the relation between...