The Experts below are selected from a list of 25371 Experts worldwide ranked by ideXlab platform
Xuezheng Liu - One of the best experts on this subject based on the ideXlab platform.
-
weakening failure detectors for k set agreement via the partition approach
International Symposium on Distributed Computing, 2007Co-Authors: Wei Chen, Jialin Zhang, Yu Chen, Xuezheng LiuAbstract:In this paper, we propose the partition approach and define several new classes of partitioned failure detectors weaker than existing failure detectors for the k-set agreement problem in both the Shared-Memory Model and the message-passing Model. In the Shared-Memory Model with n + 1 processes, for any 2 ≤ k ≤ n, we first propose a partitioned failure detector ΠΩk that solves k-set agreement with Shared read/write registers and is strictly weaker than Ωk, which was conjectured to be the weakest failure detector for k-set agreement in the Shared-Memory Model [19]. We then propose a series of partitioned failure detectors that can solve n-set agreement, yet they are strictly weaker than γ [10], the weakest failure detector ever found before our work to circumvent any asynchronous impossible problems in the Shared-Memory Model. We also define two new families of partitioned failure detectors in the message-passing Model that are strictly weaker than the existing ones for k-set agreement. Our results demonstrate that the partition approach opens a new dimension for weakening failure detectors related to set agreement, and it is an effective approach to check whether a failure detector is the weakest one or not for set agreement. So far, all previous candidates for the weakest failure detectors of set agreement have been disproved by the partitioned failure detectors.
-
partition approach to failure detectors for k set agreement
Principles of Distributed Computing, 2007Co-Authors: Wei Chen, Jialin Zhang, Yu Chen, Xuezheng LiuAbstract:In k-set agreement problem, every process proposes a value and eventually at most k different values can be decided. When k > 1, different subset of processes may decide on different values, and thus it naturally exhibits partition among processes based on their decision values. In this paper, we propose the partition approach to dene failure detectors that capture the partition nature of k-set agreement. The power of the partition approach is to further weaken failure detectors that are already very weak in solving k-set agreement, and thus invalid the failure detectors as candidates for the weakest failure detectors for k-set agreement. Using the approach, we propose two new classes of failure detectors, statically partitioned failure detectors k and splittable partitioned failure detectors S k , both are strong enough to solve k-set agreement in the message passing Model. However, we show that k is strictly weaker than k, the weakest failure detectors known so far for k-set agreement, and S is even weaker than k. The partition approach provides a new dimension to weaken failure detectors related to k-set agreement. It is an effective way to check whether a failure detector is the weakest one solving k-set agreement or not. Together with [4], we show that so far all candidates for the weakest failure detectors including k and in both the message-passing Model and the Shared-Memory Model have failed our partition test.
Petr Kuznetsov - One of the best experts on this subject based on the ideXlab platform.
-
set consensus collections are decidable
International Conference on Principles of Distributed Systems, 2016Co-Authors: Carole Delportegallet, Eli Gafni, Hugues Fauconnier, Petr KuznetsovAbstract:A natural way to measure the power of a distributed-computing Model is to characterize the set of tasks that can be solved in it. In general, however, the question of whether a given task can be solved in a given Model is undecidable, even if we only consider the wait-free Shared-Memory Model. In this paper, we address this question for restricted classes of Models and tasks. We show that the question of whether a collection C of (l, j)-set consensus objects, for various l (the number of processes that can invoke the object) and j (the number of distinct outputs the object returns), can be used by n processes to solve wait-free k-set consensus is decidable. Moreover, we provide a simple O(n^2) decision algorithm, based on a dynamic programming solution to the Knapsack optimization problem. We then present an adaptive wait-free set-consensus algorithm that, for each set of participating processes, achieves the best level of agreement that is possible to achieve using C. Overall, this gives us a complete characterization of a read-write Model defined by a collection of set-consensus objects through its set-consensus power.
-
set consensus collections are decidable
arXiv: Distributed Parallel and Cluster Computing, 2016Co-Authors: Carole Delportegallet, Eli Gafni, Hugues Fauconnier, Petr KuznetsovAbstract:A natural way to measure the power of a distributed-computing Model is to characterize the set of tasks that can be solved in it. %the Model. In general, however, the question of whether a given task can be solved in a given Model is undecidable, even if we only consider the wait-free Shared-Memory Model. In this paper, we address this question for restricted classes of Models and tasks. We show that the question of whether a collection $C$ of \emph{$(\ell,j)$-set consensus} objects, for various $\ell$ (the number of processes that can invoke the object) and $j$ (the number of distinct outputs the object returns), can be used by $n$ processes to solve wait-free $k$-set consensus is decidable. Moreover, we provide a simple $O(n^2)$ decision algorithm, based on a dynamic programming solution to the Knapsack optimization problem. We then present an \emph{adaptive} wait-free set-consensus algorithm that, for each set of participating processes, achieves the best level of agreement that is possible to achieve using $C$. Overall, this gives us a complete characterization of a read-write Model defined by a collection of set-consensus objects through its \emph{set-consensus power}.
Mark D Hill - One of the best experts on this subject based on the ideXlab platform.
-
a unified formalization of four Shared Memory Models
IEEE Transactions on Parallel and Distributed Systems, 1993Co-Authors: Mark D HillAbstract:The authors present a data-race-free-1, Shared-Memory Model that unifies four earlier Models: weak ordering, release consistency (with sequentially consistent special operations), the VAX Memory Model, and data-race-free-0. Data-race-free-1 unifies the Models of weak ordering, release consistency, the VAX, and data-race-free-0 by formalizing the intuition that if programs synchronize explicitly and correctly, then sequential consistency can be guaranteed with high performance in a manner that retains the advantages of each of the four Models. Data-race-free-1 expresses the programmer's interface more explicitly and formally than weak ordering and the VAX, and allows an implementation not allowed by weak ordering, release consistency, or data-race-free-0. The implementation proposal for data-race-free-1 differs from earlier implementations by permitting the execution of all synchronization operations of a processor even while previous data operations of the processor are in progress. To ensure sequential consistency, two sychronizing processors exchange information to delay later operations of the second processor that conflict with an incomplete data operation of the first processor. >
Wei Chen - One of the best experts on this subject based on the ideXlab platform.
-
weakening failure detectors for k set agreement via the partition approach
International Symposium on Distributed Computing, 2007Co-Authors: Wei Chen, Jialin Zhang, Yu Chen, Xuezheng LiuAbstract:In this paper, we propose the partition approach and define several new classes of partitioned failure detectors weaker than existing failure detectors for the k-set agreement problem in both the Shared-Memory Model and the message-passing Model. In the Shared-Memory Model with n + 1 processes, for any 2 ≤ k ≤ n, we first propose a partitioned failure detector ΠΩk that solves k-set agreement with Shared read/write registers and is strictly weaker than Ωk, which was conjectured to be the weakest failure detector for k-set agreement in the Shared-Memory Model [19]. We then propose a series of partitioned failure detectors that can solve n-set agreement, yet they are strictly weaker than γ [10], the weakest failure detector ever found before our work to circumvent any asynchronous impossible problems in the Shared-Memory Model. We also define two new families of partitioned failure detectors in the message-passing Model that are strictly weaker than the existing ones for k-set agreement. Our results demonstrate that the partition approach opens a new dimension for weakening failure detectors related to set agreement, and it is an effective approach to check whether a failure detector is the weakest one or not for set agreement. So far, all previous candidates for the weakest failure detectors of set agreement have been disproved by the partitioned failure detectors.
-
partition approach to failure detectors for k set agreement
Principles of Distributed Computing, 2007Co-Authors: Wei Chen, Jialin Zhang, Yu Chen, Xuezheng LiuAbstract:In k-set agreement problem, every process proposes a value and eventually at most k different values can be decided. When k > 1, different subset of processes may decide on different values, and thus it naturally exhibits partition among processes based on their decision values. In this paper, we propose the partition approach to dene failure detectors that capture the partition nature of k-set agreement. The power of the partition approach is to further weaken failure detectors that are already very weak in solving k-set agreement, and thus invalid the failure detectors as candidates for the weakest failure detectors for k-set agreement. Using the approach, we propose two new classes of failure detectors, statically partitioned failure detectors k and splittable partitioned failure detectors S k , both are strong enough to solve k-set agreement in the message passing Model. However, we show that k is strictly weaker than k, the weakest failure detectors known so far for k-set agreement, and S is even weaker than k. The partition approach provides a new dimension to weaken failure detectors related to k-set agreement. It is an effective way to check whether a failure detector is the weakest one solving k-set agreement or not. Together with [4], we show that so far all candidates for the weakest failure detectors including k and in both the message-passing Model and the Shared-Memory Model have failed our partition test.
Nacho Navarro - One of the best experts on this subject based on the ideXlab platform.
-
an asymmetric distributed Shared Memory Model for heterogeneous parallel systems
Architectural Support for Programming Languages and Operating Systems, 2010Co-Authors: Isaac Gelado, John E Stone, Javier Cabezas, Sanjay J Patel, Nacho NavarroAbstract:Heterogeneous computing combines general purpose CPUs with accelerators to efficiently execute both sequential control-intensive and data-parallel phases of applications. Existing programming Models for heterogeneous computing rely on programmers to explicitly manage data transfers between the CPU system Memory and accelerator Memory. This paper presents a new programming Model for heterogeneous computing, called Asymmetric Distributed Shared Memory (ADSM), that maintains a Shared logical Memory space for CPUs to access objects in the accelerator physical Memory but not vice versa. The asymmetry allows light-weight implementations that avoid common pitfalls of symmetrical distributed Shared Memory systems. ADSM allows programmers to assign data objects to performance critical methods. When a method is selected for accelerator execution, its associated data objects are allocated within the Shared logical Memory space, which is hosted in the accelerator physical Memory and transparently accessible by the methods executed on CPUs. We argue that ADSM reduces programming efforts for heterogeneous computing systems and enhances application portability. We present a software implementation of ADSM, called GMAC, on top of CUDA in a GNU/Linux environment. We show that applications written in ADSM and running on top of GMAC achieve performance comparable to their counterparts using programmer-managed data transfers. This paper presents the GMAC system and evaluates different design choices. We further suggest additional architectural support that will likely allow GMAC to achieve higher application performance than the current CUDA Model.