The Experts below are selected from a list of 7710 Experts worldwide ranked by ideXlab platform

Thomas Koberda - One of the best experts on this subject based on the ideXlab platform.

  • Right-angled Artin groups and a generalized isomorphism problem for finitely generated subgroups of mapping class groups
    Geometric and Functional Analysis, 2012
    Co-Authors: Thomas Koberda
    Abstract:

    Consider the mapping class group Mod_ g , p of a surface Σ_ g , p of genus g with p punctures, and a finite collection {f_1, . . . , f_k} of mapping classes, each of which is either a Dehn twist about a simple closed curve or a pseudo-Anosov homeomorphism supported on a connected subsurface. In this paper we prove that for all sufficiently large N , the mapping classes $${\{f_1^N,\ldots,f_k^N\}}$$ generate a right-angled Artin group. The right-angled Artin group which they generate can be determined from the Combinatorial Topology of the mapping classes themselves. When {f_1, . . . , f_k} are arbitrary mapping classes, we show that sufficiently large powers of these mapping classes generate a group which embeds in a right-angled Artin group in a controlled way. We establish some analogous results for real and complex hyperbolic manifolds. We also discuss the unsolvability of the isomorphism problem for finitely generated subgroups of Mod_ g , p , and recover the fact that the isomorphism problem for right-angled Artin groups is solvable. We thus characterize the isomorphism type of many naturally occurring subgroups of Mod_ g , p .

  • right angled artin groups and a generalized isomorphism problem for finitely generated subgroups of mapping class groups
    arXiv: Geometric Topology, 2010
    Co-Authors: Thomas Koberda
    Abstract:

    Consider the mapping class group $\Mod_{g,p}$ of a surface $\Sigma_{g,p}$ of genus $g$ with $p$ punctures, and a finite collection $\{f_1,...,f_k\}$ of mapping classes, each of which is either a Dehn twist about a simple closed curve or a pseudo-Anosov homeomorphism supported on a connected subsurface. In this paper we prove that for all sufficiently large $N$, the mapping classes $\{f_1^N,...,f_k^N\}$ generate a right-angled Artin group. The right-angled Artin group which they generate can be determined from the Combinatorial Topology of the mapping classes themselves. When $\{f_1,...,f_k\}$ are arbitrary mapping classes, we show that sufficiently large powers of these mapping classes generate a group which embeds in a right-angled Artin group in a controlled way. We establish some analogous results for real and complex hyperbolic manifolds. We also discuss the unsolvability of the isomorphism problem for finitely generated subgroups of $\Mod_{g,p}$, and prove that the isomorphism problem for right-angled Artin groups is solvable. We thus characterize the isomorphism type of many naturally occurring subgroups of $\Mod_{g,p}$.

