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

Thibault Rieutord - One of the best experts on this subject based on the ideXlab platform.

  • Brief Announcement: Compact Topology of Shared-Memory Adversaries
    2020
    Co-Authors: Petr Kuznetsov, Thibault Rieutord, Yuan He
    Abstract:

    The paper proposes a simple topological characterization of a large class of adversarial distributed-computing models via affine tasks: sub-complexes of the second iteration of the standard Chromatic Subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. While an adversary is in general defined as a non-compact set of infinite runs, its affine task is just a finite subset of runs of the 2-round iterated immediate snapshot (IIS) model. Our results generalize and improve all previously derived topological characterizations of distributed-computing models.

  • DISC - Brief Announcement: Compact Topology of Shared-Memory Adversaries
    2020
    Co-Authors: Petr Kuznetsov, Thibault Rieutord, Yuan He
    Abstract:

    The paper proposes a simple topological characterization of a large class of adversarial distributed-computing models via affine tasks: sub-complexes of the second iteration of the standard Chromatic Subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. While an adversary is in general defined as a non-compact set of infinite runs, its affine task is just a finite subset of runs of the 2-round iterated immediate snapshot (IIS) model. Our results generalize and improve all previously derived topological characterizations of distributed-computing models.

  • OPODIS - Read-Write Memory and k-Set Consensus as an Affine Task
    2020
    Co-Authors: Eli Gafni, Petr Kuznetsov, Yuan He, Thibault Rieutord
    Abstract:

    The wait-free read-write memory model has been characterized as an iterated Immediate Snapshot (IS) task. The IS task is affine — it can be defined as a (sub)set of simplices of the standard Chromatic Subdivision. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, k-set-consensus objects can be used is "natural" by presenting the corresponding simple affine task captured by a subset of 2-round IS runs. As an "unnatural" example, the model using the abstraction of Weak Symmetry Breaking (WSB) cannot be captured by a set of IS runs and, thus, cannot be represented as an affine task. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.

  • PODC - An Asynchronous Computability Theorem for Fair Adversaries
    Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018
    Co-Authors: Petr Kuznetsov, Thibault Rieutord, Yuan He
    Abstract:

    This paper proposes a simple topological characterization of a large class of fair adversarial models via affine tasks: sub-complexes of the second iteration of the standard Chromatic Subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. Fair adversaries include, but are not restricted to, the models of wait-freedom, t-resilience, and k-concurrency. Our results generalize and improve all previously derived topological characterizations of the ability of a model to solve distributed tasks.

  • Read-Write Memory and k-Set Consensus as an Affine Task
    arXiv: Distributed Parallel and Cluster Computing, 2016
    Co-Authors: Eli Gafni, Petr Kuznetsov, Yuan He, Thibault Rieutord
    Abstract:

    The wait-free read-write memory model has been characterized as an iterated \emph{Immediate Snapshot} (IS) task. The IS task is \emph{affine}---it can be defined as a (sub)set of simplices of the standard Chromatic Subdivision. It is known that the task of \emph{Weak Symmetry Breaking} (WSB) cannot be represented as an affine task. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, $k$-set-consensus objects can be used is, unlike WSB, "natural" by presenting the corresponding simple affine task captured by a subset of $2$-round IS runs. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.

