{'fraction_non_alphanumeric': 0.03137951450562463, 'fraction_numerical': 0.0, 'mean_word_length': 5.101083032490974, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, '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}}
Modular randomized byzantine k-set agreement in asynchronous message-passing systems

k-Set agreement is a central problem of fault-tolerant distributed computing. Considering a set of n processes, where up to t may commit failures, let us assume that each process proposes a value. The problem consists in defining an algorithm such that each non-faulty process decides a value, at most k different values are decided, and the decided values satisfy some context-depending validity condition. Synchronous message-passing algorithms solving k-set agreement have been proposed for different failure models (mainly process crashes, and process Byzantine failures). Differently, k-set agreement cannot be solved in failure-prone asynchronous message-passing systems when t ≥ k. To circumvent this impossibility an asynchronous system must be enriched with additional computational power. Assuming t ≥ k, this paper presents a distributed algorithm that solves k-set agreement in an asynchronous message-passing system where up to t processes may commit Byzantine failures. To that end, each process is enriched with randomization power. While randomized k-set agreement algorithms exist for the asynchronous process crash failure model where t ≥ k, to our knowledge the proposed algorithm is the first that solves k-set agreement in the presence of up to t ≥ k Byzantine processes. Interestingly, this algorithm is signature-free, and ensures that no value proposed only by Byzantine processes can be decided by a non-faulty process. Its design is based on a modular construction which rests on a "no-duplicity" one-to-all broadcast abstraction, and two all-to-all communication abstractions.