Castañeda Armando - One of the best experts on this subject based on the ideXlab platform.

  • K-set agreement bounds in round-based models through Combinatorial Topology
    'Association for Computing Machinery (ACM)', 2020
    Co-Authors: Shimi Adam, Castañeda Armando
    Abstract:

    Round-based models are the main message-passing models; Combinatorial Topology applied to distributed computing provide sweeping results like general lower bounds. We combine both to study the computability of k set-agreement. Among all the possible round-based models, we consider oblivious ones, where the constraints are given only round per round by a set of allowed graphs. And among oblivious models, we focus on closed-above ones, that is models where the set of possible graphs is a union of above-closure of graphs. These capture intuitively the underlying structure required by some communication model, like containing a ring. We then derive lower bounds and upper bounds in one round for k set-agreement, such that these bounds are proved using Combinatorial Topology but stated only in terms of graph properties. These bounds extend to multiple rounds when limiting our algorithms to oblivious ones, that is ones that recall only pairs of process and initial value

  • K-set agreement bounds in round-based models through Combinatorial Topology
    HAL CCSD, 2020
    Co-Authors: Shimi Adam, Castañeda Armando
    Abstract:

    International audienceRound-based models are the main message-passing models; Combinatorial Topology applied to distributed computing provide sweeping results like general lower bounds. We combine both to study the computability of k set-agreement. Among all the possible round-based models, we consider oblivious ones, where the constraints are given only round per round by a set of allowed graphs. And among oblivious models, we focus on closed-above ones, that is models where the set of possible graphs is a union of above-closure of graphs. These capture intuitively the underlying structure required by some communication model, like containing a ring. We then derive lower bounds and upper bounds in one round for k set-agreement, such that these bounds are proved using Combinatorial Topology but stated only in terms of graph properties. These bounds extend to multiple rounds when limiting our algorithms to oblivious ones, that is ones that recall only pairs of process and initial value

  • K set-agreement bounds in round-based models through Combinatorial Topology
    2020
    Co-Authors: Shimi Adam, Castañeda Armando
    Abstract:

    Round-based models are very common message-passing models; Combinatorial Topology applied to distributed computing provides sweeping results like general lower bounds. We combine both to study the computability of k-set agreement. Among all the possible round-based models, we consider oblivious ones, where the constraints are given only round per round by a set of allowed graphs. And among oblivious models, we focus on closed-above ones, that is models where the set of possible graphs contains all graphs with more edges than some starting graphs. These capture intuitively the underlying structure required by some communication model, like containing a ring. We then derive lower bounds and upper bounds in one round for k-set agreement, such that these bounds are proved using Combinatorial Topology but stated only in terms of graph properties. These bounds extend to multiple rounds when limiting our algorithms to be oblivious -- recalling only pairs of processes and initial value, not who send what and when.Comment: 23 pages, accepted at PODC 202

  • A Topological Perspective on Distributed Network Algorithms
    2020
    Co-Authors: Castañeda Armando, Fraigniaud Pierre, Paz Ami, Rajsbaum Sergio, Roy Matthieu, Travers Corentin
    Abstract:

    More than two decades ago, Combinatorial Topology was shown to be useful for analyzing distributed fault-tolerant algorithms in shared memory systems and in message passing systems. In this work, we show that Combinatorial Topology can also be useful for analyzing distributed algorithms in failure-free networks of arbitrary structure. To illustrate this, we analyze consensus, set-agreement, and approximate agreement in networks, and derive lower bounds for these problems under classical computational settings, such as the LOCAL model and dynamic networks

Guillaume Roblot - One of the best experts on this subject based on the ideXlab platform.

  • International Journal of Electrical and Computer Engineering 2:2 2007 Combinatorial Optimisation of Worm Propagation on an Unknown Network
    2013
    Co-Authors: Eric Filiol, Edouard Franc, Benoit Moquet, Ro Gubbioli, Guillaume Roblot
    Abstract:

    Abstract — Worm propagation profiles have significantly changed since 2003-2004: sudden world outbreaks like Blaster or Slammer have progressively disappeared and slower but stealthier worms appeared since, most of them for botnets dissemination. Decreased worm virulence results in more difficult detection. In this paper, we describe a stealth worm propagation model which has been extensively simulated and analysed on a huge virtual network. The main features of this model is its ability to infect any Internet-like network in a few seconds, whatever may be its size while greatly limiting the reinfection attempt overhead of already infected hosts. The main simulation results shows that the Combinatorial Topology of routing may have a huge impact on the worm propagation and thus some servers play a more essential and significant role than others. The real-time capability to identify them may be essential to greatly hinder worm propagation

  • Combinatorial Optimisation of Worm Propagation on an Unknown Network
    World Academy of Science, Engineering and Technology, 2007
    Co-Authors: Eric Filiol, Edouard Franc, Alessandro Gubbioli, Benoit Moquet, Guillaume Roblot
    Abstract:

    Worm propagation proles have signicantly changed since 2003-2004: sudden world outbreaks like Blaster or Slammer have progressively disappeared and slower but stealthier worms appeared since, most of them for botnets dissemination. Decreased worm virulence results in more difcult detection. In this paper, we describe a stealth worm propagation model which has been extensively simulated and analysed on a huge virtual network. The main features of this model is its ability to infect any Internet-like network in a few seconds, whatever may be its size while greatly limiting the reinfection attempt overhead of already infected hosts. The main simulation results shows that the Combinatorial Topology of routing may have a huge impact on the worm propagation and thus some servers play a more essential and signicant role than others. The real-time capability to identify them may be essential to greatly hinder worm propagation.

