The price of anonymity: optimal consensus despite asynchrony, crash and anonymity

摘要: This paper addresses the consensus problem in asynchronous systems prone to process crashes, where additionally processes are anonymous (they cannot be distinguished one from other: they have no name and execute same code). To circumvent three computational adversaries (asynchrony, failures anonymity) each is provided with a failure detector of class denoted ψ, that gives it an upper bound on number currently alive (in non-anonymous system, classes ψ P -the perfect detectors- equivalent). The first presents simple ψ-based algorithm decide 2t + 1 rounds (where t faulty processes). It then shows its main results, namely, lower for equipped ψ. The second contribution early-decision. proves correct early-deciding min(2f 2, 1) f actual failures). leads think anonymity doubles cost (wrt synchronous systems) conjectured min (2f corresponding bound. The finally considers k-set agreement systems. previous solves Rt = 2 ⌊t/k⌋ rounds. Then, considering family {ψl}0≤l