Research On Topological Characterizations Of Distributed Computing Theory

With the development of multi-core systems,cloud computing,the Internet of things and other technologies,distributed computation has become a main-stream computing model,and the theory of distributed computing(i.e.computability and complexity)has also become a long-term challenge.Because the FLP theorem,Turing computing theory is not suitable for this computing model,distributed computing is still the current main computing model.As a result,distributed computing theory has become an independent branch of theoretical computer science and has been greatly developed in which topology plays a decisive role.One of the most exciting achievements of distributed computing theory is the introduction of topological theory in more than 30 years,which not only has greatly promoted the development of distributed theory,but also plays a certain role in improving topology itself.Maurice Herlihy won the highest award,Godel Prize,in theoretical computer science for his outstanding contributions to that field.However,by now,the application of topology in distributed computing theory is only limited to specific situations:the solvability of distributed decision tasks in shared-memory,stopping-failure wait-free models,while for more general models and complexity analysis,it is almost blank.This is the starting point for my research topic.In this work,we study the computability and complexity of the asynchronous distributed system based on the topology theory.The main results of this dissertation can be summarized as follows:1.The k-fold chromatic d-join of an arbitrary chromatic simplicial complex is constructed,and then it is showed that the k-fold chromatic d-join of the input complex of a decision task is equivalent to the protocol complex of a full-information protocol in that model for a proper non-negative integer k.In this way,the asynchronous computability theorem of d-solo model is established,that is,a decision task can be solved if and only if there is a simplicial map,which is carried by the task assignment,from the k-fold chromatic d-join of input complex to the output complex.As a result,the solvability of a decision task in the d-solo system is determined completely by the topological characteristics of the k-fold chromatic d-join of input complex and the output complex of the decision task,as well as the relationships between those two complexes.In addition,through the research on the solvability of Input-less tasks in the d-solo model,it gives another concise proof of the relationship,the bigger of the integer d the weaker of the computational power of that model,about the computational power of d-solo models.2.The equivalent classification of the "evolutionary" rendezvous tasks is studied.Evolutionary means that the reduced homology group of the base space of an n-rendezvous task is zero except for that its n dimensional homology group is an abelian group.We show that two evolutionary n-rendezvous tasks are equivalent if and only if there exists a bidirectional homomorphism between their algebraic signatures(i.e.a pair of the n dimensional homology group of the base space and one element of that homology group).Hence the computational power of an evolutionary rendezvous task is completely characterized by its signature.In addition,this work also extends the one dimensional degenerate rendezvous tasks to any dimensional degenerate rendezvous tasks and then gives a classification of those degenerate rendezvous tasks.3.The time complexity of the t-resilient asynchronous distributed system is also studied.we firstly introduce a t-delayed model and construct a reduced complex,and then we prove that the reduced complex is equivalent to the protocol complex of a t-resilient protocol in the tdelayed system,by which the asynchronous complexity theorem is established,that is,the time complexity of a t-resilient protocol with an input complex is equal to the maximum number of the subdivision of some simplex in the input complex.Hence the time complexity of a decision task in t-resilient asynchronous distributed can be characterized by the degree of the subdivision of a simplex in the input complex of the task.Using this topological feature,the tight bound of the time complexity of solvable approximate agreement in the t-resilient asynchronous system is given.