ACM SIGACT News Distributed Computing Column ArchiveDan Alistarh, EditorJennifer L. Welch, previous Editor (December 2013 - June 2019) Idit Keidar, previous Editor (December 2007 - September 2013) Sergio Rajsbaum, previous Editor (until September 2007) |
|
|
Archive (2013-2019) |
|
Archive (2000-2013) |
|
|---|
This is an archive of Distributed Computing Columns published between December 2000 and June 2019 for the quarterly ACM publication (electronic and printed) SIGACT News.
Acknowledgment
Sergio Rajsbaum edited this column for seven years until 2007 and established it as a relevant and popular venue. Idit Keidar took over for the next six years and continued and enhanced the tradition. Most of the issues consist of contributions by guest authors. The success of this column is thanks to them.
COPYRIGHT
The documents available here are provided as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Permission to make digital or hard copies of part or all of these works for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page.I retain the copyright to my columns, and authors contributing to them retain the copyright of their papers; those can be submitted in more polished forms to refereed conferences and publications. All ACM wants is the right to publish the column in hardcopy and electronic formats (in SIGACT News Online and the ACM Digital Library). I would appreciate being notified, however, of any uses being made of the column.
This column consists of an overview of reconfigurable data center networks and is contributed by Klaus-Tycho Foerster and Stefan Schmid. After giving some accessible background on how such networks came about from the technological and empirical perspective, the authors provide an overview of the algorithmic results obtained so far for problems in this area. The take-away is that the surface has only been scratched and there is potential for much interesting work on algorithmic foundations for reconfigurable data center networks.
Many thanks to Klaus and Stefan for their contribution!| "Introduction" | 1 |
| "Survey of Reconfigurable Data Center Networks" by Klaus-Tycho Foerster and Stefan Schmid | 2 |
This issue’s column contains a review of the 2018 ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) by Laxman Dhulipa. Laxman has provided an insightful overview of the keynote lectures and highlights of the contributed presentations, that I hope will inspire you to track down and read the papers, if you haven’t done so already.
Many thanks to Laxman for his contribution!
| "Introduction" | 1 |
| "SPAA 2018 Review" by Laxman Dhulipa | 2 |
As with prior December issues, this issue is devoted to a review of notable events related to distributed computing that occurred during the year.
First, congratulations to Bowen Alpern and Fred Schneider, winners of the 2018 Edsger W. Dijkstra Prize in Distributed Computing for their paper "Defining Liveness"! Their paper appeared in Information Processing Letters in October 1985. The prize is jointly sponsored by ACM and EATCS, and is given alternately at PODC and DISC; this year it was given at PODC. This paper formally defined liveness properties of concurrent and distributed algorithms for the first time and also proved that every trace property is the conjunction of a safety property and a liveness property. The full citation can be found at http://www.podc.org/dijkstra/2018-dijkstra-prize/. I am delighted to include in this column the text of the remarks that Fred and Bowen gave at PODC when the award was presented to them.
Congratulations as well to Rati Gelashvili, who received the 2018 Principles of Distributed Computing Doctoral Dissertation Award! His thesis is entitled "On the Complexity of Synchronization" and was supervised by Professor Nir Shavit at the Massachusetts Institute of Technology. The award is jointly sponsored by PODC and DISC, and was given at DISC this year. The citation appears at http://www.podc.org/dissertation/2018-dissertation-award/. The thesis introduces a complexity-based hierarchy for concurrent objects based on combinations of weaker synchronization instructions rather than those considered in the classical consensus hierarchy. His new approach reflects the fact that actual multiprocessors let processes apply supported atomic instructions to arbitrary memory locations. The thesis also includes a linear-space lower bound for anonymous randomized consensus.
Avery Miller has contributed a review of SIROCCO3 2018. The SIROCCO Prize for Innovation in Distributed Computing was given to Zvi Lotker for his work "in network algorithms, but especially for his creative contributions to the theory of wireless and social networks." The full laudatio can be found at https://sites.google.com/view/sirocco2018/sirocco-prize?authuser=0. Tal Navon received the best student paper award for her paper "Mixed Fault Tolerance in Server Assignment: Combining Reinforcement and Backup" coauthored with David Peleg. Congratulations to Zvi, Tal, and David!
Next, Naama Ben-David provides us with a review of PODC 2018. Best student paper awards were given to Guy Goren for his paper with Yoram Moses titled "Silence" and to Thibault Rieutord and Yuan He for their paper with Petr Kuznetsov titled "An Asynchronous Computability Theorem for Fair Adversaries". Leonid Barenboim, Michael Elkin and Uri Goldenberg received the best paper award for their paper titled "Locally-Iterative Distributed (Delta + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models". Congratulations to Guy, Yoram, Thibault, Yuan, Petr, Leonid, Michael and Uri!
The column closes with a review of DISC 2018 by Aditya Biradavolu and Saptaparni Kumar. Best paper awards were given to Ali Mashreghi and Valerie King for their paper "Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model" and to Gregory Chockler and Alexey Gotsman for their paper "Multi-Shot Distributed Transaction Commit". Congratulations to Ali, Valerie, Gregory, and Alexey!
Many thanks to Bowen, Fred, Avery, Naama, Aditya and Saptaparni for their contributions!
| "Introduction" | 1 |
| "History and Context for Defining Liveness, Winner 2018 Edsger W. Dijkstra Prize" by Fred Schneider | 3 |
| "Edsger W. Dijkstra: The Main Behind the Prize" by Bowen Alpern | 7 |
| "SIROCCO 2018 Review" by Avery Miller | 9 |
| "PODC 2018 Review" by Naama Ben-David | 26 |
| "DISC 2018 Review" by Aditya Biradavolu and Saptaparni Kumar | 32 |
Population protocols have been an active area of distributed computing for over a decade, as they are an abstract model of numerous real-world scenarios from sensor networks to biological computing paradigms. For this column, Dan Alistarh and Rati Gelashvili provide a timely overview of recent results on population protocols, focusing especially on the case when each agent in the system can have more than a constant amount of local memory. Several key building blocks are presented, followed by applications of these primitives, in an accessible way that conveys the excitement of fast-moving developments in the area.
Many thanks to Dan and Rati for their contribution!
| "Introduction" | 1 |
| "Recent Algorithmic Advances in Population Protocols" by Dan Alistarh and Rati Gelashvili | 2 |
Blockchains and distributed ledgers, the technologies underlying Bitcoin and other decentralized transaction systems, have been garnering increasing interest in the theoretical distributed computing community. The current column, by Antonio Fernáandez Anta, Chryssis Georgiou, Kishori Konwar, and Nicolas Nicolaou, starts with an informative overview of the world of distributed ledgers and motivates the need for rigorous approaches. The authors present an approach for formally specifying a distributed ledger in the context of several popular consistency conditions. The authors then give algorithms that implement the different variants in message-passing systems subject to crash failures. The article closes with a discussion of intriguing open questions.
Many thanks to Antonio, Chryssis, Kishori and Nicolas for their timely contribution!
| "Introduction" | 1 |
| "Formalizing and Implementing Distributed Ledger Objects" by Antonio Fernández Anta, Chryssis Georgiou, Kishori Konwar, and Nicolas Nicolaou | 2 |
The current column is devoted to concurrency from a pedagogical perspective. The first contribution, from Wojciech Golab, revisits Brewer’s CAP principle ("consistency (C), availability (A), and partition-tolerance (P) are not simultaneously achievable") for large-scale distributed systems and Abadi’s extension called PACELC ("if P then A or C, else L or C"). The paper presents an alternative proof of the CAP theorem using a new latency lower bound for the asynchronous model, and then provides a formal interpretation of PACELC.
The second contribution, from Petr Kuznetsov, is a review of the first summer school on Practice and Theory of Concurrent Computing, which was held in summer 2017 in Saint Petersburg, Russia. The article provides overviews of the topics covered in the summer school and ends with some first-hand evaluations from teachers and students.
Many thanks to Wojciech and Petr for their contributions!
| "Introduction" | 1 |
| "Proving PACELC" by Wojciech Golab | 2 |
| "The First Summer School on Practice and Theory of Concurrent Computing SPTCC 2017" by Petr Kuznetsov | 11 |
As with prior December issues, this issue is devoted to a review of notable events related to distributed computing that occurred during the year.
First, congratulations to Elizabeth Borowksy and Eli Gafni, winners of the 2017 Edsger W. Dijkstra Prize in Distributed Computing for their paper “Generalized FLP Impossibility Result for t-Resilient Computations”! Their paper appeared in the 1993 ACM Symposium on Theory of Computing (STOC). The prize is jointly sponsored by ACM and EATCS, and is given alternately at PODC and DISC; this year it was given at DISC. To quote from the award committee’s citation,
"...this paper turned out to be crucial for our understanding of fault-tolerant distributed computing. It proposed a powerful reduction technique, the BG simulation, it introduced the immediate-snapshot model, and it established the fundamental impossibility of k-resilient k-set consensus."The full citation can be found at http://www.podc.org/dijkstra/2017-dijkstra-prize/. Congratulations as well to Mohsen Ghaffari, who received the 2017 Principles of Distributed Computing Doctoral Dissertation Award! His thesis is entitled "Improved Distributed Algorithms for Fundamental Graph Algorithms" and was supervised by Professor Nancy Lynch at the Massachusetts Institute of Technology. The award is jointly sponsored by PODC and DISC, and was given at PODC this year. The citation appears at http://www.podc.org/dissertation/2017-dissertation-award/. The thesis includes new and improved results for maximal independent set, vertex- and edge-connectivity, and scheduling multiple network tasks. And this is just the tip of the iceberg of the results he obtained while in graduate school!
The first article of the column is a review of SIROCCO 2017 by Christian Konrad. The best paper award was given to Magnus M. Halldorsson, Stephan Holzer, and Evangelia Anna Markatou for their paper "Leader Election in SINR Model with Arbitrary Power Control". Congratulations to Magnus, Stephan, and Evangelia!
The second article of the column is a review of SPAA 2017 by Sepehr Assadi. Sepehr is a coauthor, together with Sanjeev Khanna, of "Randomized Composable Coresets for Matching and Vertex Cover," which received a best paper award at SPAA. The paper "Distributed Partial Clustering" by Sudipto Guha, Yi Li, and Qin Zhang also received a best paper award. Congratulations to Sepehr, Sanjeev, Sudipto, Yi, and Qin!
Next, Peter Davies provides us with a review of PODC 2017. Peter’s paper "Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks", coauthored with Artur Czumaj, received the best student paper award. The best paper award went to "A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities" by Michael Elkin. Congratulations to Artur, Peter, and Michael! The column closes with a review of DISC 2017 by Manuela Fischer and Yannic Maus. Manuela was the winner of the best student paper award for "Improved Deterministic Distributed Matching via Rounding". Yannic is an author, together with Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Jukka Suomela and Jara Uitto, of "Improved Distributed Degree Splitting and Edge Coloring" which received the best paper award. Congratulations to Manuela, Mohsen, Juho, Fabian, Yannic, Jukka, and Jara!Many thanks to Christian, Sepehr, Peter, Manuela and Yannic for their contributions!
| "Introduction" | 1 |
| "SIROCCO 2017 Review" by Christian Konrad | 3 |
| "SPAA 2017 Review" by Sepehr Assadi | 10 |
| "PODC 2017 Review" by Peter Davies | 14 |
| "DISC 2017 Review" by Manuela Fischer and Yannic Maus | 17 |
You may be familiar with the Banff International Research Station (BIRS), a conference center located in Alberta, Canada, that hosts workshops in the mathematical sciences. Recently, BIRS has expanded to include a location in Oaxaca, Mexico, called the Casa Matemática Oaxaca (CMO) and workshops started at CMO in 2015. In this column, I provide a review of the CMO Workshop on Complexity and Analysis of Distributed Algorithms, organized by Hagit Attiya, Sergio Rajsbaum, and Philipp Woelfel, which I was fortunate enough to attend in 2016.
| "Introduction" | 1 |
| "Review of 2016 BIRS CMO Workshop on Complexity and Analysis of Distributed Algorithms" by Jennifer L. Welch | 2 |
Programmable matter is a term denoting a collection of small and simple computing entities that can work together to change their characteristics and accomplish a task. Variations of this idea have been considered in widely disparate communities. In summer 2016, a Dagstuhl seminar devoted to this topic brought together researchers from the algorithms, robotics, and distributed systems communities. The seminar was organized by Sándor Fekete, Andréa Richa, Kay Römer, and Christian Scheideler, who have contributed an overview for the current column. Their contribution consists of a description of the purpose of the workshop, and a concise summary of all the talks given. The topics range from computer systems to algorithmic theory to DNA-computing to caterpillars, just to name a few. The distributed computing community has touched on this area in the past, but new fascinating problems have surfaced, and the article gives us a convenient set of pointers to them.
Many thanks to Sándor, Andréa, Kay, and Christian for their contribution!
| "Introduction" | 1 |
| "Algorithmic Foundations of Programmable Matter, Dagstuhl Seminar 16271" by Sándor P. Fekete, Andréa Richa, Kay Römer, and Christian Scheideler | 2 |
Rajeev Alur and Stavros Tripakis have contributed an in-depth, yet accessible, article about how to automatically synthesize distributed protocols. They explain how to formalize the problems of verifying, synthesizing, and completing distributed protocols. "Completing" a protocol is the problem of starting with partial information about the state machines of the processes and determining how to fill in the missing details in order to satisfy the specification. A recent algorithm for protocol completion is described. The Alternating Bit Protocol is used as a running example throughout, which provides helpful intuition. The article concludes with a list of intriguing open problems in the area.
The second article is a review of SIROCCO 2016, which was held in Helsinki, Finland, by Lewis Tseng. Lewis provides a lively report of the highlights of the conference, including Masafumi (Mark) Yamashita’s receiving the SIROCCO Prize for Innovation, the invited talks, and a sampling of the contributed talks. Don’t miss his photos of the beautiful locale.
Many thanks to Rajeev, Stavros, and Lewis for their contributions!
| "Introduction" | 1 |
| "Automatic Synthesis of Distributed Protocols" by Rajeev Alur and Stavros Tripakis | 2 |
| "SIROCCO 2016 Review" by Lewis Tseng | 38 |
As with prior December issues, this issue is devoted to a review of notable events related to distributed computing that occurred during the year.
First, congratulations to Noga Alon, László Babi Alon Itai, and Michael Luby who shared the 2016 Dijkstra Prize for their papers on maximal independent set algorithms! Noga, László, and Alon’s paper is "A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem" and Michael’s paper is "A Simple Parallel Algorithm for the Maximal Independent Set Problem". The prize is jointly sponsored by ACM and EATCS, and is given alternately at PODC and DISC; this year it was given at PODC. The full citation can be found at http://www.podc.org/dijkstra/2016-dijkstra-prize/; highlights are:
"In these seminal works, the authors present, simultaneously and independently, an O(log n) time randomized distributed/parallel algorithm for the Maximal Independent Set (MIS) problem. MIS is regarded as a crown jewel of distributed symmetry breaking problems, and a central problem in the area of locality in distributed computing. The nominated papers provide a fascinatingly simple, elegant, and efficient randomized solution for this problem."Congratulations as well to Hsin-Hao Su and Shahar Timnat, who split the Principles of Distributed Computing Doctoral Dissertation Award! Hsin-Hao’s dissertation was entitled “Algorithms for Fundamental Problems in Computer Networks”, supervised by Seth Pettie at the University of Michigan, Ann Arbor. Shahar’s dissertation was entitled “Practical Parallel Data Structures”, supervised by Erez Petrank at the Technion. The award is jointly sponsored by PODC and DISC, and was given at DISC this year. The citation appears at http://www.podc.org/dissertation/2016-dissertation-award/; it highlights Hsin-Hao’s new and improved algorithms for graph coloring and Shahar’s work to make lock-free concurrent data structures wait-free.
The first article of the column is a review of PODC 2016 by Gregory Schwartzman, who won the Best Student Paper award for his paper “A Distributed (2 + ε)-approximation for Vertex Cover in O(log ∆/ε log log ∆) Rounds” with co-authors Reuven Bar-Yehuda and Keren Censor-Hillel. The Best Paper Award was given for the paper “Analysing Snapshot Isolation” by Andrea Cerone and Alexey Gotsman. Congratulations to Gregory, Reuven, Keren, Andrea and Alexey!
The second article is a review of DISC 2016 by Lili Su. Seri Khoury won the Best Student Paper award for the paper “Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks,” co-authored with Amir Abboud and Keren Censor-Hillel. The Best Paper award went to “Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model” by Dan Hefetz, Fabian Kuhn, Yannic Maus and Angelika Steger. Congratulations to Seri, Amir, Keren, Dan, Fabian, Yannic, and Angelika!!
Many thanks to Gregory and Lili for their contributions!
| "Introduction" | 1 |
| "PODC 2016 Review" by Gregory Schwarzman | 3 |
| "DISC 2016 Review" by Lili Su | 7 |
This column consists of an article by Lewis Tseng and Nitin Vaidya on fault-tolerant consensus in directed networks. The fault-tolerant consensus problem was initially studied for undirected complete graphs, and then for undirected arbitrary graphs. However, there was very little work on directed graphs, especially arbitrary ones, until recently. This article provides an overview of the authors’ work on identifying exactly what conditions on the topology of directed graphs are necessary and sufficient for solving consensus (exact/approximate) in various models (crash/Byzantine failures, synchronous/asynchronous) with either iterative or general algorithms. The authors point out interesting connections to papers in the control theory literature and leave us with a couple of intriguing open questions
Many thanks to Lewis and Nitin for their contributions!
| "Introduction" | 1 |
| "A Note on Fault-Tolerant Consensus in Directed Networks" by Lewis Tseng and Nitin H. Vaidya | 2 |
This column consists of an article by Roderick Bloem, Swen Jacobs, Ayrat, Khalimov, Igor Konnov, Sasha Rubin, Helmut Veith, and Josef Widder on automated verification of distributed algorithms. One of the challenges in this area is how to have the number of processors be a parameter, instead of a fixed constant. The authors recently completed a book for the Morgan & Claypool Distributed Computing Synthesis Lectures series on the subject of the decidability of parameterized verification and I thought the readers of this column might enjoy a preview of the book providing a taste of the questions studied in parameterized model checking.
On a very sad note, Helmut passed away unexpectedly during the preparation of this article. He had been working on furthering connections between the formal verification and distributed computing communities, among other projects, and will be greatly missed.
Many thanks to Roderick, Swen, Ayrat, Igor, Sasha, Helmut, and Josef for their contributions!
| "Introduction" | 1 |
| "Decidability in Parameterized Verification" by Roderick Bloem, Swen Jacobs, Ayrat Khalimov, Igor Konnov, Sasha Rubin, Helmut Veith, and Josef Widder | 2 |
Dynamic networks have been the subject of renewed interest recently, as they model peer-to-peer networks, mobile nodes in wireless networks, and data centers. Theoretical analysis of these networks is quite challenging, and are exacerbated by the presence of faults. This column consists of an article by John Augustine, Gopal Pandurangan, and Peter Robinson on the distributed algorithmic foundations of dynamic networks. The authors motivate the problem from a practical perspective, and overview some of their recent results for agreement, leader election, search and storage, and expander maintenance. A key feature of the paper is that the results are presented in a unified manner and the techniques used are highlighted. The article ends with some intriguing open problems.
Many thanks to John, Gopal and Peter for their contributions!
| "Introduction" | 1 |
| "Distributed Algorithmic Foundations of Dynamic Networks" by John Augustine, Gopal Pandurangan and Peter Robinson | 2 |
As with prior December issues, this issue is devoted to a review of notable events related to distributed computing that occurred during the year.
First, congratulations to Michael Ben-Or and Michael O. Rabin who received the 2015 Dijkstra Prize for starting the field of fault-tolerant randomized distributed computing! Michael Ben-Or's paper was "Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols" and Michael Rabin's paper was "Randomized Byzantine Generals". The prize is jointly sponsored by ACM and EATCS, and is given alternately at PODC (ACM Symposium on Principles of Distributed Computing) and DISC (EATCS Symposium on Distributed Computing); this year it was given at DISC. The full citation can be found at http://www.podc.org/dijkstra/2015-dijkstra-prize/; highlights are:
"Ben-Or and Rabin were the first to use randomness to solve to a problem, consensus in an asynchronous distributed system subject to failures, which had provably no deterministic solution. In other words, they were addressing a computability question and not a complexity one, and the answer was far from obvious... Ben-Or and Rabin’s algorithms opened the way to a large body of work on randomized distributed algorithms in asynchronous systems..."Congratulations as well to Leonid Barenboim, who was awarded the Principles of Distributed Computing Doctoral Dissertation Award! Leonid's dissertation was entitled "Efficient Network Utilization in Locality-Sensitive Distributed Algorithms", supervised by Michael Elkin at Ben Gurion University. The award is jointly sponsored by PODC and DISC was given at DISC. The citation appears at http://www.podc.org/dissertation/2015-dissertation-award. Leonid has provided some insights into his dissertation work in the first article of this column.
Spain was the place to be for distributed computing this past July. First, SIROCCO (International Colloquium on Structural Information and Communication Complexity) was held in Montserrat, and a few days later PODC started in Donostia-San Sebastián.
The next article is a review of SIROCCO 2015 by Marc Bury, who was one of the winners of the Best Student Paper Award for his paper "Randomized OBDD-Based Graph Algorithms." The other winner was Katia Patkin for her paper "Under the Hood of the Bakery Algorithm: Mutual Exclusion as a Matter of Priority", co-authored with Yoram Moses. Michel Raynal was the recipient of the SIROCCO Innovation Award in Distributed Computing for his work on the condition-based approach to fault-tolerant consensus. Congratulations to Marc, Katia, Yoram, and Michel!
The next article of the column is a review of PODC 2015 by Lewis Tseng. The winner of the Best Student Paper award was Mohsen Ghaffari for his single-author paper "Near-Optimal Scheduling for Distributed Algorithms"; this is the second year in a row that he has received this award. The Best Paper Award was given for the paper "Deterministic (Delta+1) Coloring in Sublinear (in Delta) Time, in Static, Dynamic and Faulty Networks" by Leonid Barenboim; more about this work appears in the first article. Congratulations to Mohsen and Leonid!
The last article is a review of DISC 2015 by Hillel Avni and Rati Gelashvili. Rati won the Best Paper award for his single-author paper "On the Optimal Space Complexity of Consensus for Anonymous Processes". Yuezhou Lv is the student author of "Local Information in Influence Networks", which won the Best Student Paper award and was co-authored with Thomas Moscibroda. Congratulations to Rati, Yuezhou, and Thomas!
Many thanks to Leonid, Lewis, Marc, Hillel, and Rati for their contributions!
| "Introduction" | 1 |
| "Distributed Symmetry-Breaking from a Local Point of View" by Leonid Barenboim | 3 |
| "SIROCCO 2015 Review" by Marc Bury | 7 |
| "PODC 2015 Review" by Lewis Tseng | 13 |
| "DISC 2015 Review" by Hillel Avni and Rati Gelashvili | 22 |
This column consists of an article on resource-competitive distributed algorithms by Michael Bender, Varsha Dani, Jeremy Fineman, Seth Gilbert, Mahnush Movahedi, Seth Pettie, Jared Saia, and Maxwell Young. The authors begin by motivating their definition of resource-competitive algorithms and how it differs from previous, superficially similar, concepts. They give several examples of these algorithms and their analyses, each with different notions of "resource", from the realms of jamming-resistant wireless communication, backoff algorithms for communication, noise-tolerant communication, and bridge-distribution in anonymous networks like Tor. The paper concludes with some open questions should spark interesting follow-on work.
Many thanks to Michael, Varsha, Jeremy, Seth, Mahnush, Seth, Jared, and Maxwell for their contributions! (This article may win the prize for the most authors of any Distributed Computing Column.)
| "Introduction" | 1 |
| "Resource-Competitive Algorithms" by Michael A. Bender, Varsha Dani, Jeremy T. Fineman, Seth Gilbert, Mahnush Movahedi, Seth Pettie, Jared Saia, and Maxwell Young | 2 |
Maurice Herlihy is one of the most renowned members of the Distributed Computing community. He is currently a professor in the Computer Science Department at Brown University. He has an A.B. in Mathematics from Harvard University, and a Ph.D. in Computer Science from M.I.T. He has served on the faculty of Carnegie Mellon University and on the staff of DEC Cambridge Research Lab. He is the recipient of the 2003 Dijkstra Prize in Distributed Computing, the 2004 Gödel Prize in theoretical computer science, the 2008 ISCA influential paper award, the 2012 Edsger W. Dijkstra Prize, and the 2013 Wallace McDowell award. He received a 2012 Fulbright Distinguished Chair in the Natural Sciences and Engineering Lecturing Fellowship, and he is a fellow of the ACM, a fellow of the National Academy of Inventors, and a member of the National Academy of Engineering and the American Academy of Arts and Sciences.
On the occasion of his 60th birthday, the SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), which was held in Paris, France in July 2014, hosted a celebration which included several technical presentations about Maurice's work by colleagues and friends. This column includes a summary of some of these presentations, written by the speakers themselves. In the first article, Vassos Hadzilacos overviews and highlights the impact of Maurice's seminal paper on wait-free synchronization. Then, Tim Harris provides a perspective on hardware trends and their impact on distributed computing, mentioning several interesting open problems and making connections to Maurice's work. Finally, Michael Scott gives a concise retrospective on transactional memory, another area where Maurice has been a leader.
This is a joint column with the Distributed Computing Column of the Bulletin of the European Association for Theoretical Computer Science (June 2015 issue), edited by Panagiota Fatourou.
Many thanks to Vassos, Tim, and Michael for their contributions!
| "Introduction" | 1 |
| "A Quarter-Century of Wait-Free Synchronization" by Vassos Hadzilacos | 2 |
| "Hardware Trends: Challenges and Opportunities in Distributed Computing" by Tim Harris | 12 |
| "Transactional Memory Today" by Michael Scott | 19 |
This issue is devoted to an insightful article by Keren Censor-Hillel, explaining the relationships between distributed algorithms for a variety of problems, including synchronization and gossip, and corresponding combinatorial structures, such as sparse spanners. This connection can help prove both upper and lower bounds for distributed computing problems. The article features a lucid exposition, discussion of open problems, and extensive references for further exploration.
Many thanks to Keren for her contributions!
| "Introduction" | 1 |
| "Distributed Algorithms as Combinatorial Structures" by Keren Censor-Hillel | 2 |
As with prior December issues, this issue is devoted to a review of notable events related to distributed computing that occurred during the year.
First, congratulations to Leslie Lamport for receiving the 2013 Turing Award! The award was announced in spring of 2014, and Leslie chose to give his acceptance lecture at PODC (ACM Symposium on Principles of Distributed Computing) 2014. The award was given
[f]or fundamental contributions to the theory and practice of distributed and concurrent systems, notably the invention of concepts such as causality and logical clocks, safety and liveness, replicated state machines, and sequential consistency.More details, including photos, are in this column's PODC review. And a lengthy description of Leslie's many research accomplishments, authored by Dahlia Malkhi with contributions from several others, can be viewed here: http://amturing.acm.org/award_winners/lamport_1205376.cfm. Also, congratulations to Kanianthra Mani Chandy and Leslie Lamport who received the 2014 Dijkstra Prize for their paper "Distributed Snapshots: Determining Global States of Distributed Systems"! The prize is jointly sponsored by ACM and EATCS, and is given alternately at PODC and DISC (International Symposium on Distributed Computing); however, with Leslie speaking at PODC and Mani giving a keynote talk at DISC, and both of them alluding to the Dijkstra Prize, it was difficult to determine the official locale for the prize acceptance (officially it was given at PODC). The full citation can be found at http://www.podc.org/dijkstra/2014-dijkstra-prize/; highlights are:
Bernhard Haeupler's thesis provides a sweeping multidisciplinary study of information dissemination in a network, making fundamental contributions to distributed computing and its connections to theoretical computer science and information theory. The thesis addresses an impressive list of topics to which Dr. Bernhard Haeupler contributed significantly. These topics include the design and analysis of gossip protocols overcoming the dependency to connectivity parameters such as conductance, the introduction of a completely new technique for analyzing the performance of network coding gossip algorithms, and new randomized protocols for multi-hop radio networks. These are just a few samples of the very many important contributions of Dr. Bernhard Haeupler's thesis, and the work in this dissertation is distinguished by an impressive combination of creativity, breadth, and technical skill.The first invited article of the column is a review of PODC 2014 by Oksana Denysyuk. The winner of the Best Student Paper award was Mohsen Ghaffari for his paper "Distributed Connectivity Decomposition," coauthored with Keren Censor-Hillel and Fabian Kuhn. The Best Paper Award was given for the paper "Signature-Free Asynchronous Byzantine Consensus with t < n/3 and O(n2) Messages," by Achour Mostéfaoui, Hamouma Moumen and Michel Raynal. Congratulations to Mohsen, Achour, Hamouma, and Michel! The second invited article is a review of DISC 2014 by Merav Parter and Edward Talmage. Merav won the Best Student Paper award for her single-author paper "Vertex Fault Tolerant Additive Spanners". Ho-Lin Chen, Rachel Cummings, David Doty and David Soloveichik received the Best Paper Award for their paper "Speed Faults in Computation by Chemical Reaction Networks." Congratulations to Merav, Ho-Lin, Rachel, David and David! As reported in the previous article, part of the fun of DISC was all the ancillary activities, which included two workshops and a tutorial session. A detailed review of the workshop on Biological Distributed Algorithms is provided by Mira Radeva in the last invited article of this column. Many thanks to Oskana, Merav, Edward, and Mira for their contributions!
| "Introduction" | 1 |
| "Review of PODC 2014" by Oksana Denysyuk | 4 |
| "DISC 2014 Review" by Merav Parter and Edward Talmage | 9 |
| "Review of BDA Workshop 2014" by Mira Radeva | 15 |
In the first part of this issue's column, Magnús Halldórsson and Calvin Newport take a fresh perspective on doing a workshop review. They highlighted five big-picture ideas that came out of the presentations and discussion at 2013 Workshop on Realistic Models of Wireless Networks (WRAWN) which they organized and was co-located with PODC. The focus of the workshop was whether wireless theory is sufficiently relevant to wireless practice, and if not, what can be done to improve matters.
The second part of the column is a review of the 2013 Workshop on the Theory of Transactional Memory, which was co-located with DISC. The authors, Claire Capdevielle and Sandeep Hans, have done a great job of summarizing the talks as well as putting the topics of the talks into the wider context of prior work.
The column concludes with a research paper by Heger Arfaoui and Pierre Fraigniaud on lower bounds for {\em quantum} distributed algorithms. The beauty of their approach is that the bounds can be shown without having to manipulate concepts from quantum mechanics at all! A key idea, as in the DISC 2009 paper by Gavoille, Kosowski, and Markiewicz, is to identify a class of distributions that subsumes those of quantum computing but that is easier to work with. This is then exploited to show that for most two-player games in which the players cannot communicate, quantum correlations do not allow a higher probability of success than the classical model.
Many thanks to Magnús, Calvin, Claire, Sandeep, Heger and Pierre for their contributions!
| "Introduction" | 1 |
| "Making Wireless Algorithm Theory More Useful: Five Ideas from the 2013 Workshop on Realistic Models for Algorithms in Wireless Networks" by Magnús Halldórsson and Calvin Newport | 2 |
| "WTTM 2013, The Fifth Workshop on the Theory of Transactional Memory" by Claire Capdevielle and Sandeep Hans | 5 |
| "What Can Be Computed without Communications?" by Heger Arfaoui and Pierre Fraigniaud | 12 |
You might want to check out previous coverage of TM in this Column, dating back to 2008. In March of that year, the entire column was devoted to the topic, in the context of multicore systems. The first four Workshops on the Theory of Transactional Memory (WTTM) are reviewed in the December 2009, December 2010, March 2012, and December 2012 issues. The latter issue also covers the awarding of the 2012 Dijkstra Prize for the work by Herlihy, Moss, Shavit and Touitou on TM.
Many thanks to Gokarna and Costas for their contribution!
| "Introduction" | 1 |
| "Transactional Memory: Models and Algorithms" by Gokarna Sharma and Costas Busch | 2 |
Many thanks to the seminar organizers, Bettina Kemme, G. Ramalingam, Andre Schiper, and Marc Shapiro, as well as all the attendees, for their contribution!
| "Introduction" | 66 |
| "Dagstuhl Seminar Review: Consistency in Distributed Systems" by Bettina Kemme, G. Ramalingam, André Schiper, and Marc Shapiro | 67 |
As with prior December issues, this issue is devoted to a review of notable events related to distributed computing that occurred during the year.
First, congratulations to Nati Linial who received the 2013 Dijkstra Prize for his paper "Locality in Distributed Graph Algorithms"! I have reproduced the citation for his award, which was presented at the International Symposium on Distributed Computing (DISC), illustrated with a photo. Congratulations as well to Shiri Chechik and Danupon Nanongkai, who were awarded the Principles of Distributed Computing Doctoral Dissertation Award! Shiri's dissertation was entitled "Fault-Tolerant Structures in Graphs", while Danupon's was "Graphs and Geometric Algorithms on Distributed Networks and Databases". I have also reproduced their citations; the awards were also given at DISC. Graphs rule!
The first invited article is a review of the 2013 ACM Symposium on Principles of Distributed Computing (PODC) by Nicolas Braud-Santoni. Nicolas is the student author of the paper "Fast Byzantine Agreement", which received a Best Student Paper Award; the other authors are Rachid Guerraoui and Florian Huc. Ami Paz is the student author of the paper "Upper Bound on the Complexity of Solving Hard Renaming", which also received a Best Student Paper Award; his coauthors are Hagit Attiya, Armando Castaneda, and Maurice Herlihy. Shiri Chechik received the Best Paper award for her paper "Compact Routing Schemes with Improved Stretch". Congratulations to Nicolas, Ami, and Shiri! Additional notable happenings at PODC are reported by Nicolas.
The second invited article is a review of DISC 2013 by Shahar Timnat. Shahar won the Best Student Paper award for "Lock-Free Iterators", coauthored with Erez Petrank. Mohsen Ghaffari and Fabian Kuhn received the Best Paper Award for "Distributed Minimum Cut Approximations." Congratulations to Shahar, Mohsen and Fabian! See Shahar's article for more inside information about DISC.
To close, Ami Paz has provided us with a lively review of the Mathematical Methods in Theoretical Distributed Computing workshop, which occurred August 26--30 in Bremen, Germany.
Many thanks to Nicolas, Shahar, and Ami for their contributions! For those of us who were unable to attend these events, we can get the flavor of them and be inspired not to miss them next year.
| "Introduction" | 79 |
| "2013 Dijkstra Prize in Distributed Computing" | 81 |
| "2013 Principles of Distributed Computing Doctoral Dissertation Award" | 82 |
| "PODC 2013 Review" by Nicolas Braud-Santoni | 83 |
| "DISC 2013 Review" by Shahar Timnat | 87 |
| "Bremen Workshop Review" by Ami Paz | 91 |
Please see Idit Keidar's Distributed Computing Column website.