Yuan He - One of the best experts on this subject based on the ideXlab platform.

  • Brief Announcement: Compact Topology of Shared-Memory Adversaries
    2020
    Co-Authors: Petr Kuznetsov, Thibault Rieutord, Yuan He
    Abstract:

    The paper proposes a simple topological characterization of a large class of adversarial distributed-computing models via affine tasks: sub-complexes of the second iteration of the standard Chromatic Subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. While an adversary is in general defined as a non-compact set of infinite runs, its affine task is just a finite subset of runs of the 2-round iterated immediate snapshot (IIS) model. Our results generalize and improve all previously derived topological characterizations of distributed-computing models.

  • DISC - Brief Announcement: Compact Topology of Shared-Memory Adversaries
    2020
    Co-Authors: Petr Kuznetsov, Thibault Rieutord, Yuan He
    Abstract:

    The paper proposes a simple topological characterization of a large class of adversarial distributed-computing models via affine tasks: sub-complexes of the second iteration of the standard Chromatic Subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. While an adversary is in general defined as a non-compact set of infinite runs, its affine task is just a finite subset of runs of the 2-round iterated immediate snapshot (IIS) model. Our results generalize and improve all previously derived topological characterizations of distributed-computing models.

  • OPODIS - Read-Write Memory and k-Set Consensus as an Affine Task
    2020
    Co-Authors: Eli Gafni, Petr Kuznetsov, Yuan He, Thibault Rieutord
    Abstract:

    The wait-free read-write memory model has been characterized as an iterated Immediate Snapshot (IS) task. The IS task is affine — it can be defined as a (sub)set of simplices of the standard Chromatic Subdivision. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, k-set-consensus objects can be used is "natural" by presenting the corresponding simple affine task captured by a subset of 2-round IS runs. As an "unnatural" example, the model using the abstraction of Weak Symmetry Breaking (WSB) cannot be captured by a set of IS runs and, thus, cannot be represented as an affine task. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.

  • PODC - An Asynchronous Computability Theorem for Fair Adversaries
    Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018
    Co-Authors: Petr Kuznetsov, Thibault Rieutord, Yuan He
    Abstract:

    This paper proposes a simple topological characterization of a large class of fair adversarial models via affine tasks: sub-complexes of the second iteration of the standard Chromatic Subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. Fair adversaries include, but are not restricted to, the models of wait-freedom, t-resilience, and k-concurrency. Our results generalize and improve all previously derived topological characterizations of the ability of a model to solve distributed tasks.

  • Read-Write Memory and k-Set Consensus as an Affine Task
    arXiv: Distributed Parallel and Cluster Computing, 2016
    Co-Authors: Eli Gafni, Petr Kuznetsov, Yuan He, Thibault Rieutord
    Abstract:

    The wait-free read-write memory model has been characterized as an iterated \emph{Immediate Snapshot} (IS) task. The IS task is \emph{affine}---it can be defined as a (sub)set of simplices of the standard Chromatic Subdivision. It is known that the task of \emph{Weak Symmetry Breaking} (WSB) cannot be represented as an affine task. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, $k$-set-consensus objects can be used is, unlike WSB, "natural" by presenting the corresponding simple affine task captured by a subset of $2$-round IS runs. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.

Petr Kuznetsov - One of the best experts on this subject based on the ideXlab platform.

  • Brief Announcement: Compact Topology of Shared-Memory Adversaries
    2020
    Co-Authors: Petr Kuznetsov, Thibault Rieutord, Yuan He
    Abstract:

    The paper proposes a simple topological characterization of a large class of adversarial distributed-computing models via affine tasks: sub-complexes of the second iteration of the standard Chromatic Subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. While an adversary is in general defined as a non-compact set of infinite runs, its affine task is just a finite subset of runs of the 2-round iterated immediate snapshot (IIS) model. Our results generalize and improve all previously derived topological characterizations of distributed-computing models.

  • DISC - Brief Announcement: Compact Topology of Shared-Memory Adversaries
    2020
    Co-Authors: Petr Kuznetsov, Thibault Rieutord, Yuan He
    Abstract:

    The paper proposes a simple topological characterization of a large class of adversarial distributed-computing models via affine tasks: sub-complexes of the second iteration of the standard Chromatic Subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. While an adversary is in general defined as a non-compact set of infinite runs, its affine task is just a finite subset of runs of the 2-round iterated immediate snapshot (IIS) model. Our results generalize and improve all previously derived topological characterizations of distributed-computing models.

  • OPODIS - Read-Write Memory and k-Set Consensus as an Affine Task
    2020
    Co-Authors: Eli Gafni, Petr Kuznetsov, Yuan He, Thibault Rieutord
    Abstract:

    The wait-free read-write memory model has been characterized as an iterated Immediate Snapshot (IS) task. The IS task is affine — it can be defined as a (sub)set of simplices of the standard Chromatic Subdivision. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, k-set-consensus objects can be used is "natural" by presenting the corresponding simple affine task captured by a subset of 2-round IS runs. As an "unnatural" example, the model using the abstraction of Weak Symmetry Breaking (WSB) cannot be captured by a set of IS runs and, thus, cannot be represented as an affine task. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.

  • PODC - An Asynchronous Computability Theorem for Fair Adversaries
    Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018
    Co-Authors: Petr Kuznetsov, Thibault Rieutord, Yuan He
    Abstract:

    This paper proposes a simple topological characterization of a large class of fair adversarial models via affine tasks: sub-complexes of the second iteration of the standard Chromatic Subdivision. We show that the task computability of a model in the class is precisely captured by iterations of the corresponding affine task. Fair adversaries include, but are not restricted to, the models of wait-freedom, t-resilience, and k-concurrency. Our results generalize and improve all previously derived topological characterizations of the ability of a model to solve distributed tasks.

  • Read-Write Memory and k-Set Consensus as an Affine Task
    arXiv: Distributed Parallel and Cluster Computing, 2016
    Co-Authors: Eli Gafni, Petr Kuznetsov, Yuan He, Thibault Rieutord
    Abstract:

    The wait-free read-write memory model has been characterized as an iterated \emph{Immediate Snapshot} (IS) task. The IS task is \emph{affine}---it can be defined as a (sub)set of simplices of the standard Chromatic Subdivision. It is known that the task of \emph{Weak Symmetry Breaking} (WSB) cannot be represented as an affine task. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, $k$-set-consensus objects can be used is, unlike WSB, "natural" by presenting the corresponding simple affine task captured by a subset of $2$-round IS runs. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.

