The Experts below are selected from a list of 99 Experts worldwide ranked by ideXlab platform
Sergio Rajsbaum - One of the best experts on this subject based on the ideXlab platform.
-
SSS - A Topological View of Partitioning Arguments: Reducing k -Set Agreement to Consensus
Lecture Notes in Computer Science, 2019Co-Authors: Hugo Rincon Galeana, Kyrill Winkler, Ulrich Schmid, Sergio RajsbaumAbstract:The objective of this paper is to understand the effect of partitioning in distributed computing models. In spite of being quite similar agreement problems, (deterministic) consensus (1-set agreement) and k-set agreement (for \(k>1\)) require surprisingly different techniques for proving impossibilities. There is a widely applicable generic theorem, however, which allows to reduce the impossibility of k-set agreement to consensus in message-passing models that allow some partitioning. In this paper, we provide the topological representation of this theorem, which reveals how partitioning is reflected in the Protocol Complex: It turns out that this leads to a “color splitting” of the algorithm’s decision map, which separates the sub-Complexes representing the partitioned processes. We also harvest a general advantage of topological results, which allowed us to carry over our findings to shared memory systems. We first demonstrate the utility of our reduction theorem by proving that d-set agreement cannot be solved in the d-solo asynchronous read-write model even when a single process may crash, not just in the wait-free case. Moreover, our new insights into the structure of Protocol Complexes gave us the idea for a simple proof of the fact that no partitioning argument can provide a valid impossibility proof for wait-free set agreement in the iterated immediate snapshot model: For any set of partition-compatible runs (which do not contain runs where all processes always have a complete view), we provide a way to construct a simple algorithm that solves set agreement.
-
Collapsibility of read/write models using discrete morse theory
Journal of Applied and Computational Topology, 2018Co-Authors: Fernando Benavides, Sergio RajsbaumAbstract:The celebrated asynchronous computability theorem provides a characterization of the class of decision tasks that can be solved in a wait-free manner by asynchronous processes that communicate by writing and taking atomic snapshots of a shared memory. Several variations of the model have been proposed, all equivalent for wait-free solution of decision tasks, in spite of the fact that the Protocol Complexes that arise from the different models are structurally distinct. The topological and combinatorial properties of these snapshot Protocol Complexes have been studied in detail, providing explanations for why the asynchronous computability theorem holds in all the models. In reality concurrent systems do not provide processes with snapshot operations. Instead, snapshots are implemented (by a wait-free Protocol) using operations that write and read individual shared memory locations. Thus, read/write Protocols are also computationally equivalent to snapshot Protocols. However, the structure of the read/write Protocol Complex has not been studied. In this paper we show that the read/write iterated Protocol Complex is collapsible, using discrete Morse theory. Furthermore, we show that a distributed Protocol that wait-free implements atomic snapshots in effect is performing the collapses.
-
LATIN - The Read/Write Protocol Complex Is Collapsible
LATIN 2016: Theoretical Informatics, 2016Co-Authors: Fernando Benavides, Sergio RajsbaumAbstract:The celebrated asynchronous computability theorem provides a characterization of the class of decision tasks that can be solved in a wait-free manner by asynchronous processes that communicate by writing and taking atomic snapshots of a shared memory. Several variations of the model have been proposed (immediate snapshots and iterated immediate snapshots), all equivalent for wait-free solution of decision tasks, in spite of the fact that the Protocol Complexes that arise from the different models are structurally distinct. The topological and combinatorial properties of these snapshot Protocol Complexes have been studied in detail, providing explanations for why the asynchronous computability theorem holds in all the models.
-
The read/write Protocol Complex is collapsible ?
arXiv: Distributed Parallel and Cluster Computing, 2015Co-Authors: Fernando Benavides, Sergio RajsbaumAbstract:The celebrated \emph{asynchronous computability theorem} provides a characterization of the class of decision tasks that can be solved in a wait-free manner by asynchronous processes that communicate by writing and taking atomic snapshots of a shared memory. Several variations of the model have been proposed (immediate snapshots and iterated immediate snapshots), all equivalent for wait-free solution of decision tasks, in spite of the fact that the Protocol Complexes that arise from the different models are structurally distinct. The topological and combinatorial properties of these snapshot Protocol Complexes have been studied in detail, providing explanations for why the asynchronous computability theorem holds in all the models. In reality concurrent systems do not provide processes with snapshot operations. Instead, snapshots are implemented (by a wait-free Protocol) using operations that write and read individual shared memory locations. Thus, read/write Protocols are also computationally equivalent to snapshot Protocols. However, the structure of the read/write Protocol Complex has not been studied. In this paper we show that the read/write iterated Protocol Complex is collapsible (and hence contractible). Furthermore, we show that a distributed Protocol that wait-free implements atomic snapshots in effect is performing the collapses.
-
PODC - The topology of shared-memory adversaries
Proceeding of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing - PODC '10, 2010Co-Authors: Maurice Herlihy, Sergio RajsbaumAbstract:Failure patterns in modern parallel and distributed system are not necessarily uniform. The notion of an adversary scheduler is a natural way to extend the classical wait-free and t-faulty models of computation. A well-established way to characterize an adversary is by its set of cores, where a core is any minimal set of processes that cannot all fail in any execution. We show that the Protocol Complex associated with an adversary is (c-2)-connected, where c is the size of the adversary's smallest core. This implies, among other results, that such an adversary can solve c-set agreement, but not (c-1)-set agreement. The proofs are combinatorial, relying on a novel application of the Nerve Theorem of modern combinatorial topology.
Yoram Moses - One of the best experts on this subject based on the ideXlab platform.
-
PODC - Unbeatable Set Consensus via Topological and Combinatorial Reasoning
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016Co-Authors: Armando Castañeda, Yannai A. Gonczarowski, Yoram MosesAbstract:The set consensus problem has played an important role in the study of distributed systems for over two decades. Indeed, the search for lower bounds and impossibility results for this problem spawned the topological approach to distributed computing, which has given rise to new techniques in the design and analysis of Protocols. The design of efficient solutions to set consensus has also proven to be challenging. In the synchronous crash failure model, the literature contains a sequence of solutions to set consensus, each improving upon the previous ones. This paper presents an unbeatable Protocol for nonuniform k-set consensus in the synchronous crash failure model. This is an efficient Protocol whose decision times cannot be improved upon. Moreover, the description of our Protocol is extremely succinct. Proving unbeatability of this Protocol is a nontrivial challenge. We provide two proofs for its unbeatability: one is a subtle constructive combinatorial proof, and the other is a topological proof of a new style. These two proofs provide new insight into the connection between topological reasoning and combinatorial reasoning about Protocols, which has long been a subject of interest. In particular, our topological proof reasons in a novel way about subComplexes of the Protocol Complex, and sheds light on an open question posed by Guerraoui and Pochon (2009). Finally, using the machinery developed in the design of this unbeatable Protocol, we propose a Protocol for uniform k-set consensus that beats all known solutions by a large margin.
-
Unbeatable Set Consensus via Topological and Combinatorial Reasoning
arXiv: Distributed Parallel and Cluster Computing, 2016Co-Authors: Armando Castañeda, Yannai A. Gonczarowski, Yoram MosesAbstract:The set consensus problem has played an important role in the study of distributed systems for over two decades. Indeed, the search for lower bounds and impossibility results for this problem spawned the topological approach to distributed computing, which has given rise to new techniques in the design and analysis of Protocols. The design of efficient solutions to set consensus has also proven to be challenging. In the synchronous crash failure model, the literature contains a sequence of solutions to set consensus, each improving upon the previous ones. This paper presents an unbeatable Protocol for nonuniform k-set consensus in the synchronous crash failure model. This is an efficient Protocol whose decision times cannot be improved upon. Moreover, the description of our Protocol is extremely succinct. Proving unbeatability of this Protocol is a nontrivial challenge. We provide two proofs for its unbeatability: one is a subtle constructive combinatorial proof, and the other is a topological proof of a new style. These two proofs provide new insight into the connection between topological reasoning and combinatorial reasoning about Protocols, which has long been a subject of interest. In particular, our topological proof reasons in a novel way about subComplexes of the Protocol Complex, and sheds light on an open question posed by Guerraoui and Pochon (2009). Finally, using the machinery developed in the design of this unbeatable Protocol, we propose a Protocol for uniform k-set consensus that beats all known solutions by a large margin.
Armando Castañeda - One of the best experts on this subject based on the ideXlab platform.
-
PODC - Unbeatable Set Consensus via Topological and Combinatorial Reasoning
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016Co-Authors: Armando Castañeda, Yannai A. Gonczarowski, Yoram MosesAbstract:The set consensus problem has played an important role in the study of distributed systems for over two decades. Indeed, the search for lower bounds and impossibility results for this problem spawned the topological approach to distributed computing, which has given rise to new techniques in the design and analysis of Protocols. The design of efficient solutions to set consensus has also proven to be challenging. In the synchronous crash failure model, the literature contains a sequence of solutions to set consensus, each improving upon the previous ones. This paper presents an unbeatable Protocol for nonuniform k-set consensus in the synchronous crash failure model. This is an efficient Protocol whose decision times cannot be improved upon. Moreover, the description of our Protocol is extremely succinct. Proving unbeatability of this Protocol is a nontrivial challenge. We provide two proofs for its unbeatability: one is a subtle constructive combinatorial proof, and the other is a topological proof of a new style. These two proofs provide new insight into the connection between topological reasoning and combinatorial reasoning about Protocols, which has long been a subject of interest. In particular, our topological proof reasons in a novel way about subComplexes of the Protocol Complex, and sheds light on an open question posed by Guerraoui and Pochon (2009). Finally, using the machinery developed in the design of this unbeatable Protocol, we propose a Protocol for uniform k-set consensus that beats all known solutions by a large margin.
-
Unbeatable Set Consensus via Topological and Combinatorial Reasoning
arXiv: Distributed Parallel and Cluster Computing, 2016Co-Authors: Armando Castañeda, Yannai A. Gonczarowski, Yoram MosesAbstract:The set consensus problem has played an important role in the study of distributed systems for over two decades. Indeed, the search for lower bounds and impossibility results for this problem spawned the topological approach to distributed computing, which has given rise to new techniques in the design and analysis of Protocols. The design of efficient solutions to set consensus has also proven to be challenging. In the synchronous crash failure model, the literature contains a sequence of solutions to set consensus, each improving upon the previous ones. This paper presents an unbeatable Protocol for nonuniform k-set consensus in the synchronous crash failure model. This is an efficient Protocol whose decision times cannot be improved upon. Moreover, the description of our Protocol is extremely succinct. Proving unbeatability of this Protocol is a nontrivial challenge. We provide two proofs for its unbeatability: one is a subtle constructive combinatorial proof, and the other is a topological proof of a new style. These two proofs provide new insight into the connection between topological reasoning and combinatorial reasoning about Protocols, which has long been a subject of interest. In particular, our topological proof reasons in a novel way about subComplexes of the Protocol Complex, and sheds light on an open question posed by Guerraoui and Pochon (2009). Finally, using the machinery developed in the design of this unbeatable Protocol, we propose a Protocol for uniform k-set consensus that beats all known solutions by a large margin.
Christine Tasson - One of the best experts on this subject based on the ideXlab platform.
-
Geometric and combinatorial views on asynchronous computability
Distributed Computing, 2018Co-Authors: Éric Goubault, Samuel Mimram, Christine TassonAbstract:We show that the Protocol Complex formalization of fault-tolerant Protocols can be directly derived from a suitable semantics of the underlying synchronization and communication primitives, based on a geometrization of the state space. By constructing a one-to-one relationship between simplices of the Protocol Complex and (di)homotopy classes of (di)paths in the latter semantics, we describe a connection between these two geometric approaches to distributed computing: Protocol Complexes and directed algebraic topology. This is exemplified on atomic snapshot, iterated snapshot and layered immediate snapshot Protocols, where a well-known combinatorial structure, interval orders, plays a key role. We believe that this correspondence between models will extend to proving impossibility results for much more intricate fault-tolerant distributed architectures.
-
From Geometric Semantics to Asynchronous Computability
2016Co-Authors: Éric Goubault, Samuel Mimram, Lix École Polytechnique, Christine TassonAbstract:We show that the Protocol Complex formalization of fault-tolerant Protocols can be derived from first principles, i.e. directly from a suitable semantics of the underlying synchronization and commu-nication primitives, based on a geometrization of the state space. By constructing a one-to-one relationship between simplices of the Protocol Complex and (di)homotopy classes of (di)paths in the later semantics, we describe a connection between these two geometric approaches to distributed computing: Protocol Complexes and di-rected algebraic topology. This is exemplified on atomic snapshot, iterated snapshot and layered immediate snapshot Protocols, where a well-known combinatorial structure, interval orders, plays a key role. We believe that this correspondence between models paves the way to proving impossibility results for much more intricate fault-tolerant distributed architectures. Categories and Subject Descriptors F.1.1 [Computation by Ab-stract Devices]: Models of Computation–computability theory
-
DISC - From Geometric Semantics to Asynchronous Computability
Lecture Notes in Computer Science, 2015Co-Authors: Éric Goubault, Samuel Mimram, Christine TassonAbstract:We show that the Protocol Complex formalization of fault-tolerant Protocols can be directly derived from a suitable semantics of the underlying synchronization and communication primitives, based on a geometrization of the state space. By constructing a one-to-one relationship between simplices of the Protocol Complex and dihomotopy classes of dipaths in the latter semantics, we describe a connection between these two geometric approaches to distributed computing: Protocol Complexes and directed algebraic topology. This is exemplified on atomic snapshot, iterated snapshot and layered immediate snapshot Protocols, where a well-known combinatorial structure, interval orders, plays a key role. We believe that this correspondence between models will extend to proving impossibility results for much more intricate fault-tolerant distributed architectures.
-
From Geometric Semantics to Asynchronous Computability
2015Co-Authors: Éric Goubault, Samuel Mimram, Christine TassonAbstract:We show that the Protocol Complex formalization of fault-tolerant Protocols can be directly derived from a suitable semantics of the underlying synchronization and communication primitives, based on a geometrization of the state space. By constructing a one-to-one relationship between simplices of the Protocol Complex and (di)homotopy classes of (di)paths in the latter semantics, we describe a connection between these two geometric approaches to distributed computing: Protocol Complexes and directed algebraic topology. This is exemplified on atomic snapshot, iterated snapshot and layered immediate snapshot Protocols, where a well-known combinatorial structure, interval orders, plays a key role. We believe that this correspondence between models will extend to proving impossibility results for much more intricate fault-tolerant distributed architectures.
Maurice Herlihy - One of the best experts on this subject based on the ideXlab platform.
-
DISC - Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems
2015Co-Authors: Hammurabi Mendes, Maurice HerlihyAbstract:In this paper, we show that the Protocol Complex of a Byzantine synchronous system can remain (k −1)-connected for up to ⌈t/k⌉ rounds, where t is the maximum number of Byzantine processes, and t ≥ k ≥ 1. Protocol Complex connectivity is important since a (k −1)-connected Protocol Complex does not admit solutions for the k-set agreement problem. In crash-failure systems, the connectivity upper bound is ⌊t/k⌋ rounds, therefore, in Byzantine systems, the ambiguity in the communication can potentially persist for one extra round, delaying the solution to k-set agreement and other related problems. Additionally, we show that our connectivity bound is tight, at least when n+1, the number of processes, is suitably large compared to t. We solve a formulation of k-set agreement appropriate for Byzantine systems in ⌈t/k⌉ + 1 rounds. Essentially, we see that Byzantine failures can potentially require us one extra round to handle ambiguity, and, in specific cases, at most that.
-
Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems
arXiv: Distributed Parallel and Cluster Computing, 2015Co-Authors: Hammurabi Mendes, Maurice HerlihyAbstract:In this paper, we show that the Protocol Complex of a Byzantine synchronous system can remain $(k - 1)$-connected for up to $\lceil t/k \rceil$ rounds, where $t$ is the maximum number of Byzantine processes, and $t \ge k \ge 1$. Protocol Complex connectivity is important since a $(k - 1)$-connected Protocol Complex does not admit solutions for the $k$-set agreement problem. In crash-failure systems, the connectivity upper bound is $\lfloor t/k \rfloor$ rounds, therefore, in Byzantine systems, the ambiguity in the communication can potentially persist for one extra round, delaying the solution to $k$-set agreement and other related problems. Additionally, we show that our connectivity bound is tight, at least when $n + 1$, the number of processes, is suitably large compared to $t$. We solve a formulation of $k$-set agreement appropriate for Byzantine systems in $\lceil t/k \rceil + 1$ rounds. Essentially, we see that Byzantine failures can potentially require us one extra round to handle ambiguity, and, in specific cases, at most that.
-
PODC - The topology of shared-memory adversaries
Proceeding of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing - PODC '10, 2010Co-Authors: Maurice Herlihy, Sergio RajsbaumAbstract:Failure patterns in modern parallel and distributed system are not necessarily uniform. The notion of an adversary scheduler is a natural way to extend the classical wait-free and t-faulty models of computation. A well-established way to characterize an adversary is by its set of cores, where a core is any minimal set of processes that cannot all fail in any execution. We show that the Protocol Complex associated with an adversary is (c-2)-connected, where c is the size of the adversary's smallest core. This implies, among other results, that such an adversary can solve c-set agreement, but not (c-1)-set agreement. The proofs are combinatorial, relying on a novel application of the Nerve Theorem of modern combinatorial topology.
