Multidimensional ϵ-Approximate Agreement and Computability in Byzantine Systems

This talk is divided in two parts. In the first part, we discuss a problem called multidimensional ϵ-approximate agreement, which generalizes the traditional ϵ-approximate agreement of Dolev, Lynch, Pinter, Stark, and Weihl of 1983/1986. Assuming a Byzantine, asynchronous system, we let processes to input values in a space such as Rd with d≥1, and require non-faulty processes to finish with values where:

1. all outputs lie within a distance ϵ of each other; and
2. all outputs are in the convex hull of the non-faulty process inputs.

We see how this problem has implications to distributed computability of colorless tasks, considering our Byzantine, asynchronous setting.

In the second part, we characterize computability in Byzantine, asynchronous systems (but not only with colorless tasks) 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 input complex and output complex defines task semantics. Effectively, outputs of non-faulty processes are constrained only by inputs of non-faulty processes. We see how such task is solvable if and only if a "dual", suitably defined asynchronous, crash-failure task is solvable as well. Since solvability had long been characterized for crash-failure tasks, we have computability conditions under Byzantine failures as well.