{'fraction_non_alphanumeric': 0.0512, 'fraction_numerical': 0.0064, 'mean_word_length': 4.535398230088496, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multidimensional approximate agreement in Byzantine asynchronous systems

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 Rm, for m ≥ 1, and present an optimal protocol in regard to fault tolerance. Our scenario is the following. Processes start with values in Rm, 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 Rm; (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 Rm. Non-faulty processes send O(n2 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.