Title: | Logic and Complexity in Distributed Computing Logiikka ja vaativuus hajautetussa laskennassa |
Author(s): | Lempiäinen, Tuomo |
Date: | 2019 |
Language: | en |
Pages: | 71 + app. 73 |
Department: | Tietotekniikan laitos Department of Computer Science |
ISBN: | 978-952-60-8478-7 (electronic) 978-952-60-8477-0 (printed) |
Series: | Aalto University publication series DOCTORAL DISSERTATIONS, 55/2019 |
ISSN: | 1799-4942 (electronic) 1799-4934 (printed) 1799-4934 (ISSN-L) |
Supervising professor(s): | Suomela, Jukka, Prof., Aalto University, Department of Computer Science, Finland |
Thesis advisor(s): | Suomela, Jukka, Prof., Aalto University, Department of Computer Science, Finland |
Subject: | Computer science |
Keywords: | distributed computing, computational complexity theory, port-numbering model, LOCAL model, graph problems, LCL problems, modal logic, bisimulation, hajautettu laskenta, laskennan vaativuusteoria, porttinumerointimalli, LOCAL-malli, verkko-ongelmat, LCL-ongelmat, modaalilogiikka, bisimulaatio |
Archive | yes |
|
|
Abstract:Tässä väitöskirjassa tutkitaan hajautetun laskennan teoriaa. Hajautetussa tilanteessa laskentaa suorittavat useat itsenäiset laskentayksiköt. Ne kommunikoivat viereisten laskentayksiköiden kanssa ja yhdessä tuottavat ratkaisun johonkin ongelmaan. Tällaisia järjestelmiä esiintyy laajalti niin tietoyhteiskunnassa kuin luonnossakin: hyviä esimerkkejä ovat Internet, usean suorittimen tietokonejärjestelmät, biologisen organismin solut tai vaikkapa ihmisten muodostamat sosiaaliset verkostot. Siksi on tärkeää saada tietoa tällaisten järjestelmien perustavanlaatuisista kyvyistä ja rajoituksista. |
|
Parts:[Publication 1]: Lauri Hella, Matti Järvisalo, Antti Kuusisto, Juhana Laurinharju, Tuomo Lempiäinen, Kerkko Luosto, Jukka Suomela, Jonni Virtema. Weak models of distributed computing, with connections to modal logic. Distributed Computing, 2015, volume 28, issue 1, pp. 31–53. DOI: 10.1007/s00446-013-0202-3 View at Publisher [Publication 2]: Tuomo Lempiäinen. Ability to count messages is worth Θ(Δ) rounds in distributed computing. In Proc. 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2016), New York, NY, USA, pp. 357–366, July 2016. DOI: 10.1145/2933575.2934567 View at Publisher [Publication 3]: Tuomo Lempiäinen, Jukka Suomela. Constant space and non-constant time in distributed computing. In Proc. 21st International Conference on Principles of Distributed Systems (OPODIS 2017), Lisbon, Portugal, pp. 30:1–30:16, March 2018. Full Text in Acris/Aaltodoc: http://urn.fi/URN:NBN:fi:aalto-201812106087. DOI: 10.4230/LIPIcs.OPODIS.2017.30 View at Publisher [Publication 4]: Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, Jukka Suomela. New classes of distributed time complexity. In Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), Los Angeles, CA, USA, pp. 1307–1318, June 2018. DOI: 10.1145/3188745.3188860 View at Publisher |
|
|
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Page content by: Aalto University Learning Centre | Privacy policy of the service | About this site