CS Talk
Speaker: Hammurabi Mendes, Brown University
Title: Multidimensional ε-Approximate Agreement and Computability in Byzantine Systems
Abstract: This talk is divided in two parts. In the first part, we discuss a problem called multidimensional ε-approximate agreement.
Consider a distributed system with asynchronous communication and Byzantine (i.e., arbitrary) failures. Each process inputs a value in R^d with d ≥ 1, and all non-faulty processes must finish with values where: (1) outputs lie within a distance ε of each other; and (2) outputs are in the convex hull of non-faulty process inputs. This problem generalizes the traditional ε-approximate agreement of 1983/1986, and has implications to computability for more general Byzantine tasks.
In the second part, we characterize computability in Byzantine, asynchronous systems by using tools adapted from combinatorial topology. Tasks are formalized with a pair of combinatorial structures called simplicial complexes, one for non-faulty process inputs (the input complex), and another for non-faulty process outputs (the output complex). A map between the input complex and the output complex defines task semantics. We see how a Byzantine asynchronous task is solvable if and only if a “dual” asynchronous, crash-failure task is solvable as well. We are then able to characterize computability for Byzantine asynchronous tasks with a concise, topology-based language.