PODC 2019 Review
Abstract
The 38th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2019) was held on July 29-August 2, 2019 at the Double Tree Hilton hotel in Toronto, Canada. With three keynotes, over 40 accepted papers, over 20 accepted brief announcements, two workshops, and roughly 150 attendants, PODC 2019 constituted a composition of fascinating improvements in many areas of distributed and parallel computing.
On the evening of the 31st of July, the conference banquet was held on a cruise over beautiful Lake Ontario and included the best papers award ceremony. The best paper award went to Yi-Jun Chang, and Thatchaphol Saranurak for their work titled, \Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration" [19]; two best student paper awards were given to Yi-Jun Chang, Manuela Fischer, and Yufan Zheng for their work titled, \The Complexity of (Δ + 1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation" [17] which was co-authored with Mohsen Gha ari, and Jara Uitto, and to Michal Dory and Dean Leitersdorf for the work on \Fast Approximate Shortest Paths in the Congested Clique" [16] which was co-authored with Keren Censor-Hillel, and Janne H. Korhonen. Congratulations to all the awardees and a special congratulations to Yi-Jun Chang for having received both awards!
This review would be incomplete without mentioning perhaps one of the most notable results in the eld in recent years which was uploaded to the online archive just days before the conference gathered, and which was not presented at PODC 2019 but a ected many works presented at the conference: the work titled, ¶olylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization" [48] by Vaclav Rozhon, and Mohsen Gha ari. Throughout the entire conference there was talk regarding the implications of this work, culminating with perhaps one of the more memorable moments of PODC 2019, where Mohsen described this result during his talk on a di erent paper which he co-authored with Fabian Kuhn - Mohsen quoted from his and Kuhn's paper [31]: \we provide results that are in some sense the strongest that one can achieve, barring a major breakthrough", and on the next slide was that major breakthrough - a picture of Vaclav Rozhon along with the rst page of [48]. Congratulations to the authors on this work!
We hope that this review will give readers the opportunity to experience some of PODC 2019 and potentially attend the conference in future years. Thank you to the organizers and authors for a captivating and though-provoking conference!
References
[1]
Ittai Abraham, TH Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Communication complexity of byzantine agreement, revisited. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 317{326. ACM, 2019.
[2]
Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. Asymptotically optimal validated asynchronous byzantine agreement. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 337{346. ACM, 2019.
[3]
Abhinav Aggarwal, G. Matthew Fricke, Diksha Gupta, and Melanie E. Moses. On site delity and the price of ignorance in swarm robotic central place foraging algorithms. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 63{65, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331572.
[4]
Zahra Aghazadeh, Damien Imbs, Michel Raynal, Gadi Taubenfeld, and Philipp Woelfel. Optimal memory-anonymous symmetric deadlock-free mutual exclusion. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 157{166, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331594.
[5]
Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Virendra Marathe, and Igor Zablotchi. The impact of rdma on agreement. In Proceedings of the 2019 ACM Sympo- sium on Principles of Distributed Computing, PODC '19, pages 409{418, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331601. 3293611.3331601.
[6]
Sepehr Assadi, Xiaorui Sun, and OmriWeinstein. Massively parallel algorithms for nding wellconnected components in sparse graphs. In Proceedings of the 2019 ACM Symposium on Prin- ciples of Distributed Computing, PODC '19, pages 461{470, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331596.
[7]
Nir Bacrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf, and Ami Paz. Hardness of distributed optimization. In Proceedings of the 2019 ACM Symposium on Princi- ples of Distributed Computing, PODC '19, pages 238{247, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331597.
[8]
Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikael Rabie, and Jukka Suomela. Lower bounds for maximal matchings and maximal independent sets. CoRR, abs/1901.02441, 2019.
[9]
Alkida Balliu, Juho Hirvonen, Dennis Olivetti, and Jukka Suomela. Hardness of minimal symmetry breaking in distributed computing. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019., pages 369{378, 2019.
[10]
Philipp Bamberger, Mohsen Gha ari, Fabian Kuhn, Yannic Maus, and Jara Uitto. On the complexity of distributed splitting problems. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019., pages 280{289, 2019.
[11]
Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M. Karp, and Jara Uitto. Massively parallel computation of matching and mis in sparse graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 481{490, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331609.
[12]
Petra Berenbrink, Dominik Kaaser, and Tomasz Radzik. On counting the population size. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 43{52, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/ 3293611.3331631.
[13]
Greg Bodwin and Shyamal Patel. A trivial yet optimal solution to vertex fault tolerant spanners. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019., pages 541{543, 2019.
[14]
Sebastian Brandt. An automatic speedup theorem for distributed problems. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019., pages 379{388, 2019.
[15]
Manuel Bravo and Alexey Gotsman. Recon gurable atomic transaction commit. In Proceed- ings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 399{408, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611. 3331590.
[16]
Keren Censor-Hillel, Michal Dory, Janne H. Korhonen, and Dean Leitersdorf. Fast approximate shortest paths in the congested clique. In Proceedings of the 2019 ACM Symposium on Prin- ciples of Distributed Computing, PODC '19, pages 74{83, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331633.
[17]
Yi-Jun Chang, Manuela Fischer, Mohsen Gha ari, Jara Uitto, and Yufan Zheng. The complexity of (Delta+1) coloring in congested clique, massively parallel computation, and centralized local computation. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 471{480, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331607.
[18]
Yi-Jun Chang, Seth Pettie, and Hengjie Zhang. Distributed triangle detection via expander decomposition. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6--9, 2019, pages 821{840, 2019. URL: https://doi.org/10.1137/1.9781611975482.51. 9781611975482.51.
[19]
Yi-Jun Chang and Thatchaphol Saranurak. Improved distributed expander decomposition and nearly optimal triangle enumeration. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 66{73, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331618.
[20]
Hsueh-Ping Chen and Ho-Lin Chen. Self-stabilizing leader election. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 53{59, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331616.
[21]
Lijie Chen and Ofer Grossman. Broadcast congested clique: Planted cliques and pseudorandom generators. In Proceedings of the 2019 ACM Symposium on Principles of Dis- tributed Computing, PODC '19, pages 248{255, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331599.
[22]
Jurek Czyzowicz, Leszek Gasieniec, Ryan Killick, and Evangelos Kranakis. Symmetry breaking in the plane: Rendezvous by robots with unknown attributes. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 4{13, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331608. 3293611.3331608.
[23]
Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak. Distributed edge connectivity in sublinear time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23- 26, 2019., pages 343{354, 2019. URL: https://doi.org/10.1145/3313276.3316346.
[24]
Michael Dinitz, Magn--us M. Halld--orsson, Taisuke Izumi, and Calvin Newport. Distributed minimum degree spanning trees. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019., pages 511{520, 2019.
[25]
Michal Dory and Mohsen Gha ari. Improved distributed approximations for minimum-weight two-edge-connected spanning subgraph. In Proceedings of the 2019 ACM Symposium on Prin- ciples of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019., pages 521{530, 2019.
[26]
David Doty and Mahsa Eftekhari. Efficient size estimation and impossibility of termination in uniform dense population protocols. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 34{42, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331627.
[27]
Michael Elkin, Hartmut Klauck, Danupon Nanongkai, and Gopal Pandurangan. Can quantum communication speed up distributed computation? In Proceedings of the 2014 ACM Sympo- sium on Principles of Distributed Computing, PODC '14, pages 166{175, New York, NY, USA, 2014. ACM. URL: http://doi.acm.org/10.1145/2611462.2611488. 2611462.2611488.
[28]
Michael Elkin and Shaked Matar. Near-additive spanners in low polynomial deterministic CONGEST time. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019., pages 531{540, 2019.
[29]
Francois Le Gall, Harumichi Nishimura, and Ansis Rosmanis. Quantum Advantage for the LOCAL Model in Distributed Computing. In Rolf Niedermeier and Christophe Paul, editors, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), volume 126 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1{49:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl{Leibniz-Zentrum fuer Informatik. URL: http:// drops.dagstuhl.de/opus/volltexte/2019/10288.
[30]
Buddhima Gamlath, Sagar Kale, Slobodan Mitrovic, and Ola Svensson. Weighted matchings via unweighted augmentations. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 491{500, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331603.
[31]
Mohsen Gha ari and Fabian Kuhn. On the use of randomness in local distributed graph algorithms. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019., pages 290{299, 2019.
[32]
George Giakkoupis, Frederik Mallmann-Trenn, and Hayk Saribekyan. How to spread a rumor: Call your neighbors or take a walk? In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 24{33, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331622.
[33]
Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, and Dragos-Adrian Seredinschi. The consensus number of a cryptocurrency. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 307{316. ACM, 2019.
[34]
Magnus M. Halldorsson and Tigran Tonoyan. Plain sinr is enough! In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 127{136, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331602.
[35]
Taisuke Izumi and Francois Le Gall. Quantum distributed algorithm for the all-pairs shortest path problem in the congest-clique model. In Proceedings of the 2019 ACM Sympo- sium on Principles of Distributed Computing, PODC '19, pages 84{93, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331628. 3293611.3331628.
[36]
Prasad Jayanti and Siddhartha Jayanti. Constant amortized rmr abortable mutex for cc and dsm. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 167{176, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/ 10.1145/3293611.3331592.
[37]
Prasad Jayanti, Siddhartha Jayanti, and Anup Joshi. A recoverable mutex algorithm with sublogarithmic rmr on both cc and dsm. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 177{186, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331634.
[38]
Siddhartha Jayanti, Robert E. Tarjan, and Enric Boix-Adsera. Randomized concurrent set union and generalized wake-up. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 187{196, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331593.
[39]
Muhammad Samir Khan, Syed Shalan Naqvi, and Nitin H. Vaidya. Exact byzantine consensus on undirected graphs under local broadcast model. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 327{336, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331619.
[40]
Kunal Korgaonkar, Joseph Izraelevitz, Jishen Zhao, and Steven Swanson. Vorpal: Vector clock ordering for large persistent memory systems. In Proceedings of the 2019 ACM Sym- posium on Principles of Distributed Computing, PODC '19, pages 435{444, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331598. 3293611.3331598.
[41]
Adrian Kosowski, Przemyslaw Uznanski, and Laurent Viennot. Hardness of exact distance queries in sparse graphs through hub labeling. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019., pages 272{279, 2019.
[42]
Francois Le Gall and Frederic Magniez. Sublinear-time quantum computation of the diameter in congest networks. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC '18, pages 337{346, New York, NY, USA, 2018. ACM. URL: http://doi. acm.org/10.1145/3212734.3212744.
[43]
Avery Miller, Boaz Patt-Shamir, and Will Rosenbaum. With great speed come small bu ers: Space-bandwidth tradeo s for routing. In Proceedings of the 2019 ACM Symposium on Prin- ciples of Distributed Computing, PODC '19, pages 117{126, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331614.
[44]
Ruslan Nikolaev and Binoy Ravindran. Hyaline: fast and transparent lock-free memory reclamation. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 419{421, New York, NY, USA, 2019. ACM. URL: http: //doi.acm.org/10.1145/3293611.3331575.
[45]
Sean Ovens and Philipp Woelfel. Strongly linearizable implementations of snapshots and other types. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 197{206, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/ 10.1145/3293611.3331632.
[46]
Merav Parter and Eylon Yogev. Distributed algorithms made secure: A graph theoretic approach. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algo- rithms, SODA '19, pages 1693{1710, Philadelphia, PA, USA, 2019. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3310435.3310537.
[47]
Merav Parter and Eylon Yogev. Secure distributed computing made (nearly) optimal. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 107{116, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/ 3293611.3331620.
[48]
V--aclav Rozhon and Mohsen Gha ari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. CoRR, abs/1907.10937, 2019.
[49]
Ilya Sergey. Engineering distributed systems that we can trust (and also run). In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 306{306, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3338839.
[50]
Eric E. Severson, David Haley, and David Doty. Composable computation in discrete chemical reaction networks. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 14{23, New York, NY, USA, 2019. ACM. URL: http://doi. acm.org/10.1145/3293611.3331615.
[51]
Yuichi Sudo, Fukuhito Ooshita, Taisuke Izumi, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Logarithmic expected-time leader election in population protocol model. In Proceed- ings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 60{62, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611. 3331585.
[52]
Samuel Thomas and Hammurabi Mendes. Layering data structures over skip graphs for increased numa locality. In Proceedings of the 2019 ACM Symposium on Principles of Dis- tributed Computing, PODC '19, pages 422{424, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331576.
[53]
Zhaoguo Wang, Changgeng Zhao, Shuai Mu, Haibo Chen, and Jinyang Li. On the parallels between paxos and raft, and how to port optimizations. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 445{454, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331595. 1145/3293611.3331595.
[54]
Zhuolun Xiang and Nitin H. Vaidya. Partially replicated causally consistent shared memory: Lower bounds and an algorithm. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC '19, pages 425{434, New York, NY, USA, 2019. ACM. URL: http://doi.acm.org/10.1145/3293611.3331600.
[55]
Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gueta, and Ittai Abraham. Hotstu : Bft consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 347{356. ACM, 2019.
Recommendations
PODC 2020 Review
Rachid Guerraoui was the rst keynote speaker, and he got things o to a great start by discussing the broad relevance of the research done in our community relative to both industry and academia. He rst argued that, in some sense, the fact that ...
Node and Edge Averaged Complexities of Local Graph Problems
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed ComputingWe continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. The node-averaged complexity of a distributed algorithm running on a graph G=(V,E) is the average over the times at which the ...
Brief Announcement: Distributed MST Computation in the Sleeping Model: Awake-Optimal Algorithms and Lower Bounds
PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed ComputingWe study the distributed minimum spanning tree (MST) problem, a fundamental problem in distributed computing. It is well-known that distributed MST can be solved in Õ(D+√n) rounds in the standard CONGEST model (where n is the network size and D is the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
December 2019
114 pages
Copyright © 2019 Copyright is held by the owner/author(s).
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 December 2019
Published in SIGACT Volume 50, Issue 4
Check for updates
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 226Total Downloads
- Downloads (Last 12 months)12
- Downloads (Last 6 weeks)4
Reflects downloads up to 05 Mar 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in