Arrow Research search

Author name cluster

Hammurabi Mendes

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

STOC Conference 2014 Conference Paper

Distributed computability in Byzantine asynchronous systems

  • Hammurabi Mendes
  • Christine Tasson
  • Maurice Herlihy

In this work, 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 where an adversary chooses faulty processes. 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, the number of failures, as well as the topological structure of the task's simplicial complexes.

Details

STOC Conference 2013 Conference Paper

Multidimensional approximate agreement in Byzantine asynchronous systems

  • Hammurabi Mendes
  • Maurice Herlihy

The problem of ε-approximate agreement 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 that lie in R m , for m ≥ 1, and present an optimal protocol in regard to fault tolerance. Our scenario is the following. Processes start with values in R m , for m ≥ 1, and communicate via message-passing. The system is asynchronous : there is no upper bound on processes' relative speeds or on message delay. Some faulty processes can display arbitrarily malicious (i.e. Byzantine) behavior. Non-faulty processes must decide on values that are: (1) in R m ; (2) within distance ε of each other; and (3) in the convex hull of the non-faulty processes' inputs. We give an algorithm with a matching lower bound on fault tolerance: we require n > t(m+2), where n is the number of processes, t is the number of Byzantine processes, and input and output values reside in R m . Non-faulty processes send O(n 2 d log(m/ε max{δ(d): 1 ≤ d ≤ m})) messages in total, where δ(d) is the range of non-faulty inputs projected at coordinate d. The Byzantine processes do not affect the algorithm's running time.

Details
v2026.09.13