Eli Gafni - One of the best experts on this subject based on the ideXlab platform.

  • OPODIS - Read-Write Memory and k-Set Consensus as an Affine Task
    2020
    Co-Authors: Eli Gafni, Petr Kuznetsov, Yuan He, Thibault Rieutord
    Abstract:

    The wait-free read-write memory model has been characterized as an iterated Immediate Snapshot (IS) task. The IS task is affine — it can be defined as a (sub)set of simplices of the standard Chromatic Subdivision. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, k-set-consensus objects can be used is "natural" by presenting the corresponding simple affine task captured by a subset of 2-round IS runs. As an "unnatural" example, the model using the abstraction of Weak Symmetry Breaking (WSB) cannot be captured by a set of IS runs and, thus, cannot be represented as an affine task. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.

  • Read-Write Memory and k-Set Consensus as an Affine Task
    arXiv: Distributed Parallel and Cluster Computing, 2016
    Co-Authors: Eli Gafni, Petr Kuznetsov, Yuan He, Thibault Rieutord
    Abstract:

    The wait-free read-write memory model has been characterized as an iterated \emph{Immediate Snapshot} (IS) task. The IS task is \emph{affine}---it can be defined as a (sub)set of simplices of the standard Chromatic Subdivision. It is known that the task of \emph{Weak Symmetry Breaking} (WSB) cannot be represented as an affine task. In this paper, we highlight the phenomenon of a "natural" model that can be captured by an iterated affine task and, thus, by a subset of runs of the iterated immediate snapshot model. We show that the read-write memory model in which, additionally, $k$-set-consensus objects can be used is, unlike WSB, "natural" by presenting the corresponding simple affine task captured by a subset of $2$-round IS runs. Our results imply the first combinatorial characterization of models equipped with abstractions other than read-write memory that applies to generic tasks.

Nir Shavit - One of the best experts on this subject based on the ideXlab platform.

  • Toward a Topological Characterization of Asynchronous Complexity
    SIAM Journal on Computing, 2006
    Co-Authors: Gunnar Hoest, Nir Shavit
    Abstract:

    This paper introduces the use of topological models and methods, formerly used to analyze computability, as tools for the quantification and classification of asynchronous complexity. We present the first asynchronous complexity theorem, applied to decision tasks in the iterated immediate snapshot (IIS) model of Borowsky and Gafni. We do so by introducing a novel form of topological tool called the nonuniform Chromatic Subdivision. Building on the framework of Herlihy and Shavit's topological computability model, our theorem states that the time complexity of any asynchronous algorithm is directly proportional to the level of nonuniform Chromatic Subdivisions necessary to allow a simplicial map from a task's input complex to its output complex. To show the power of our theorem, we use it to derive a new tight bound on the time to achieve n process approximate agreement in the IIS model: $\bigl\lceil \log_d \frac{\max\_input - \min\_input}{\epsilon} \bigr\rceil$, where d = 3 for two processes and d = 2 for three or more. This closes an intriguing gap between the known upper and lower bounds implied by the work of Aspnes and Herlihy. More than the new bounds themselves, the importance of our asynchronous complexity theorem is that the algorithms and lower bounds it allows us to derive are intuitive and simple, with topological proofs that require no mention of concurrency at all.

  • Towards a topological characterization of asynchronous complexity
    Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing - PODC '97, 1997
    Co-Authors: Gunnar Hoest, Nir Shavit
    Abstract:

    This paper introduces the use of topological models and methods, formerly used to analyze computability, as tools for the quantification and classification of asynchronous complexity. We present the first asynchronous complexity theorem, applied to decision tasks in the iterated immediate snapshot (IIS) model of Borowsky and Gafni. We do so by introducing a novel form of topological tool called the nonuniform Chromatic Subdivision. Building on the framework of Herlihy and Shavit's topological computability model, our theorem states that the time complexity of any asynchronous algorithm is directly proportional to the level of nonuniform Chromatic Subdivisions necessary to allow a simplicial map from a task's input complex to its output complex. To show the power of our theorem, we use it to derive a new tight bound on the time to achieve n process approximate agreement in the IIS model: logd max input−min input � , where d = 3 for two processes and d = 2 for three or more. This closes an intriguing gap between the known upper and lower bounds implied by the work of Aspnes and Herlihy. More than the new bounds themselves, the importance of our asynchronous complexity theorem is that the algorithms and lower bounds it allows us to derive are intuitive and simple, with topological proofs that require no mention of concurrency at all.