39 results on '"Blin, Lélia"'
Search Results
2. Compact self-stabilizing leader election for general networks
- Author
-
Blin, Lélia and Tixeuil, Sébastien
- Published
- 2020
- Full Text
- View/download PDF
3. A self-stabilizing memory efficient algorithm for the minimum diameter spanning tree under an omnipotent daemon
- Author
-
Blin, Lélia, Boubekeur, Fadwa, and Dubois, Swan
- Published
- 2018
- Full Text
- View/download PDF
4. Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative
- Author
-
Blin, Lélia and Tixeuil, Sébastien
- Published
- 2018
- Full Text
- View/download PDF
5. Exclusive Graph Searching
- Author
-
Blin, Lélia, Burman, Janna, and Nisse, Nicolas
- Published
- 2017
- Full Text
- View/download PDF
6. Compact Deterministic Self-stabilizing Leader Election : The Exponential Advantage of Being Talkative
- Author
-
Blin, Lélia, Tixeuil, Sébastien, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Afek, Yehuda, editor
- Published
- 2013
- Full Text
- View/download PDF
7. Fast Self-stabilizing Minimum Spanning Tree Construction : Using Compact Nearest Common Ancestor Labeling Scheme
- Author
-
Blin, Lélia, Dolev, Shlomi, Potop-Butucaru, Maria Gradinariu, Rovedakis, Stephane, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Lynch, Nancy A., editor, and Shvartsman, Alexander A., editor
- Published
- 2010
- Full Text
- View/download PDF
8. A super-stabilizing [formula omitted]-approximation algorithm for dynamic Steiner trees
- Author
-
Blin, Lélia, Potop-Butucaru, Maria, and Rovedakis, Stephane
- Published
- 2013
- Full Text
- View/download PDF
9. Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms.
- Author
-
Blin, Lélia, Feuilloley, Laurent, and Le Bouder, Gabriel
- Subjects
- *
ELECTIONS , *SELF-stabilization (Computer science) , *COMPUTER algorithms , *COMPUTER networks , *BOOLEAN functions - Abstract
Given a boolean predicate Π on labeled networks (e.g., proper coloring, leader election, etc.), a self-stabilizing algorithm for Π is a distributed algorithm that can start from any initial configuration of the network (i.e., every node has an arbitrary value assigned to each of its variables), and eventually converge to a configuration satisfying Π. It is known that leader election does not have a deterministic self-stabilizing algorithm using a constant-size register at each node, i.e., for some networks, some of their nodes must have registers whose sizes grow with the size n of the networks. On the other hand, it is also known that leader election can be solved by a deterministic self-stabilizing algorithm using registers of O(log log n) bits per node in any n-node bounded-degree network. We show that this latter space complexity is optimal. Specifically, we prove that every deterministic self-stabilizing algorithm solving leader election must use (log log n)-bit per node registers in some n-node networks. In addition, we show that our lower bounds go beyond leader election, and apply to all problems that cannot be solved by anonymous algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2023
10. Self-stabilizing minimum degree spanning tree within one from the optimal degree
- Author
-
Blin, Lélia, Potop-Butucaru, Maria Gradinariu, and Rovedakis, Stephane
- Published
- 2011
- Full Text
- View/download PDF
11. Resource Efficient Stabilization for Local Tasks despite Unknown Capacity Links
- Author
-
Blin, Lélia, Durand, Anaïs, Tixeuil, Sébastien, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Université d'Évry-Val-d'Essonne (UEVE), Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Laboratory of Information, Network and Communication Sciences (LINCS), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU)
- Subjects
and phrases Self-stabilizing algorithm ,message passing ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,unbounded capacity commu- nication ,nodes coloring ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] - Abstract
Self-stabilizing protocols enable distributed systems to recover correct behavior starting from any arbitrary configuration. In particular, when processors communicate by message passing, fake messages may be placed in communication links by an adversary. When the number of such fake messages is unknown, self-stabilization may require huge resources: generic solutions (a.k.a. data link protocols) require unbounded resources, which makes them unrealistic to deploy, specific solutions (e.g., census or tree construction) require O(n log n) or O(∆ log n) bits of memory per node, where n denotes the network size and ∆ its maximum degree, which may prevent scalability. We investigate the possibility of resource efficient self-stabilizing protocols in this context. Specifically, we present a self-stabilizing protocol for (∆+1)-coloring in any n-node graph, under the asynchronous message-passing model. The problem of (∆+1)-coloring is considered a benchmarking problem for local tasks. Our protocol offers many desirable features. It is deterministic, it converges in O(k∆n^2 log n) message exchanges, where k is the bound of the link capacity in terms of number of messages, and it uses messages on O(log log n+log ∆) bits with a memory of O(∆ log ∆+log log n) bits at each node. The resource consumption of our protocol is thus almost oblivious to the number of nodes, enabling scalability. Moreover, a striking property of our protocol is that the nodes do not need to know the number, or any bound on the number of messages initially present in each communication link of the initial (potentially corrupted) network configuration. This permits our protocol to handle any future network with unknown message capacity communication links. A key building block of our coloring scheme is a spanning directed acyclic graph construction, that is of independent interest, and can serve as a useful tool for solving other tasks in this challenging setting.
- Published
- 2020
12. Distributed chasing of network intruders
- Author
-
Blin, Lélia, Fraigniaud, Pierre, Nisse, Nicolas, and Vial, Sandrine
- Published
- 2008
- Full Text
- View/download PDF
13. Brief Announcement: Memory Lower Bounds for Self-Stabilization
- Author
-
Blin, Lélia, Feuilloley, Laurent, and Le Bouder, Gabriel
- Subjects
000 Computer science, knowledge, general works ,Computer Science - Abstract
In the context of self-stabilization, a silent algorithm guarantees that the communication registers (a.k.a register) of every node do not change once the algorithm has stabilized. At the end of the 90's, Dolev et al. [Acta Inf. '99] showed that, for finding the centers of a graph, for electing a leader, or for constructing a spanning tree, every silent deterministic algorithm must use a memory of Omega(log n) bits per register in n-node networks. Similarly, Korman et al. [Dist. Comp. '07] proved, using the notion of proof-labeling-scheme, that, for constructing a minimum-weight spanning tree (MST), every silent algorithm must use a memory of Omega(log^2n) bits per register. It follows that requiring the algorithm to be silent has a cost in terms of memory space, while, in the context of self-stabilization, where every node constantly checks the states of its neighbors, the silence property can be of limited practical interest. In fact, it is known that relaxing this requirement results in algorithms with smaller space-complexity. In this paper, we are aiming at measuring how much gain in terms of memory can be expected by using arbitrary deterministic self-stabilizing algorithms, not necessarily silent. To our knowledge, the only known lower bound on the memory requirement for deterministic general algorithms, also established at the end of the 90's, is due to Beauquier et al. [PODC '99] who proved that registers of constant size are not sufficient for leader election algorithms. We improve this result by establishing the lower bound Omega(log log n) bits per register for deterministic self-stabilizing algorithms solving (Delta+1)-coloring, leader election or constructing a spanning tree in networks of maximum degree Delta.
- Published
- 2019
- Full Text
- View/download PDF
14. Compact Self-Stabilizing Leader Election for Arbitrary Networks
- Author
-
Blin, Lélia and Tixeuil, Sébastien
- Subjects
Computer Science - Distributed, Parallel, and Cluster Computing ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY - Abstract
We present a self-stabilizing leader election algorithm for arbitrary networks, with space-complexity $O(\max\{\log \Delta, \log \log n\})$ bits per node in $n$-node networks with maximum degree~$\Delta$. This space complexity is sub-logarithmic in $n$ as long as $\Delta = n^{o(1)}$. The best space-complexity known so far for arbitrary networks was $O(\log n)$ bits per node, and algorithms with sub-logarithmic space-complexities were known for the ring only. To our knowledge, our algorithm is the first algorithm for self-stabilizing leader election to break the $\Omega(\log n)$ bound for silent algorithms in arbitrary networks. Breaking this bound was obtained via the design of a (non-silent) self-stabilizing algorithm using sophisticated tools such as solving the distance-2 coloring problem in a silent self-stabilizing manner, with space-complexity $O(\max\{\log \Delta, \log \log n\})$ bits per node. Solving this latter coloring problem allows us to implement a sub-logarithmic encoding of spanning trees --- storing the IDs of the neighbors requires $\Omega(\log n)$ bits per node, while we encode spanning trees using $O(\max\{\log \Delta, \log \log n\})$ bits per node. Moreover, we show how to construct such compactly encoded spanning trees without relying on variables encoding distances or number of nodes, as these two types of variables would also require $\Omega(\log n)$ bits per node.
- Published
- 2017
15. Brief announcement: Compact Self-Stabilizing Leader Election for General Networks
- Author
-
Blin, Lélia, Tixeuil, Sébastien, Tixeuil, Sébastien, Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps - - ESTATE2016 - ANR-16-CE25-0009 - AAPG2016 - VALID, Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Université d'Évry-Val-d'Essonne (UEVE), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Laboratory of Information, Network and Communication Sciences (LINCS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT), and ANR-16-CE25-0009,ESTATE,Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps(2016)
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS/C.2.4: Distributed Systems ,ACM: D.: Software/D.4: OPERATING SYSTEMS/D.4.8: Performance ,[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,ACM: D.: Software/D.4: OPERATING SYSTEMS/D.4.6: Security and Protection ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,ACM: D.: Software/D.4: OPERATING SYSTEMS/D.4.5: Reliability ,ACM: D.: Software/D.4: OPERATING SYSTEMS/D.4.4: Communications Management ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC] ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] - Abstract
International audience; We present a self-stabilizing leader election algorithm for general networks, with space-complexity $O(\max\{\log \Delta, \log \log n\})$ bits per node in $n$-node networks with maximum degree~$\Delta$. This space complexity is sub-logarithmic in $n$ as long as $\Delta = n^{o(1)}$. The best space-complexity known so far for general networks was $O(\log n)$ bits per node, and algorithms with sub-logarithmic space-complexities were known for the ring only. To our knowledge, our algorithm is the first algorithm for self-stabilizing leader election to break the $\Omega(\log n)$ bound for silent algorithms in general networks. Breaking this bound was obtained via the design of a (non-silent) self-stabilizing algorithm using sophisticated tools such as solving the distance-2 coloring problem in a silent self-stabilizing manner, with space-complexity $O(\max\{\log \Delta, \log \log n\})$ bits per node. Solving this latter coloring problem allows us to implement a sub-logarithmic encoding of spanning trees --- storing the IDs of the neighbors requires $\Omega(\log n)$ bits per node, while we encode spanning trees using $O(\max\{\log \Delta, \log \log n\})$ bits per node. Moreover, we show how to construct such compactly encoded spanning trees without relying on variables encoding distances or number of nodes, as these two types of variables would also require $\Omega(\log n)$ bits per node.
- Published
- 2017
16. Brief Announcement: Compact Self-Stabilizing Leader Election in Arbitrary Graphs
- Author
-
Blin, Lélia and Tixeuil, Sébastien
- Subjects
000 Computer science, knowledge, general works ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Computer Science ,Data_FILES ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
We present the first self-stabilizing algorithm for leader election in arbitrary topologies whose space complexity is O(max{log Delta, log log n}) bits per node, where n is the network size and Delta its degree. This complexity is sub-logarithmic in n when Delta = n^o(1).
- Published
- 2017
- Full Text
- View/download PDF
17. Self-stabilizing algorithms for spanning tree construction and for the management of mobile entities
- Author
-
Blin, Lélia, Blin, Lélia, Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Université Pierre et Marie Curie - Paris VI, and Franck Petit
- Subjects
spanning tree ,Algorithmique distribuée ,Distributed algorithm ,Computer Science - Distributed, Parallel, and Cluster Computing ,auto-stabilisation ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,robots ,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,self-stablilization ,arbres couvrants - Abstract
In the context of large-scale networks, the consideration of faults is an evident necessity. This document is focussing on the self-stabilizing approach which aims at conceiving algorithms ''repairing themselves'' in case of transient faults, that is of faults implying an arbitrary modification of the states of the processes. The document focuses on two different contexts, covering the major part of my research work these last years. The first part of the document is dedicated to the design and analysis of self-stabilizing algorithms for networks of processes. The second part of the document is dedicated to the design and analysis of self-stabilizing algorithms for autonomous entities (i.e., software agents, robots, etc.) moving in a network., Dans le contexte des réseaux à grande échelle, la prise en compte des pannes est une nécessité évidente. Ce document s'intéresse à l'approche auto-stabilisante qui vise à concevoir des algorithmes se ''réparant d'eux-même ' en cas de fautes transitoires, c'est-à-dire de pannes impliquant la modification arbitraire de l'état des processus. Il se focalise sur deux contextes différents, couvrant la majeure partie de mes travaux de recherche ces dernières années. La première partie du document est consacrée à l'algorithmique auto-stabilisante pour les réseaux de processus. La seconde partie du document est consacrée quant à elle à l'algorithmique auto-stabilisante pour des entités autonomes (agents logiciels, robots, etc.) se déplaçant dans un réseau.
- Published
- 2013
18. On asynchronous rendezvous in general graphs.
- Author
-
Bampas, Evangelos, Blin, Lélia, Czyzowicz, Jurek, Ilcinkas, David, Labourel, Arnaud, Potop-Butucaru, Maria, and Tixeuil, Sébastien
- Subjects
- *
GRAPH theory , *ASYNCHRONOUS learning , *POLYNOMIAL time algorithms , *COMPUTER algorithms , *MOBILE agent systems - Abstract
Abstract A pair of agents (robots) are moving in a graph with the goal of meeting at the same node or while traversing the same edge. An asynchronous adversary knows the prescribed walks of the two agents and is in complete control of the speed of each agent during its walk. We provide a complete characterization of pairs of walks that enforce rendezvous against an asynchronous adversary after traversing a given number of edges. The characterization is efficient in that it can be checked in polynomial time. We argue that the certificate of rendezvous enforcement that is produced by the checking algorithm contains a wealth of information on why rendezvous is enforced. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
19. A Very Fast (Linear Time) Distributed Algorithm, on General Graphs, for the Minimum-Weight Spanning Tree
- Author
-
Blin, Lélia, Butelle, Franck, Université d'Évry-Val-d'Essonne (UEVE), Laboratoire d'Informatique de Paris-Nord (LIPN), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Blin, Lélia, and Butelle, Franck
- Subjects
Systèmes distribués et parallèles ,Graphes ,combinatoire ,Informatique théorique ,[SCCO.COMP] Cognitive science/Computer science ,Optimisation ,[INFO]Computer Science [cs] ,[INFO] Computer Science [cs] ,ComputingMilieux_MISCELLANEOUS - Abstract
This paper develops linear time distributed algorithm, on general graphs, for the minimum spanning tree, in asynchronous communication network. We concentrated our efforts on the improvement of the execution time this is why our algorithm is faster than all previous linear algorithms. Our algorithm propose a solution for computing the MST in time $n/2$ with $O(n^2)$ messages (where $n=|V|$ for a graph $G=(V,E)$). The total number of messages in the worst case is slightly higher than the others algorithms, but in practice is often better.
- Published
- 2010
20. Polynomial-Time Space-Optimal Silent Self-Stabilizing Minimum-Degree Spanning Tree Construction
- Author
-
Blin, Lélia and Fraigniaud, Pierre
- Subjects
Computer Science - Distributed, Parallel, and Cluster Computing ,Computer Science - Data Structures and Algorithms - Abstract
Motivated by applications to sensor networks, as well as to many other areas, this paper studies the construction of minimum-degree spanning trees. We consider the classical node-register state model, with a weakly fair scheduler, and we present a space-optimal \emph{silent} self-stabilizing construction of minimum-degree spanning trees in this model. Computing a spanning tree with minimum degree is NP-hard. Therefore, we actually focus on constructing a spanning tree whose degree is within one from the optimal. Our algorithm uses registers on $O(\log n)$ bits, converges in a polynomial number of rounds, and performs polynomial-time computation at each node. Specifically, the algorithm constructs and stabilizes on a special class of spanning trees, with degree at most $OPT+1$. Indeed, we prove that, unless NP $=$ coNP, there are no proof-labeling schemes involving polynomial-time computation at each node for the whole family of spanning trees with degree at most $OPT+1$. Up to our knowledge, this is the first example of the design of a compact silent self-stabilizing algorithm constructing, and stabilizing on a subset of optimal solutions to a natural problem for which there are no time-efficient proof-labeling schemes. On our way to design our algorithm, we establish a set of independent results that may have interest on their own. In particular, we describe a new space-optimal silent self-stabilizing spanning tree construction, stabilizing on \emph{any} spanning tree, in $O(n)$ rounds, and using just \emph{one} additional bit compared to the size of the labels used to certify trees. We also design a silent loop-free self-stabilizing algorithm for transforming a tree into another tree. Last but not least, we provide a silent self-stabilizing algorithm for computing and certifying the labels of a NCA-labeling scheme.
- Published
- 2014
21. Compact Deterministic Self-Stabilizing Leader Election: The Exponential Advantage of Being Talkative
- Author
-
Blin, Lélia, Tixeuil, Sébastien, Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Laboratory of Information, Network and Communication Sciences (LINCS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT), and ANR-11-INFR-0016,IRIS,R eseaux Tout IP pour le Futur Internet d'Objets In- telligents(2011)
- Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] ,[INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing ,[INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF] ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Computer Science - Distributed, Parallel, and Cluster Computing ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] - Abstract
International audience; This paper focuses on compact deterministic self-stabilizing solutions for the leader election problem. When the protocol is required to be silent (i.e., when communication content remains fixed from some point in time during any execution), there exists a lower bound of Ω(logn) bits of memory per node participating to the leader election (where n denotes the number of nodes in the system). This lower bound holds even in rings. We present a new deterministic (non-silent) self-stabilizing protocol for n-node rings that uses only O(loglogn) memory bits per node, and stabilizes in O(nlog^2 n) time. Our protocol has several attractive features that make it suitable for practical purposes. First, the communication model matches the one that is expected by existing compilers for real networks. Second, the size of the ring (or any upper bound for this size) needs not to be known by any node. Third, the node identifiers can be of various sizes. Finally, no synchrony assumption besides a weak fair scheduler is assumed. Therefore, our result shows that, perhaps surprisingly, trading silence for exponential improvement in term of memory space does not come at a high cost regarding stabilization time, neither it does regarding minimal assumptions about the framework for our algorithm.
- Published
- 2014
22. Fast Self-Stabilizing Minimum Spanning Tree Construction Using Compact Nearest Common Ancestor Labeling Scheme
- Author
-
Blin, Lélia, Dolev, Shlomi, Gradinariu Potop-Butucaru, Maria, Rovedakis, Stephane, Université d'Évry-Val-d'Essonne (UEVE), Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Beer-Sheva], Ben-Gurion University of the Negev (BGU), CEDRIC. Réseaux et Objets Connectés (CEDRIC - ROC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), LIP6 UMR 7606, INRIA, UPMC Sorbonne Universités, France, Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), and HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)
- Subjects
Self-stabilizing algorithm ,Space complexity ,Minimum spanning trees ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Convergence time ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Labeling scheme ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
We present a novel self-stabilizing algorithm for minimum spanning tree (MST) construction. The space complexity of our solution is $O(\log^2n)$ bits and it converges in $O(n^2)$ rounds. Thus, this algorithm improves the convergence time of previously known self-stabilizing asynchronous MST algorithms by a multiplicative factor $\Theta(n)$, to the price of increasing the best known space complexity by a factor $O(\log n)$. The main ingredient used in our algorithm is the design, for the first time in self-stabilizing settings, of a labeling scheme for computing the nearest common ancestor with only $O(\log^2n)$ bits.
- Published
- 2013
23. Perpetual Graph Searching
- Author
-
Blin, Lélia, Burman, Janna, Nisse, Nicolas, Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Université d'Évry-Val-d'Essonne (UEVE), Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Partially supported by FP7 STREP EULER (N.N.), INRIA, ANR-18-CE23-0013,AGAPE,Un langage d'enchères pour des joueurs génériques d'enchères(2018), Université Nice Sophia Antipolis (... - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS)
- Subjects
Computer Science::Multiagent Systems ,self-stabilization ,graph searching ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,CORDA model ,Distributed computing ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
In graph searching, a team of mobile agents aims at clearing the edges of a contaminated graph. To clear an edge, an agent has to slide along it, however, an edge can be recontaminated if there is a path without agents from a contaminated edge to a clear edge. To goal of graph searching is to clear the graph, i.e., all edges are clear simultaneously, using the fewest number of agents. We study this problem in the minimal CORDA model of distributed computation. This model has very weak hypothesis: network nodes and agents are anonymous, have no memory of the past, and agents have no common sense of orientation. Moreover, all agents execute the same algorithm in the Look-Compute-Move manner and in an asynchronous environment. One interest of this model is that, if the clearing can be done by the agents starting from arbitrary positions (e.g., after faults or recontamination), the lack of memory implies that the clearing is done perpetually and then provides a first approach of fault-tolerant graph searching. Constraints due to the minimal CORDA model lead us to define a new variant of graph searching, called graph searching without collisions, where more than one agent cannot occupy the same node. We show that, in a centralized setting, this variant does not have the same behavior as classical graph searching. For instance, it not monotonous nor close by subgraph. We show that, in a graph with maximum degree $\Delta$, the smallest number of agents required to clear a graph without collisions is at most $\Delta$ times the number of searchers required when collisions are allowed. Moreover, this bound is tight up to a constant ratio. Then, we fully characterize graph searching without collisions in trees. In a distributed setting, i.e., in the minimal CORDA model, the question we ask is the following. Given a graph $G$, does there exist an algorithm that clears $G$, whatever be the initial positions of the agents on distinct vertices. In the case of a path network, we show that it is not possible is the number of agents is even in a path of odd order, or if there are at most two agents in a path with at least three vertices. We present an algorithm that clears all paths in all remaining cases. Finally, we propose an algorithm that clears any tree using a sufficient number of agents.
- Published
- 2012
24. Construction auto-stabilisante d'un arbre couvrant de poids minimum
- Author
-
Blin, Lélia, Dolev, Shlomi, Potop-Butucaru, Maria, Rovedakis, Stephane, Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science [Beer-Sheva], Ben-Gurion University of the Negev (BGU), Large-Scale Distributed Systems and Applications (Regal), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), CEDRIC. Réseaux et Objets Connectés (CEDRIC - ROC), Centre d'études et de recherche en informatique et communications (CEDRIC), Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), Ducourthial, Bertrand, Felber, Pascal, Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-Ecole Nationale Supérieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)-Conservatoire National des Arts et Métiers [CNAM] (CNAM), HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM)-HESAM Université - Communauté d'universités et d'établissements Hautes écoles Sorbonne Arts et métiers université (HESAM), and Rovedakis, Stephane
- Subjects
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,[INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Construction d'arbre couvrant de poids minimum ,[INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Auto-stabilisation ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Algorithme distribué - Abstract
International audience; L'arbre couvrant de poids minimum offre une solution de routage ayant le double avantage de donner une structure de communication simple et économique. Dans ce papier, nous présentons un nouvel algorithme auto-stabilisant pour la construction d'un arbre couvrant de poids minimum dans un système distribué et asynchrone. Notre solution améliore l'existant en permettant d'atteindre un meilleur compromis entre le temps de convergence, $O(n^2)$, et la complexité en mémoire nécessaire sur chaque noeud du réseau, $O(\log^2 n)$. Le temps de convergence est amélioré d'un facteur multiplicatif $\Theta(n)$ au prix d'un facteur multiplicatif de $O(\log n)$ sur la mémoire. La clé de voûte de ce travail est l'utilisation d'une méthode de nommage auto-stabilisante permettant d'identifier pour toute paire de noeuds le plus proche ancêtre commun dans l'arbre.
- Published
- 2011
25. Universal Loop-Free Super-Stabilization
- Author
-
Blin, Lélia, Rovedakis, Stephane, Potop-Butucaru, Maria, Tixeuil, Sébastien, Informatique, Biologie Intégrative et Systèmes Complexes (IBISC), Université d'Évry-Val-d'Essonne (UEVE), Networks and Performance Analysis (NPA), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Large-Scale Distributed Systems and Applications (Regal), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
- Subjects
Networking and Internet Architecture (cs.NI) ,FOS: Computer and information sciences ,Computer Science - Networking and Internet Architecture ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,Computer Science - Distributed, Parallel, and Cluster Computing ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,Computer Science - Data Structures and Algorithms ,Data Structures and Algorithms (cs.DS) ,Distributed, Parallel, and Cluster Computing (cs.DC) ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] - Abstract
We propose an univesal scheme to design loop-free and super-stabilizing protocols for constructing spanning trees optimizing any tree metrics (not only those that are isomorphic to a shortest path tree). Our scheme combines a novel super-stabilizing loop-free BFS with an existing self-stabilizing spanning tree that optimizes a given metric. The composition result preserves the best properties of both worlds: super-stabilization, loop-freedom, and optimization of the original metric without any stabilization time penalty. As case study we apply our composition mechanism to two well known metric-dependent spanning trees: the maximum-flow tree and the minimum degree spanning tree.
- Published
- 2010
26. A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-Free Property.
- Author
-
BLIN, LÉLIA, POTOP-BUTUCARU, MARIA, ROVEDAKIS, STÉPHANE, and TIXEUIL, SÉBASTIEN
- Subjects
- *
SELF-stabilization (Computer science) , *SPANNING trees , *DISTRIBUTED computing , *DISTRIBUTED algorithms , *DATA recovery - Abstract
The minimum spanning tree (MST) construction is a classical problem in Distributed Computing for creating a globally minimized structure distributedly. Self-stabilization is versatile technique for forward recovery that permits to handle any kind of transient faults in a unified manner. The loop-free property provides interesting safety assurance in dynamic networks where edge-cost changes during operation of the protocol.We present a new self-stabilizing MST protocol that improves on previous known approaches in several ways. First, it makes fewer system hypotheses as the size of the network (or an upper bound on the size) need not be known to the participants. Secondly, it is loop-free in the sense that it guarantees that a spanning tree structure is always preserved while edge costs change dynamically and the protocol adjusts to a new MST. Finally, time complexity matches the best known results, while space complexity results show that this protocol is the most efficient to date. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
27. On Proof-Labeling Schemes versus Silent Self-stabilizing Algorithms.
- Author
-
Blin, Lélia, Fraigniaud, Pierre, and Patt-Shamir, Boaz
- Published
- 2014
- Full Text
- View/download PDF
28. Exclusive Graph Searching.
- Author
-
Blin, Lélia, Burman, Janna, and Nisse, Nicolas
- Published
- 2013
- Full Text
- View/download PDF
29. Loop-Free Super-Stabilizing Spanning Tree Construction.
- Author
-
Blin, Lélia, Potop-Butucaru, Maria Gradinariu, Rovedakis, Stephane, and Tixeuil, Sébastien
- Abstract
We propose an univesal scheme to design loop-free and super-stabilizing protocols for constructing spanning trees optimizing any tree metrics (not only those that are isomorphic to a shortest path tree). Our scheme combines a novel super-stabilizing loop-free BFS with an existing self-stabilizing spanning tree that optimizes a given metric. The composition result preserves the best properties of both worlds: super-stabilization, loop-freedom, and optimization of the original metric without any stabilization time penalty. As case study we apply our composition mechanism to two well known metric-dependent spanning trees: the maximum-flow tree and the minimum degree spanning tree. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
30. Exclusive Perpetual Ring Exploration without Chirality.
- Author
-
Blin, Lélia, Milani, Alessia, Potop-Butucaru, Maria, and Tixeuil, Sébastien
- Abstract
In this paper, we study the exclusive perpetual exploration problem with mobile anonymous and oblivious robots in a discrete space. Our results hold for the most generic settings: robots are asynchronous and are not given any sense of direction, so the left and right sense (i.e. chirality) is decided by the adversary that schedules robots for execution, and may change between invocations of a particular robots (as robots are oblivious). We investigate both the minimal and the maximal number of robots that are necessary and sufficient to solve the exclusive perpetual exploration problem. On the minimal side, we prove that three deterministic robots are necessary and sufficient, provided that the size n of the ring is at least 10, and show that no protocol with three robots can exclusively perpetually explore a ring of size less than 10. On the maximal side, we prove that k = n − 5 robots are necessary and sufficient to exclusively perpetually explore a ring of size n when n is co-prime with k. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
31. A Superstabilizing log(n)-Approximation Algorithm for Dynamic Steiner Trees.
- Author
-
Blin, Lélia, Potop-Butucaru, Maria Gradinariu, and Rovedakis, Stephane
- Abstract
This paper proposes a fully dynamic self-stabilizing algorithm for the Steiner tree problem. The Steiner tree problem aims at constructing a Minimum Spanning Tree (MST) over a subset of nodes called Steiner members, or Steiner group usually denoted S. Steiner trees are good candidates to efficiently implement communication primitives such as publish/subscribe or multicast, essential building blocks in the design of middleware architectures for the new emergent networks (e.g. P2P, sensor or adhoc networks). Our algorithm returns a log|S|-approximation of the optimal Steiner tree. It improves over existing solutions in several ways. First, it is fully dynamic, in other words it withstands the dynamism when both the group members and ordinary nodes can join or leave the network. Next, our algorithm is self-stabilizing, that is, it copes with nodes memory corruption. Last but not least, our algorithm is superstabilizing. That is, while converging to a correct configuration (i.e., a Steiner tree) after a modification of the network, it keeps offering the Steiner tree service during the stabilization time to all members that have not been affected by this modification. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
32. A New Self-stabilizing Minimum Spanning Tree Construction with Loop-Free Property.
- Author
-
Blin, Lélia, Potop-Butucaru, Maria, Rovedakis, Stephane, and Tixeuil, Sébastien
- Abstract
The minimum spanning tree (MST) construction is a classical problem in Distributed Computing for creating a globally minimized structure distributedly. Self-stabilization is versatile technique for forward recovery that permits to handle any kind of transient faults in a unified manner. The loop-free property provides interesting safety assurance in dynamic networks where edge-cost changes during operation of the protocol. We present a new self-stabilizing MST protocol that improves on previous known approaches in several ways. First, it makes fewer system hypotheses as the size of the network (or an upper bound on the size) need not be known to the participants. Second, it is loop-free in the sense that it guarantees that a spanning tree structure is always preserved while edge costs change dynamically and the protocol adjusts to a new MST. Finally, time complexity matches the best known results, while space complexity results show that this protocol is the most efficient to date. [ABSTRACT FROM AUTHOR]
- Published
- 2009
- Full Text
- View/download PDF
33. On the Self-stabilization of Mobile Robots in Graphs.
- Author
-
Blin, Lélia, Gradinariu Potop-Butucaru, Maria, and Tixeuil, Sébastien
- Abstract
Self-stabilization is a versatile technique to withstand any transient fault in a distributed system. Mobile robots (or agents) are one of the emerging trends in distributed computing as they mimic autonomous biologic entities. The contribution of this paper is threefold. First, we present a new model for studying mobile entities in networks subject to transient faults. Our model differs from the classical robot model because robots have constraints about the paths they are allowed to follow, and from the classical agent model because the number of agents remains fixed throughout the execution of the protocol. Second, in this model, we study the possibility of designing self-stabilizing algorithms when those algorithms are run by mobile robots (or agents) evolving on a graph. We concentrate on the core building blocks of robot and agents problems: naming and leader election. Not surprisingly, when no constraints are given on the network graph topology and local execution model, both problems are impossible to solve. Finally, using minimal hypothesis with respect to impossibility results, we provide deterministic and probabilistic solutions to both problems, and show equivalence of these problems by an algorithmic reduction mechanism. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
34. Distributed Chasing of Network Intruders.
- Author
-
Flocchini, Paola, Gąsieniec, Leszek, Blin, Lélia, Fraigniaud, Pierre, Nisse, Nicolas, and Vial, Sandrine
- Abstract
This paper addresses the graph searching problem in a distributed setting. We describe a distributed protocol that enables searchers with logarithmic size memory to clear any network, in a fully decentralized manner. The search strategy for the network in which the searchers are launched is computed online by the searchers themselves without knowing the topology of the network in advance. It performs in an asynchronous environment, i.e., it implements the necessary synchronization mechanism in a decentralized manner. In every network, our protocol performs a connected strategy using at most k + 1 searchers, where k is the minimum number of searchers required to clear the network in a monotone connected way, computed in the centralized and synchronous setting. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF
35. An Improved Snap-Stabilizing PIF Algorithm.
- Author
-
Goos, Gerhard, Hartmanis, Juris, van Leeuwen, Jan, Shing-Tsaan Huang, Herman, Ted, Blin, Lélia, Cournier, Alain, and Villain, Vincent
- Abstract
A snap-stabilizing protocol, starting from any arbitrary initial configuration, always behaves according to its specification. In [10], Cournier and al. present the first snap-stabilizing Propagation of Information with Feedback (PIF) protocol in arbitrary networks. But, in order to achieve the desirable property of snap-stabilization, the algorithm needs the knowledge of the exact size of the network. This drawback prevents the protocol from working on dynamical systems. In this paper, we propose an original protocol which solves this drawback. [ABSTRACT FROM AUTHOR]
- Published
- 2003
- Full Text
- View/download PDF
36. Hardness Results and Heuristic for Multi-groups Interconnection.
- Author
-
Blin, Lélia, Laforest, Christian, Rovedakis, Stephane, and Thibault, Nicolas
- Subjects
- *
COMPUTER networks , *INTERNET service providers , *COMPUTER programming , *HEURISTIC programming , *ARTIFICIAL intelligence - Abstract
This paper is dedicated to the connection, by a provider, of multiple groups of nodes spread over a network. The role of the provider is to interconnect the members of every group. For this purpose, it must distribute the available links of the network between the groups. The general aim then is to allocate these links in such a way that the communications latencies in the allocated structure are equivalent to the ones in the original (full) network for each group. We study two approaches constructing structures preserving the maximum latency (called the diameter). Unfortunately we show that the associated optimization graph problems are difficult (one cannot be approximated by a constant and the other is NP-complete). Due to these difficulties we relax the constraint on the diameter and propose to construct a unique tree connecting all the groups together. We give a heuristic to treat this problem and we propose several analytical results on its maximum and average latencies performance. [ABSTRACT FROM PUBLISHER]
- Published
- 2010
- Full Text
- View/download PDF
37. THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS.
- Author
-
Blin, Lélia and Butelle, Franck
- Subjects
- *
ALGORITHMS , *GRAPH theory , *COMBINATORICS , *NP-complete problems , *COMPUTATIONAL complexity , *LOCAL area networks - Abstract
In this paper we present the first distributed algorithm on general graphs for the Minimum Degree Spanning Tree problem. The problem is NP-hard in sequential. Our algorithm give a Spanning Tree of a degree at most 1 from the optimal. The resulting distributed algorithm is asynchronous, it works for named asynchronous arbitrary networks and achieves O(|V|) time complexity and O(|V||E|) message complexity. [ABSTRACT FROM AUTHOR]
- Published
- 2004
- Full Text
- View/download PDF
38. Brief Announcement: Distributed Exclusive and Perpetual Tree Searching.
- Author
-
Blin, Lélia, Burman, Janna, and Nisse, Nicolas
- Published
- 2012
- Full Text
- View/download PDF
39. The First Approximated Distributed Algorithm for the Minimum Degree Spanning Tree Problem on General Graphs
- Author
-
Lélia Blin, Franck Butelle, Blin, Lélia, Université d'Évry-Val-d'Essonne (UEVE), Laboratoire d'Informatique de Paris-Nord (LIPN), Université Paris 13 (UP13)-Institut Galilée-Université Sorbonne Paris Cité (USPC)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Méthodes Informatiques (LaMI), and Université d'Évry-Val-d'Essonne (UEVE)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Theoretical computer science ,Computational complexity theory ,Computer science ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,[SCCO.COMP]Cognitive science/Computer science ,Minimum spanning tree ,[INFO] Computer Science [cs] ,k-minimum spanning tree ,Steiner tree problem ,Combinatorics ,Distributed minimum spanning tree ,symbols.namesake ,Kruskal's algorithm ,Euclidean minimum spanning tree ,Computer Science (miscellaneous) ,[INFO]Computer Science [cs] ,Time complexity ,ComputingMilieux_MISCELLANEOUS ,Mathematics ,Minimum degree spanning tree ,Discrete mathematics ,Systèmes distribués et parallèles ,Spanning tree ,Shortest-path tree ,Prim's algorithm ,Edmonds' algorithm ,Graph ,Tree (data structure) ,Informatique théorique ,Distributed algorithm ,Reverse-delete algorithm ,symbols ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,algorithmique - Abstract
In this paper we present the first distributed algorithm on general graphs for the Minimum Degree Spanning Tree problem. The problem is NP-hard in sequential. Our algorithm give a Spanning Tree of a degree at most 1 from the optimal. The resulting distributed algorithm is asynchronous, it works for named asynchronous arbitrary networks and achieves O(|V|) time complexity and O(|V||E|) message complexity.
- Published
- 2003
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.