Title: | Lower bounds in distributed computing Lower bounds in distributed computing |
Author(s): | Hirvonen, Juho |
Date: | 2016 |
Language: | en |
Pages: | 75 + app. 81 |
Department: | Tietotekniikan laitos Department of Computer Science |
ISBN: | 978-952-60-7137-4 (electronic) 978-952-60-7138-1 (printed) |
Series: | Aalto University publication series DOCTORAL DISSERTATIONS, 239/2016 |
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, local algorithms, lower bounds, hajautettu laskenta, paikalliset algoritmit, alarajat |
Archive | yes |
|
|
Abstract:Tutkin tässä väitöskirjatyössä hajautetun laskennan vaativuusteoriaa synkronisissa viestinvälitysmalleissa. Työ keskittyy paikallisiin ongelmiin, eli ongelmiin, joiden ratkaisu voidaan löytää käyttäen vain vähäinen määrä kommunikaatiota. Tutkitussa asetelmassa kommunikaatioverkko on myös ongelman syöte. Hajautetun järjestelmän täytyy löytää ratkaisu, joka liittyy tämän verkon rakenteeseen ja jokaisen verkon solmun täytyy tuottaa oma osansa tulosteesta. |
|
Parts:[Publication 1]: Juho Hirvonen and Jukka Suomela. Distributed maximal matching: greedy is optimal. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (PODC 2012), Funchal, Portugal, pages 165–174, July 2012. DOI: 10.1145/2332432.2332464 View at Publisher [Publication 2]: Pierre Fraigniaud, Juho Hirvonen, and Jukka Suomela. Node labels in local decision. Proceedings of the 22nd International Colloquim on Structural Information and Communication Complexity (SIROCCO 2015), Montserrat, Spain, pages 31–45, July 2015. DOI: 10.1007/978-3-319-25258-2_3 View at Publisher [Publication 3]: Laurent Feuilloley, Pierre Fraigniaud, and Juho Hirvonen. A hierarchy of local decision. Accepted for publication in Proceedings of the 43rd International Colloquim on Automata, Languages, and Programming (ICALP 2016), July 2016[Publication 4]: Henning Hasemann, Juho Hirvonen, Joel Rybicki, and Jukka Suomela. Deterministic local algorithms, unique identifiers, and fractional graph colouring. Theoretical Computer Science, Volume 610, part B, 11, pages 204–217, January 2016. DOI:10.1016/j.tcs.2014.06.044 View at Publisher [Publication 5]: Mika Göös, Juho Hirvonen, and Jukka Suomela. Linear-in-lower bounds in the LOCAL model. Accepted for publication in Distributed Computing, 2016. DOI: 10.1145/2611462.2611467 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