Vladimir Retakh - One of the best experts on this subject based on the ideXlab platform.

Armando Castaneda - One of the best experts on this subject based on the ideXlab platform.

  • k set agreement bounds in round based models through Combinatorial Topology
    Principles of Distributed Computing, 2020
    Co-Authors: Adam Shimi, Armando Castaneda
    Abstract:

    Round-based models are very common message-passing models; Combinatorial Topology applied to distributed computing provides sweeping results like general lower bounds. We combine both to study the computability of k-set agreement. Among all the possible round-based models, we consider oblivious ones, where the constraints are given only round per round by a set of allowed graphs. And among oblivious models, we focus on closed-above ones, that is models where the set of possible graphs contains all graphs with more edges than some starting graphs. These capture intuitively the underlying structure required by some communication model, like containing a ring. We then derive lower bounds and upper bounds in one round for k-set agreement, such that these bounds are proved using Combinatorial Topology but stated only in terms of graph properties. These bounds extend to multiple rounds when limiting our algorithms to be oblivious - recalling only pairs of processes and initial value, not who send what and when.

  • new Combinatorial Topology bounds for renaming the upper bound
    Journal of the ACM, 2012
    Co-Authors: Armando Castaneda, Sergio Rajsbaum
    Abstract:

    In the renaming task, n+1 processes start with unique input names from a large space and must choose unique output names taken from a smaller name space, 0,1,…, K. To rule out trivial solutions, a protocol must be anonymous: the value chosen by a process can depend on its input name and on the execution, but not on the specific process ID.Attiya et al. [1990] showed that renaming has a wait-free solution when K≥ 2n. Several algebraic Topology proofs of a lower bound stating that no such protocol exists when K

  • new Combinatorial Topology bounds for renaming the lower bound
    Distributed Computing, 2010
    Co-Authors: Armando Castaneda, Sergio Rajsbaum
    Abstract:

    In the renaming task n + 1 processes start with unique input names taken from a large space and must choose unique output names taken from a smaller name space, 0, 1, . . . , K. To rule out trivial solutions, a protocol must be anonymous: the value chosen by a process can depend on its input name and on the execution, but not on the specific process id. Attiya et al. showed in 1990 that renaming has a wait-free solution when K ≥ 2n. Several proofs of a lower bound stating that no such protocol exists when K < 2n have been published. We presented in the ACM PODC 2008 conference the following two results. First, we presented the first completely Combinatorial lower bound proof stating that no such a protocol exists when K < 2n. This bound holds for infinitely many values of n. Second, for the other values of n, we proved that the lower bound for K < 2n is incorrect, exhibiting a wait-free renaming protocol for K = 2n−1. More precisely, we presented a theorem stating that there exists a wait-free renaming protocol for K < 2n if and only if the set of integers $${\{ {n+1 \choose i+1} | 0 \leq i \leq \lfloor \frac{n-1}{2} \rfloor \}}$$ are relatively prime. This paper is the first part of the full version of the results presented in the ACM PODC 2008 conference. It includes only the lower bound. Namely, we show here that no protocol for renaming exists when K <  2n, if n is such that $${\{ {n+1 \choose i+1} | 0 \leq i \leq \lfloor \frac{n-1}{2}\rfloor \}}$$ are not relatively prime. We prove this result using the known equivalence of K-renaming for K = 2n−1 and the weak symmetry breaking task. In this task processes have no input values and the output values are 0 or 1, and it is required that in every execution in which all processes participate, at least one process decides 0 and at least one process decides 1. The full version of the upper bound appears in a companion paper [10].

  • new Combinatorial Topology upper and lower bounds for renaming
    Principles of Distributed Computing, 2008
    Co-Authors: Armando Castaneda, Sergio Rajsbaum
    Abstract:

    In the renaming task n+1 processes start with unique input names from a large space and must choose unique output names taken from a smaller name space, namely 0,1,...,K. To rule out trivial solutions, a protocol must be anonymous: the value chosen by a process can depend on its input name and on the execution, but not on the specific process id. Attiya et al. showed in 1990 that renaming has a wait-free solution when K