Consider a distributed system with @math processors out of which @math can be Byzantine faulty. In the approximate agreement task, each processor @math receives an input value @math and has to decide on an output value @math such that - the output values are in the convex hull of the non-faulty processors' input values, - the output values are within distance @math of each other. Classically, the values are assumed to be from an @math -dimensional Euclidean space, where @math . In this work, we study the task in a discrete setting, where input values with some structure expressible as a graph. Namely, the input values are vertices of a finite graph @math and the goal is to output vertices that are within distance @math of each other in @math , but still remain in the graph-induced convex hull of the input values. For @math , the task reduces to consensus and cannot be solved with a deterministic algorithm in an asynchronous system even with a single crash fault. For any @math , we show that the task is solvable in asynchronous systems when @math is chordal and @math , where @math is the clique number of @math . In addition, we give the first Byzantine-tolerant algorithm for a variant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact variants of these and related tasks over a large class of combinatorial structures.
Objects like queue, swap, and test-and-set allow two processes to reach consensus, and are consequently "universal" for a system of two processes. But are there deterministic objects that do not solve 2-process consensus, and nevertheless allow two processes to solve a task that is not otherwise wait-free solvable in read-write shared memory? The answer "no" is a simple corollary of the main result of this paper: Let A be a deterministic object such that no protocol solves consensus among n+1 processes using copies of A and read-write registers. If a task T is wait-free solvable by n + 1 processes using read-write shared-memory and copies of A, then T is also wait-free solvable when copies of A are replaced with n-consensus objects. Thus, from the task-solvability perspective, n-consensus is the second strongest object (after (n+1)-consensus) in deterministic shared memory systems of n+1 processes, i.e., there is a distinct gap between n- and (n + 1)-consens. We derive this result by showing that any (n+1)-process protocol P that uses objects A can be emulated using only n-consensus objects. The resulting emulation is non-blocking and relies on an a priori knowledge of P. The emulation technique is another important contribution of this paper. Distributed Computing Through Combinatorial Topology describes techniques for analyzing distributed algorithms based on award winning combinatorial topology research. The authors present a solid theoretical foundation relevant to many real systems reliant on parallelism with unpredictable delays, such as multicore microprocessors, wireless networks, distributed systems, and Internet protocols. Today, a new student or researcher must assemble a collection of scattered conference publications, which are typically terse and commonly use different notations and terminologies. This book provides a self-contained explanation of the mathematics to readers with computer science backgrounds, as well as explaining computer science concepts to readers with backgrounds in applied mathematics. The first section presents mathematical notions and models, including message passing and shared-memory systems, failures, and timing models. The next section presents core concepts in two chapters each: first, proving a simple result that lends itself to examples and pictures that will build up readers' intuition; then generalizing the concept to prove a more sophisticated result. The overall result weaves together and develops the basic concepts of the field, presenting them in a gradual and intuitively appealing way. The book's final section discusses advanced topics typically found in a graduate-level course for those who wish to explore further. Gathers knowledge otherwise spread across research and conference papers using consistent notations and a standard approach to facilitate understandingPresents unique insights applicable to multiple computing fields, including multicore microprocessors, wireless networks, distributed systems, and Internet protocols Synthesizes and distills material into a simple, unified presentation with examples, illustrations, and exercises Loop agreement is a family of wait-free tasks that includes instances of set agreement and approximate agreement tasks. A task G implements task F if one can construct a solution to F from a solution to G, possibly followed by access to a read write memory. Loop agreement tasks form a lattice under this notion of implementation.This paper presents a classification of loop agreement tasks. Each loop agreement task can be assigned an algebraic signature consisting of a finitely presented group G and a distinguished element g in G. This signature characterizes the task's power to implement other tasks. If F and G are loop agreement tasks with respective signatures 〈F,f〉 and 〈G,g〉, then F implements G if and only if there exists a group homomorphism h : F → G carrying f to g. The rendezvous is a type of distributed decision tasks including many well-known tasks such as set agreement, simplex agreement, and approximation agreement. An n-dimensional rendezvous task, n>=1, allows n+2 distinct input values, and each execution produces at most n+2 distinct output values. A rendezvous task is said to implement another if an instance of its solution, followed by a protocol based on shared read write registers, solves the other. The notion of implementation induces a classification of rendezvous tasks of every dimension: two tasks belong to the same class if they implement each other. Previous work on classifying rendezvous tasks only focused on 1-dimensional ones. This paper solves an open problem by presenting the classification of nice rendezvous of arbitrary dimension. An n-dimensional rendezvous task is said to be nice if the qth reduced homology group of its decision space is trivial for q n, and free for q=n. Well-known examples are set agreement, simplex agreement, and approximation agreement. Each n-dimensional rendezvous task is assigned an algebraic signature, which consists of the nth homology group of the decision space, as well as a distinguished element in the group. It is shown that an n-dimensional nice rendezvous task implements another if and only if there is a homomorphism from its signature to that of the other. Hence the computational power of a nice rendezvous task is completely characterized by its signature. In each dimension, there are infinitely many classes of rendezvous tasks, and exactly countable classes of nice ones. A representative is explicitly constructed for each class of nice rendezvous tasks.