# Logic and Complexity in Distributed Computing

Tutkimustuotos ›

### Standard

**Logic and Complexity in Distributed Computing.** / Lempiäinen, Tuomo.

Tutkimustuotos ›

### Harvard

### APA

*Logic and Complexity in Distributed Computing*. Aalto University.

### Vancouver

### Author

### Bibtex - Lataa

}

### RIS - Lataa

TY - THES

T1 - Logic and Complexity in Distributed Computing

AU - Lempiäinen, Tuomo

PY - 2019

Y1 - 2019

N2 - This dissertation studies the theory of distributed computing. In the distributed setting, computation is carried out by multiple independent computational units. They communicate with neighbouring units and collectively solve a problem. Systems of this kind are widespread in the information society as well as in the natural world: prime examples include the Internet, multi-processor computer systems, the cells of a biological organism and human social networks. Therefore it is important to gain knowledge on the fundamental capabilities and limitations of distributed systems. Our work takes place in the context of deterministic and synchronous message-passing models of distributed computing. Such models abstract away some possible features of distributed systems, such as asynchrony, congestion and faults, while putting emphasis on the amount of communication needed between the units. The computational units are expected to solve a problem related to the structure of the underlying communication network. More specifically, we study the standard LOCAL model, the standard port-numbering model and several weaker variants of the latter. The contributions of this dissertation are two-fold. First, we give new methods for studying distributed computing by establishing a strong connection between several weak variants of the port-numbering model and corresponding variants of modal logic. This makes it possible to apply existing logical tools, such as bisimulation, to understand computation in the distributed setting. We also give a full characterisation of the relationships between the models of computing, which has implications on the side of mathematical logic. Second, we prove the existence of various new non-empty complexity classes. One of our results studies the relationship between time and space complexity, which is a relatively new topic in distributed computing research. We demonstrate the existence of a problem that can be solved in a constant amount of space in a very weak model but nonetheless requires a non-constant amount of time even in a much stronger model of computing. Another result continues the recent success on developing complexity theory for the LOCAL model. We introduce a new technique which shows the existence of an infinite hierarchy of problems with novel time complexities.

AB - This dissertation studies the theory of distributed computing. In the distributed setting, computation is carried out by multiple independent computational units. They communicate with neighbouring units and collectively solve a problem. Systems of this kind are widespread in the information society as well as in the natural world: prime examples include the Internet, multi-processor computer systems, the cells of a biological organism and human social networks. Therefore it is important to gain knowledge on the fundamental capabilities and limitations of distributed systems. Our work takes place in the context of deterministic and synchronous message-passing models of distributed computing. Such models abstract away some possible features of distributed systems, such as asynchrony, congestion and faults, while putting emphasis on the amount of communication needed between the units. The computational units are expected to solve a problem related to the structure of the underlying communication network. More specifically, we study the standard LOCAL model, the standard port-numbering model and several weaker variants of the latter. The contributions of this dissertation are two-fold. First, we give new methods for studying distributed computing by establishing a strong connection between several weak variants of the port-numbering model and corresponding variants of modal logic. This makes it possible to apply existing logical tools, such as bisimulation, to understand computation in the distributed setting. We also give a full characterisation of the relationships between the models of computing, which has implications on the side of mathematical logic. Second, we prove the existence of various new non-empty complexity classes. One of our results studies the relationship between time and space complexity, which is a relatively new topic in distributed computing research. We demonstrate the existence of a problem that can be solved in a constant amount of space in a very weak model but nonetheless requires a non-constant amount of time even in a much stronger model of computing. Another result continues the recent success on developing complexity theory for the LOCAL model. We introduce a new technique which shows the existence of an infinite hierarchy of problems with novel time complexities.

KW - distributed computing

KW - computational complexity theory

KW - port-numbering model

KW - LOCAL model

KW - graph problems

KW - LCL problems

KW - modal logic

KW - bisimulation

KW - hajautettu laskenta

KW - laskennan vaativuusteoria

KW - porttinumerointimalli

KW - LOCAL-malli

KW - verkko-ongelmat

KW - LCL-ongelmat

KW - modaalilogiikka

KW - bisimulaatio

KW - distributed computing

KW - computational complexity theory

KW - port-numbering model

KW - LOCAL model

KW - graph problems

KW - LCL problems

KW - modal logic

KW - bisimulation

M3 - Doctoral Thesis

SN - 978-952-60-8477-0

T3 - Aalto University publication series DOCTORAL DISSERTATIONS

PB - Aalto University

ER -

ID: 33310579