ACM SIGACT News Distributed Computing Column

Jennifer L. Welch, Editor

Idit Keidar, previous Editor (December 2007 - September 2013)

Sergio Rajsbaum, previous Editor (until September 2007)


  New columns (from Dec 2013)  
  Archive (2000-2013)  

This is an archive of Distributed Computing Columns published since December 2000 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.

Call for Contributions

Please send me suggestions for material to include in this column, including news, communications, and authors willing to write a guest column or to review an event related to distributed computing. In particular, I welcome tutorials, either exposing the community to new and interesting topics, or providing new insight on well-studied topics by organizing them in new ways. I also welcome open problems with short descriptions of context and motivation.

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.

 

Contents

 

Column Introductions and Tables of Contents

Column 66, SIGACT News Volume 48, Number 2, June 2017
Algorithmic Foundations of Programmable Matter, Dagstuhl Seminar 16271
Pdf

Introduction

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!

Column 66 Table of Contents


Column 65, SIGACT News Volume 48, Number 1, March 2017
Automatic Synthesis of Distributed Protocols and SIROCCO 2016 Review
Pdf

Introduction

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!

Column 65 Table of Contents


Column 64, SIGACT News Volume 47, Number 4, December 2016
Annual Review 2016
Pdf

Introduction

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!

Column 64 Table of Contents


Column 63, SIGACT News Volume 47, Number 3, September 2016
A Note on Fault-tolerant Consensus in Directed Networks
Pdf

Introduction

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 neces- sary 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!

Column 63 Table of Contents


Column 62, SIGACT News Volume 47, Number 2, June 2016
Decidability in Parameterized Verification
Pdf

Introduction

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!

Column 62 Table of Contents


Column 61, SIGACT News Volume 47, Number 1, March 2016
Distributed Algorithmic Foundations of Dynamic Networks
Pdf

Introduction

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!

Column 61 Table of Contents


Column 60, SIGACT News Volume 46, Number 4, December 2015
Annual Review 2015
Pdf

Introduction

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!

Column 60 Table of Contents


Column 59, SIGACT News Volume 46, Number 3, September 2015
Resource-Competitive Algorithms
Pdf

Introduction

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.)

Column 59 Table of Contents


Column 58, SIGACT News Volume 46, Number 2, June 2015
Maurice Herlihy's 60th Birthday Celebration
Pdf

Introduction

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!

Column 58 Table of Contents


Column 57, SIGACT News Volume 46, Number 1, March 2015
Distributed Algorithms as Combinatorial Structures
Pdf

Introduction

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!

Column 57 Table of Contents


Column 56, SIGACT News Volume 45, Number 4, December 2014
Annual Review 2014
Pdf

Introduction

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: Congratulations as well to Bernhard Haeupler, who was awarded the Principles of Distributed Computing Doctoral Dissertation Award! Bernhard's dissertation was entitled "Probabilistic Methods for Distributed Information Dissemination", supervised by Jonathan Kelner, Muriel Médard, and David Karger at MIT. The award is jointly sponsored by PODC and DISC was given at DISC. The citation ( http://www.podc.org/dissertation/2014-dissertation-award/) is:
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!

Column 56 Table of Contents


Column 55, SIGACT News Volume 45, Number 3, September 2014
WRAWN 2013 Review, WTTM 2013 Review, and Lower Bounds for Distributed Quantum Computing
Pdf

Introduction

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!

Column 55 Table of Contents


Column 54, SIGACT News Volume 45, Number 2, June 2014
Transactional Memory: Models and Algorithms
Pdf

Introduction

This issue's column consists of a review article by Gokarna Sharma and Costas Busch on models and algorithms for transactional memory (TM), with particular emphasis on scheduling. With the ever-growing popularity of TM, this is a timely topic. The authors cover three main models. First, work on transaction scheduling algorithms for tightly-coupled systems are surveyed. Second, distributed networks systems are considered; the new aspect is how to find the shared objects efficiently and provide consistency of the objects after transactions terminate. Third, related results for non-uniform memory access systems are surveyed, with emphasis on how to provide consistency in a load-balanced way. The article closes with a discussion of future directions.

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!

Column 54 Table of Contents


Column 53, SIGACT News Volume 45, Number 1, March 2014
Dagstuhl Seminar Review: Consistency in Distributed Systems
Pdf

Introduction

This issue's column is devoted to a detailed review of a fascinating Dagstuhl seminar on consistency in distributed systems, held in February 2013, which I was fortunate enough to attend. This seminar brought together researchers and practitioners in distributed systems, programming languages, databases and concurrent programming to make progress in understanding the trade-offs between data consistency, availability and fault-tolerance. In addition to the tutorials, technical presentations, and breakout sessions reported on below, attendees got the opportunity to participate in a chilly but rewarding trip to the city of Trier, containing the Porta Nigra (the Black Gate, the largest Roman city gate north of the Alps) and the Trier Cathedral (home to the Holy Tunic).

Many thanks to the seminar organizers, Bettina Kemme, G. Ramalingam, Andre Schiper, and Marc Shapiro, as well as all the attendees, for their contribution!

Column 53 Table of Contents


Column 52, SIGACT News Volume 44, Number 4, December 2013
Annual Review 2013
Pdf

Introduction

This is my inaugural issue as editor of the SIGACT News Distributed Computing Column. I am honored to be asked to take over from Idit Keidar, who has done a wonderful job with the column for the last seven years, obtaining a wide variety of articles that have provided the community with informative news, and leavening it with her sense of humor. I hope to continue to rely on the efforts of the community to share information about our field.

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.

Column 52 Table of Contents


 

Archive - Columns Edited by Idit Keidar (2007-2013) and Sergio Rajsbaum (2000-2007)

Please see Idit Keidar's Distributed Computing Column website.