Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ INRIA a CCSD electro...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
versions View all 2 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Independent sets and beyond, through the prism of distributed systems and colored graphs

Authors: Sénizergues, Jonas;

Independent sets and beyond, through the prism of distributed systems and colored graphs

Abstract

Le travail présenté par cette thèse peut être divisé en deux parties, la première se concentrant sur l'autostabilisation dans des systèmes distribués, la seconde sur de l'algorithmique de graphe classique. La partie portant sur l'autostabilisation s'intéresse aux pannes Byzantines pour des problèmes qui n'avaient pas d'algorithme connu supportant celles-ci. L'un d'eux est ensuite utilisé pour proposer un mécanisme produisant des algorithme autostabilisants pour tout problème raccommodable dans des réseaux anonymes. La partie d'algorithmique de graphes introduit a nouveau problème étendant des travaux antérieurs sur les couplages colorés et donne un résultat de difficulté algorithmique ainsi qu'un algorithme FPT pour un certain paramètre.Le chapitre 3 introduit un algorithme qui supporte les pannes Byzantines et résout le problème de l'indépendant maximal dans les systèmes anonymes en O(n²) rounds avec forte probabilité sous le démon distribué juste. Il donne ensuite une version légèrement modifiée de cet algorithme qui résout le même problème sous le démon distribué antagoniste (sans supporter de pannes Byzantines) en O(n²) opérations.Le chapitre 5 introduit un algorithme qui supporte les pannes Byzantines et résout le problème de partition minimales en cliques en O(Δn) rounds sous le démon distribué juste dans des systèmes à identifiants uniques.Le chapitre 4 introduit un algorithme qui résout le problème du (k,k-1)-ensemble dirigeant dans les réseaux anonymes sous le démon Gouda. La construction en parallèle de tels ensembles dirigeants permet de trouver une coloration à distance K, dont on utilise les couleurs comme identifiants pour résoudre n'importe quel problème raccommodable sur des réseaux anonymes.Enfin, le chapitre 6 introduit un nouveau problème, le problème du couplage maximum minimalement coloré, qui étend des travaux antérieurs sur les couplages colorés. Ce problème est ici démontré NP-dur, et difficile à approximer sous un ratio logarithmique de la taille du graphe. Il y est également démontré qu'il W[2]-difficile en considérant le paramètre "taille de la solution", mais FPT en considérant le paramètre "taille d'un couplage maximum".

The work presented in this thesis can be divided in two, the first part focusing on self-stabilization in distributed systems, and the second one on classical graph algorithms.The self-stabilization part deals with Byzantine faults for problems that had no prior algorithm handling those. One of them is then used to propose a way to produce self-stabilizing algorithms for mendable problems in anonymous networks. The classical graph algorithm part introduces a new problem that extends some previous work on colored matchings and gives a hardness results as well as an FPT algorithm for a specific parameter.Chapter 3 introduces an algorithm that handles Byzantine faults and solves the MIS problem in anonymous systems in O(n²) rounds with high probability under the fair distributed daemon. It then gives a slightly modified version of this algorithm, that solves the same problem under the adversarial distributed daemon (without handling Byzantine faults) in O(n²) moves.Chapter 5 introduces an algorithm that handles Byzantine faults and solves the Minimal Clique Decomposition problem in O(Δn) rounds under the fair distributed daemon in systems with unique identifiers.Chapter 4 introduces an algorithm that solves the (k,k-1)-ruling set problem in anonymous networks under the Gouda daemon. The parallel construction of multiple such ruling sets allows to find a distance-K coloring in an anonymous network, whose colors are used as identifiers to solve any mending problems on anonymous networks.Finally, Chapter 6 introduces a new problem, the Minimum Colored Maximum Matching problem, that extends what had already been done on colored matchings. The problem is shown to be NP-hard and hard to approximate within a logarithmic ratio of the size of the graph. It is also proven W[2]-hard with the parameter "size of the solution", but fixed-parameter tractable with the parameter "size of a maximum matching".

Country
France
Keywords

Distributed, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Algorithmes, Distribué, Graphes, Autostabilisation, Complexity, Complexité, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Graphs, Approximation, Algorithms, Self-Stabilizing

14 references, page 1 of 2

2 Graphs and models 13 2.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Graph notions and notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Models of distributed systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.1 Rules, transitions, and executions . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.2 Daemons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.3 Algorithm and self-stabilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.4 Byzantine faults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.5 Complexities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Maximal Independent Set 21 3.1 State of the art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 With Byzantines Nodes under the Fair Daemon . . . . . . . . . . . . . . . . . . . . . . . 22 3.2.1 Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.2 An example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.3 The proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 In an Anonymous System under the Adversary Daemon . . . . . . . . . . . . . . . . . . . 34 3.3.1 An example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.3.2 The proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4 Ruling Set 45 4.1 State of the art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.2 Self-Stabilizing Algorithm for Computing a (k, k-1)-Ruling Set . . . . . . . . . . . . . . . 48 4.2.1 General Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2.2 The Clock System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.2.3 Handling Initial and Perturbed Configurations . . . . . . . . . . . . . . . . . . . . 52 4.3 Proof of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 6 Minimally Colored Maximum Matching 107 6.1 Notations and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 6.2 Introduction to the MCMM problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 6.3 NP-hardness and W[2]-hardness of MCMM . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.4 Hardness of approximating MCMM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 6.5 MCMM is FTP when parameterized by the maximum size of a matching in the input graph 118 6.6 APX-completeness on collections of P2 and P3 . . . . . . . . . . . . . . . . . . . . . . . 125 6.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 We also use the standard notation for integer segments. When (x, y) ∈ Z, Jx, yK is the set {r ∈ Z | x ≤ r ≤ y}.

[1] Noga Alon, László Babai, and Alon Itai. “A fast and simple randomized parallel algorithm for the maximal independent set problem”. In: Journal of Algorithms 7.4 (1986), pp. 567-583.

[2] Baruch Awerbuch. “Complexity of Network Synchronization”. In: J. ACM 32.4 (1985), pp. 804-823.

[3] Baruch Awerbuch et al. “Network decomposition and locality in distributed computation”. In: FOCS. Vol. 30. Citeseer. 1989, pp. 364- 369.

[4] Alkida Balliu, Sebastian Brandt, and Dennis Olivetti. “Distributed lower bounds for ruling sets”. In: SIAM Journal on Computing 51.1 (2022), pp. 70-115.

[26] Shlomi Dolev. Self-stabilization. MIT press, 2000. [OpenAIRE]

[27] Shlomi Dolev, Amos Israeli, and Shlomo Moran. “Uniform dynamic self-stabilizing leader election”. In: Distributed Algorithms. Ed. by Sam Toueg, Paul G. Spirakis, and Lefteris Kirousis. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992, pp. 167-180.

[28] Rod G. Downey and Michael R. Fellows. “Fixed-Parameter Tractability and Completeness I: Basic Results”. In: SIAM Journal on Computing 24.4 (1995), pp. 873-921.

  • BIP!
    Impact byBIP!
    citations
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
  • citations
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
    Powered byBIP!BIP!
Powered by OpenAIRE graph
Found an issue? Give us feedback
citations
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Related to Research communities
INRIA