In this journal paper, we discuss algorithms for multidimensional Byzantine agreement both in synchronous and in asynchronous networks, integrating and refining previous work presented by the authors at STOC and PODC conferences. Co-authored by Hammurabi Mendes, Maurice Herlihy, Nitin Vaidya and Vijay Garg. In Distributed Computing - Download.
We extend the topology-based approach for characterizing computability in asynchronous crash-failure distributed systems to asynchronous Byzantine systems. We give the first theorem with necessary and sufficient conditions to solve arbitrary tasks in asynchronous Byzantine systems. For colorless tasks, an important subclass of distributed problems, the general result reduces to an elegant model that effectively captures the relation between the number of processes and the number of failures, besides the topological structure of the task's simplicial complexes. Appeared at STOC'14 - Download.
In this paper, we integrate the techniques of flat combining, delegation, and elimination into a novel priority queue design, having the scalability of parallel insertions coupled with the efficiency of batched removals. We implement and evaluate our design using a variety of techniques including locking, atomic operations, hardware transactional memory, as well as employing adaptive heuristics given the workload. Appeared at DISC'14 - Download.
The approximate agreement problem in Byzantine asynchronous systems is well-understood when all values lie on the real line. In this paper, we generalize the problem to consider values with multiple dimensions, and present an optimal protocol in regard to fault tolerance. We use some geometric arguments, as Helly's Theorem, to prove the correctness of the protocol. Appeared at STOC'13 - Download.