A Topological Characterization to Arbitrary Resilient Asynchronous Complexity

Abstract

In this work, we extend the topology-based framework and method for the quantification and classification of general resilient asynchronous complexity. We present the arbitrary resilient asynchronous complexity theorem, applied to decision tasks in an iterated delayed model which is based on a series of communicating objects, each of which mainly consists of the delayed algorithm. In order to do this, we first introduce two topological structures, delayed complex and reduced delayed complex, and build the topological computability model, and then investigate some properties of those structures and the computing power of that model. Our theorem states that the time complexity of any arbitrary resilient asynchronous algorithm is proportional to the level of a reduced delayed complex necessary to allow a simplicial map from a task’s input complex to its output complex. As an application, we use it to derive the bounds on time complexity to approximate agreement with n+1 processes.

Keywords

• distributed computation
• asynchronous computation
• combinatorial topology
• computability
• complexity
• resilience