A Topological Characterization to Arbitrary Resilient Asynchronous Complexity

Yunguang Yue, Xingwu Liu, Fengchun Lei and Jie Wu
Additional contact information
Yunguang Yue: School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China
Xingwu Liu: School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China
Fengchun Lei: School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China
Jie Wu: Yanqi Lake Beijing Institute of Mathematical Sciences and Applications, Beijing 101408, China

Mathematics, 2022, vol. 10, issue 15, 1-20

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; task-solvability (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/15/2720/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/15/2720/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:15:p:2720-:d:877853

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().