ACM SIGACT News Distributed Computing Column
Archive of columns edited by Idit Keidar and Sergio Rajsbaum 2000-2013
The column is currently edited by Jennifer L. Welch
|New columns edited by Jennifer L. Welch||
For a few years, it was common to settle for weak consistency in such settings, adhering to the so-called "NoSQL" approach. Indeed, an article that appeared in this column four years ago1 reported a "fear of synchronization" among chief architects who had built large-scale distributed systems in industry. But in the past couple of years, we see this trend reversing. Both academic and industrial projects have recognized the need for strong consistency and so-called ACID transactions in large distributed storage systems. Such strong consistency is the topic of the current column.
Our first contribution, by Dahlia Malkhi and Jean-Philippe Martin explains the concurrency control mechanism of Google's Spanner system. Our second contribution, by Ittay Eyal, discusses more generally fault-tolerant architectures for distributed ACID transactions. Many thanks to Dahlia, Jean-Philippe, and Ittay for their contributions!
On a personal note, this is my last issue as editor of the
distributed computing column. I have truly enjoyed performing this
role for the past six years. Above all, I am grateful to the many
authors who have contributed interesting and enlightening articles on
diverse topics. They have made my job both easy and gratifying. Yet
after six years, I feel that it is time to step down, and bring in a
fresh perspective. I leave the column in the capable hands of Jennifer
Welch, who will replace me as of the next issue. I wish Jennifer that
her tenure as editor will be at least as enjoyable as mine was.
Column 51 Table of Contents
This column also pays back an outstanding debt from last year's annual review column1, with reports on the Prize for Innovation in Distributed Computing and SIROCCO 2012 where it was awarded. I open with the announcement of the prize, which was awarded to Roger Wattenhofer in 2012; congratulations Roger! The award statement is followed by our main article by Alptekin. The column concludes with a review by Heger Arfaoui of SIROCCO 2012.
Many thanks to Alptekin and Heger for their contributions!
Column 50 Table of Contents
This column deals with advances in coding theory that are (or might be) applicable to distributed storage. It begins with a primer by Yuval Cassuto, describing the different considerations in distributed storage, as well as codes designed to address them. Yuval lists a range of requirements from codes for distributed storage. The list begins with properties required in disk arrays, such as low redundancy and low encode/decode complexity, and continues to considerations that arise in wide-area distributed storage such as degraded reads and efficient rebuild. The latter is the focus of our second contribution, by Anwitaman Datta and Frederique Oggier. Their article gives an overview of codes that aim to achieve better repairability in networked distributed storage systems. In particular, Anwitaman and Frederique consider the rebuild cost in the face of concurrent failures.
Many thanks to Yuval, Anwitaman, and Frederique for their contributions!
Column 49 Table of Contents
Today's column includes two articles highlighting recent advances in automated synthesis in these two domains. Both consider the case where a given program was generated to work correctly in a certain model, but needs to be fixed to work in a different model, under less restrictive assumptions. In the context of distributed programs, Borzoo Bonakdarpour and Sandeep S. Kulkarni discuss automated model repair - a mechanism for automatically fixing bugs in a program or increasing its fault tolerance. They provide a broad survey of techniques developed in the last decade for model repair in distributed computing, fault-tolerance, self-stabilization, and real-time systems. Second, Michael Kuperstein, Martin Vechev, and Eran Yahav present an approach for automatic fence inference in concurrent programs, allowing them to run under relaxed memory models. Again, we are given a program that is correct in some restricted model - in this case, a sequentially consistent memory model - and the problem is to synthesize one that behaves correctly under a relaxed model, such as those implemented in today's computer architectures.
Many thanks to Borzoo, Sandeep, Michael, Martin, and Eran for their
Column 46 Table of Contents
In this column, Haifeng Yu presents a tutorial on how social networks
can be leveraged to defend against sybil attacks, and a survey of
recent suggestions employing this approach. Though Haifeng tackles the
problem from a theoretical standpoint, (proving formal bounds etc.),
this direction has garnered more attention from the systems community,
perhaps because sybil attacks are perceived as a real threat for which
social networks can provide a viable solution. Yet it appears that
much theory for sybil defense using social networks is yet to be
developed. In particular, there is a need for better understanding the
graph properties of social networks, and how they can be leveraged to
achieve provable bounds on false positives and false negatives in the
detection of sybil nodes. Haifeng touches upon some of these
directions in the last section.
Many thanks to Haifeng for his article!
Column 43 Table of Contents
In today's column, Fabian Kuhn and Rotem Oshman survey recent work on
dynamic networks. They consider adversarial as well as random models
of graph evolution. In this context, they explain how the classical
graph notions of diameter and cover time generalize to dynamic ones.
These notions have important implications on information dissemination
in the network. Fabian and Rotem then present an example algorithm for
counting and information dissemination on adversarially evolving
graphs. As research on dynamic networks is still in its infancy, many
questions remain open; the column concludes with a discussion of some
promising directions for future research. Many thanks to Fabian and
Rotem for this survey!
Column 41 Table of Contents
Column 40 Table of Contents
First, our main contribution, by Valerie King and Jared Saia, argues for running BA in setting with a large number of nodes (or processors). Valerie and Jared survey new BA protocols whose communication complexity is scalable in the number of participating processors. This, they argue, enables their deployment in larger-scale domains for which BA was considered infeasible before. The second contribution, by Marko Vukolic, considers another emerging domain for BA. It calls for wider-scale deployment of BA protocols, not among many processors, but rather over multiple cloud computing providers.
The column ends with a short announcement about Morgan Claypool's new monograph series on Distributed Computing Theory, edited by Nancy Lynch.
Many thanks to Valerie, Jared, and Marko for sharing their insights!
Column 39 Table of Contents
This column's contribution, by Zvi (Zvika) Lotker and David Peleg
focuses on the promising signal-to-interference and noise ratio
(SINR) model, and studies it from an algorithmic perspective. It
surveys the model's structural properties as well as algorithms
designed for this model. Along the way, some of the similarities and
differences between the SINR model and the UDG model are highlighted.
Many thanks to Zvika and David for their contribution!
Column 38 Table of Contents
Second--- our main contribution for this column is a tutorial on reconfiguration in replicated state machines, by Leslie Lamport, Dahlia Malkhi, and Lidong Zhou of Microsoft Research. This is also a bit of a throwback to a column from last year (SIGACT News 40(3), September 2009, pp. 77-85), where Lidong Zhou discussed a number of oft theoretically-neglected issues that arise in practical deployments of large-scale distributed systems. Lidong had written that, in practice, reconfiguration of replicated systems has always been a key focus, though it got little attention in theoretical work. In this column, you will find an instructive (semi-formal) treatment of this vital-but-not-well-understood issue, covering a range of practical approaches to reconfiguration.
Many thanks to Yoram, Leslie, Dahlia and Lidong for their contributions!
Column 37 Table of Contents
Column 36 Table of Contents
"BFTW3: Why? When? Where? Workshop on the Theory and Practice of Byzantine Fault Tolerance" by Petr Kuznetsov and Rodrigo Rodrigues
"Reliability and Security inWireless Networks" by Seth Gilbert and Dariusz R. Kowalski
"Theoretical Aspects of Dynamic Distributed Systems" by Roberto Baldoni and Alexander A. Shvartsman
"Game-Theoretic Aspects of Distributed Computing" by Chryssis Georgiou
Column 35 Table of Contents
Our main contribution is by Ken Birman, Gregory (Grisha) Chockler, and Robbert van Renesse, who identify a research agenda for cloud computing, based on insights gained at the 2008 LADIS workshop. They question whether contemporary research in distributed computing, which sometimes targets cloud environments, is indeed relevant for cloud computing. Some researchers will be disappointed by (and might disagree with) the conclusions they reach. They then proceed to define a new agenda for cloud computing research. Their article, however, does not consider issues of security and trust. This perhaps stems from the fact that the paper is written from the perspective of cloud service providers, rather than users, whereas trust is a concern for the latter. In the next contribution, Christian Cachin, Yours Truly, and Alexander (Alex) Shraer examine the trust that users have (or can have) in cloud services where they store their data, surveying risks as well as solutions that are being proposed to address them.
The column then turns to a more applied perspective. The next contribution, by Edward (Eddie) Bortnikov from Yahoo! Research, surveys open source technologies that are used for web-scale computing, highlighting some technology transfer from the research community to actual implementations. The column concludes with an announcement, provided by Roger Barga and Jose Bernabeu-Auban from Microsoft, about a Cloud Computing tutorial that will be given at DISC'2009 in September, in Elche, Spain.
Many thanks to Ken, Grisha, Robbert, Christian, Alex, Eddie, Roger, and Jose for their contributions!
Column 34 Table of Contents
This column looks at the multi-core programming problem from an educational perspective. How can those among us who teach, help students become comfortable with concurrency? A workshop on this very topic, organized by Nir Shavit, will take place on March 8, co-located with ASPLOS'09. I include here an announcement about the workshop, as provided by Nir.
The column then proceeds with a review, by Danny Hendler, of the book ``Synchronization Algorithms and Concurrent Programming'' by Gadi Taubenfeld. Danny discusses how material from the book can be used in both undergraduate and graduate courses. The next contribution, by Alan Fekete, tackles concrete questions of curriculum design: What courses in the undergraduate computer science curriculum should deal with concurrency? What should be taught about concurrency? and how? As might be expected, there are no definite answers to these questions, yet Alan provides a through discussion of the pros and cons of various approaches and what works well in different contexts. Alan also surveys related results from the Computer Education literature. The column concludes with Leslie Lamport's high-level vision of how computer scientists should learn to think about computations, both serial and concurrent. This thought-provoking article takes a step back from the details of where, what, and how, and makes a case for the high level goal of teaching students how to think clearly. Many thanks to Danny, Alan, and Leslie for their contributions!
Column 33 Table of Contents
I then proceed with reviews of PODC- the ACM Symposium on Principles of Distributed Computing- and its European counterpart, DISC- the International Symposium on DIStributed Computing. I decided to also include a review of SPAA- the ACM Symposium on Parallelism in Algorithms and Architectures- since the boundaries between distributed and parallel computing are quite blurred these days: SPAA increasingly deals with classical distributed computing topics such as network (and graph) algorithms, while PODC and DISC continue to deal extensively with concurrent and shared memory-based computing, which arises in parallel architectures.
To review these three events, I invited students who have won Best Paper and Best Student Paper Awards in the respective conferences (PODC, DISC, and SPAA). I also asked them to include descriptions of their winning papers in their reviews.
The review of PODC is by Armando Castaneda from Universidad Nacional Autonoma de Mexico, who won the Best Student Paper Award for his paper ``New Combinatorial Topology Upper and Lower Bounds for Renaming'', co-authored with his advisor Sergio Rajsbaum. This remarkable paper refutes a long-standing lower bound result on wait-free renaming, which was proven in a number of papers, including a Godel Award winner. More specifically, the paper shows that the previously proven lower bound does not hold for all values of n, where n is the number of processes, while for other values of n it does hold. (See more below). PODC was co-located with CONCUR this year, and featured a special symposium to celebrate the contributions of Nancy Lynch in light of her sixtieth birthday. See more on the celebration (and a picture) in Armando's review of PODC below.
DISC is reviewed by the winners of two awards: Robert Danek and Wojciech Golab from the University of Toronto, who won the Best Paper Award for their paper ``Closing the Complexity Gap Between FCFS Mutual Exclusion and Mutual Exclusion'', and Wojciech Wawrzyniak from Adam Mickiewicz University in Poland, who won the Best Student Paper Award for the paper ``Fast distributed approximations in planar graphs'' he co-authored with M. Hanckowiak and A. Czygrinow. The winning papers are discussed in the review below.
The review of SPAA is by Zvika Guz from the Technion, winner of SPAA's Best Paper Award, for the paper ``Utilizing Shared Data in Chip Multiprocessors with the Nahalal Architecture'', which he co-authored with Yours Truly, Avinoam Kolodny, and Uri Weiser, and discusses in his review of SPAA below.
Of course, these reviews do not cover all the interesting events where distributed computing is studied; distributed computing papers appear in numerous additional conferences. While it is clearly impossible to cover all the relevant venues in this column, I do try to provide a taste of this wide variety. For example, a recent column (Column 30, SIGACT News 39(2)), has surveyed distributed computing research in systems conferences (SOSP and OSDI). In the current column, I chose to highlight another community that dabbles in distributed computing-- the dependability community. To this end, I include a review by Gabi (Gabriel) Kliot of distributed computing papers in DSN 2008-- the International Conference on Dependable Systems and Networks.
In all four reviews, you will find fun information about the venues,
as well as technical content. Many thanks to Gadi, Armando, Robert,
Wojciech, Wojciech, Zvika and Gabi for their colorful contributions!
Column 32 Table of Contents
First, Anne Broadbent and Alain Tapp provide a broad overview of distributed computations and multi-party protocols that can benefit from quantum mechanics, most notably from entanglement. Some of these are unsolvable with classical computing, for example, pseudo-telepathy. In other cases, like appointment scheduling, the problem's communication complexity can be reduced by quantum means.
Next, Vasil Denchev and Gopal Pandurangan critically examine the joint future of quantum computers and distributed computing, asking whether this is a new frontier ... or science fiction. They give background to the lay reader on quantum mechanics concepts that provide added value over classical computing, (again, entanglement figures prominently). They also elaborate on the practical difficulties of implementing them. They then illustrate how these concepts can be exploited for two goals: (1) to distribute centralized quantum algorithms over multiple small quantum computers; and (2) to solve leader election in various distributed computing models. They conclude that the jury is still out on the cost-effectiveness of quantum distributed computing.
Both surveys outline open questions and directions for future
Many thanks to Anne, Alain, Vasil and Gopal for their contributions!
Column 31 Table of Contents
Not surprisingly, the “systems” research community follows a similar trend, and increasingly focuses on distributed systems, distributed storage, and parallel computing. Topics like replication and fault-tolerance, (including Byzantine fault-tolerance), which have been studied in distributed computing conferences like PODC and DISC for a couple of decades, have now found their way to the mainstream of systems research. Even the SIGOPS Hall of Fame Award, which recognizes the most influential Operating Systems papers, was awarded in 2007 to five distributed computing papers (see below). At the same time, new research topics with a distributed flavor have emerged in response to real-world drives such as peer-to-peer applications, data storage across multiple administrative trust domains, and multi-core architectures.
This column examines how distributed computing principles can (and do) come into play in systems research. I first list the laureates of the 2007 SIGOPS Hall of Fame Award. Next, Allen Clement surveys recent papers in systems conferences (SOSP and OSDI) that employ distributed algorithms. He first discusses how topics that have been studied in the distributed algorithms community are now used in systems research, and then overviews new topics that are treated in both communities, albeit differently. Allen also points out where future research on foundations of distributed computing can help advance the field.
The bulk of this column is by Roy Friedman, Anne-Marie Kermarrec, and Michel Raynal, who discuss the important principle of modularity in distributed systems. They illustrate how this principle has contributed to research in the areas of shared memory-based computing and agreement problems. They then advocate a similar approach for peer-to-peer systems.
Many thanks to Allen, Roy, Anne-Marie, and Michel for their
contributions to this column. Upcoming columns will focus on “quantum
computers meet distributed computing” and on “teaching concurrency”.
Column 30 Table of Contents
This column features three contributions that reflect on the role of Distributed Computing research in the brave new world of multi-processors. What new challenges are raised by the newfound ubiquitous relevance of concurrency? What can we, the Distributed Computing community, do to address them?
The most notable challenge stemming from the shift to multi-core architectures is the difficulty of programming concurrent code. One concept that tackles this challenge is transactional memory, which allows multiple processes (or threads) to concurrently access memory objects with transaction-like consistency semantics. As this concept is already taken seriously by industry, and real-world implementations begin to materialize, one may ask what role the Distributed Computing community has in its continued development. This column provides three different takes on this question.
The first contribution, by Pascal Felber, Christof Fetzer, Rachid Guerraoui, and Tim Harris, questions whether transactions in memory are any different from the well-studied database transactions; and if there are differences, what do they entail? The authors point out some aspects in which conventional database wisdom does not provide adequate answers for transactional memory systems. The second contribution, by Hagit Attiya, is a call for more foundational research, or Theory, for transactional memory. Last but not least, Maurice Herlihy and Victor Luchangco provide their perspective on the role of Distributed Computing in the multi-core revolution. All three highlight some promising research directions.
Many thanks to Hagit, Pascal, Christof, Rachid, Tim, Maurice, and
Victor for their contributions.
Column 29 Table of Contents
The main two conferences in the area of principles of distributed computing, PODC and DISC, took place this summer. This issue is centered around these conferences, and more broadly, distributed computing research as reflected therein, ranging from reviews of this year's instantiations, through influential papers in past instantiations, to examining PODC's place within the realm of computer science.
I begin with a short review of PODC'07, and highlight some ``hot'' trends that have taken root in PODC, as reflected in this year's program. Some of the forthcoming columns will be dedicated to these up-and-coming research topics. This is followed by a review of this year's DISC, by Edward (Eddie) Bortnikov. For some perspective on long-running trends in the field, I next include the announcement of this year's Edsger W. Dijkstra Prize in Distributed Computing, (presented at DISC'07), along with the list of past laureates. The prize is awarded annually to an outstanding paper on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has withstood the text of time and has been evident for at least a decade. This year's winner is ``Consensus in the Presence of Partial Synchrony'' by Dwork, Lynch, and Stockmeyer.
The main part of this issue, contributed by Michael Kuhn and Roger Wattenhofer, is a quest for the ``center'' of computer science, based on ``distances'' between conferences. It further studies the evolution of such distances over time, focusing on theory of computing and distributed computing conferences. Finally, it identifies ``central'' people in these communities. The article extends a more PODC-centered (and quite entertaining) presentation given by Roger at the PODC business meeting.
Many thanks to Eddie, Michael, and Roger for their contributions.
Column 28 Table of Contents
A review of the DISC 2000 Conference by Lisa Higham, and
a routing survey by Cyril Gavoille.
This survey focuses on routing messages in distributed networks with
efficient data structures. After an overview of the various results of
the literature, some interestingly open problems are described.
After some announcements,
the contribution by Idit Keidar and myself titled "On
the Cost of Fault-Tolerant Consensus When There
Are No Faults." This paper considers the
problem in an asynchronous model enriched with unreliable failure
and in the partial synchrony model. It considers algorithms that solve
consensus and tolerate crash failures and/or message omissions. It
tight lower bounds on the number of communication steps performed by
such algorithms in failure-free executions. It presents in a unified
framework a number of related lower bound results. It also illustrates
matching upper bounds, by giving algorithms that achieve the lower
consists of the contribution by Boaz Patt-Shamir "Transmission
of Real-Time Streams," that
thatsurveys some of the interesting
This issue consists of
four parts: a survey of SIROCCO'01 by Pierre Fraigniaud, a survey
POMC'01 by Rui Fan,
a survey of SIROCCO'01 by Pierre Fraigniaud, a survey
POMC'01 by Rui Fan,
This year was the 20-th
anniversary of PODC, and included a special celebration honoring the
of Leslie Lamport, on the occasion of his 60th
"At the PODC 2001 conference, I got tired of everyone saying how difficult it was to understand the Paxos algorithm, published in . Although people go so hung up in the pseudo-Greek names that they found the paper hard to understand, the algorithm itself is very simple. So, I cornered a couple of people at the conference and explained the algorithm to them orally, with no paper. When I got home, I wrote down the explanation as a short note, which I later revised based on comments from Fred Schneider and Butler Lampson. The current version is 13 pages long, and contains no formula more complicated than n1 > n2."
This issue consists of two parts: a survey of DISC'01 by Panagiota Fatourou, and a survey of Self-Stabilization at WSS'01 and DISC'01 by Ted Herman.
This issue consists of three parts:
Announcements about PODC 2002, 2003, 2004 and 2005 by Gil Neiger
The paper "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services" by Seth Gilbert and Nancy Lynch
The survey "Topology
and Routing in Ad hoc Networks: a Survey" by Rajmohan Rajaraman
The abstract for Gilbert and Lynch paper is the following. When designing distributed web services, there are three properties that are commonly desired: consistency, availability, and partition tolerance. It is impossible to achieve all three. In this note, they prove this conjecture in the asynchronous network model, and then discuss solutions to this dilemma in the partially synchronous model.
The survey by Rajaraman
consists of the following parts. First various
relevant to modeling ad hoc networks are described. Then topology control
is discussed. Since the nodes of an ad hoc
network are often associated with points in 2-dimensional space,
control is closely tied to computational geometry; this relationship
and extant work in the area are briefly reviewed. Next, routing protocols
for ad hoc networks are discussed. After
a brief overview of the many protocols that have been proposed,
approaches based on the adversarial network model are discussed.
This issue consists of the paper:
"Distributed Computing Research Issues in Grid Computing" by Henri Casanova
Abstract: Ensembles of distributed, heterogeneous resources, or Computational
Grids, have emerged as popular platforms for deploying large-scale
and resource-intensive applications. Large collaborative efforts are
underway to provide the necessary software infrastructure. Grid
raises challenging issues in many areas of computer science, and
in the area of distributed computing, as Computational Grids
cover increasingly large networks and span many organizations. In this paper we briefly motivate Grid
computing and introduce its basic concepts. We then highlight a number
of distributed computing research questions, and discuss both the
relevance and the shortcomings of previous research results when
applied to Grid computing.
Volume 33, Number 4, (Whole Number
This issue consists of the paper:
"Incentives and Internet Computation" by Joan Feigenbaum and Scott Shenker
Abstract: The emergence of the Internet as a standard platform for distributed computing has led to diversification of the research agenda in distributed algorithms, and that agenda now consists of much more than traditional, core PODC concerns. If distributed algorithms are to be designed, analyzed, implemented, and deployed for the full range of applications that are now plausible, the research community will need to develop new computational models, new failure models, new measures of computational complexity, and new analysis techniques. This column is intended as an introduction to one theme that has grown steadily in popularity and importance during the past few years: the
recognition that participants in an Internet algorithm are economic actors as well as computational processes.
- Volume 34, Number 1, (Whole Number 126), March 2003
This issue consists of the paper:
Abstract: The celebrated Paxos algorithm of Lamport implements a fault-tolerant deterministic service by replicating it over a distributed message-passing system. This paper presents a deconstruction of the algorithm by factoring out its fundamental algorithmic principles within two abstractions: an eventual leader election and an eventual register abstractions. In short, the leader election abstraction encapsulates the liveness property of Paxos whereas the register abstraction encapsulates its safety property. Our deconstruction is faithful in that it preserves the resilience and efficiency of the original Paxos algorithm in terms of stable storage logs, message complexity, anc communication steps. In a companion paper, we show how to use our abstractions to reconstruct powerful variants of Paxos
- Volume 34, Number 2, (Whole Number 127), August 2003
Abstract: The celebrated Paxos algorithm of Lamport implements a fault-tolerant deterministic service by replicating it over a distributed message-passing system. In the previous column the authors presented a deconstruction of the algorithm by factoring
- "Reconstructing Paxos" by Romain Boichat, Partha Dutta, Svend Frolund, and Rachid Guerraoui
out its fundamental algorithmic principles within two abstractions:
an eventual leader election and an eventual register abstractions.
Using those abstractions, they show in this paper how to reconstruct, in a modular manner, powerful variants of Paxos. In particular, they show how to (1) alleviate the need for stable storage access if some processes remain up for sufficiently long, (2) augment the resilience of the algorithm against unstable processes, (3) enable single process decision with shared commodity disks, and (4) reduce the number of communication steps during stable periods of the system.
- Volume 34, Number 3, (Whole Number 128), SeptemberAugust 2003
This issue consists of the paper
Abstract: In this note, we discuss the applications of lattice theory to solving
- "Applications of Lattice Theory to Distributed Computing" by Vijay Garg, Neeraj Mittal, and Alper Sen.
problems in distributed systems. The first problem we consider is that of detecting a predicate in a computation, i.e., determining whether there exists a consistent cut of the
computation satisfying the given predicate. The second problem involves computing the slice of a computation with respect to a predicate. A slice is a concise representation of all those global states of the computation that satisfy the given predicate. The third problem we consider is that of analyzing a partial order trace of a distributed program to determine whether it satisfies the given temporal logic formula. Finally, we consider the problem of timestamping events and global states of a computation to capture the order relationship. We discuss how the results from lattice theory can be used in solving each of the above problems.
- Volume 34, Number 4, (Whole Number 129), December 2003August 2003
This issue describes the PODC 20th anniversary Special Issue published by
Distributed Computing journal.
Abstract: The 20th ACM Principles of Distributed Computing (PODC) conference was held in 2002. To celebrate this event, Hagit Attiya and myself edited a special issue of the journal Distributed Computing, with the
support and encouragement of its editor, Vassos Hadzilacos. We invited
contributions from the community, including surveys, retrospectives,
new results, and personal perspectives. We ended up with nine papers, described here.
- Volume 35, Number 2, (Whole Number 131), August 2004
This issue consists of the paper
Abstract: Many distributed algorithms are designed for a system with a fixed set of n processes. However, some systems may dynamically change and expand over time, so that the number of processes may grow to infinity as time tends to infinity. This paper considers such systems, and gives algorithms that are new and simple (but not necessarily efficient) for common problems. The reason for simplicity is to better expose some of the algorithmic techniques for dealing with infinitely many processes. A brief summary of existing work in the subject is also provided.
- "A Pleasant Stroll through the Land of Infinitely Many Creatures" by Marcos Aguilera.
- Volume 35, Number 3, (Whole Number 132), September 2004
This issue consists of:
- An eulogy in memory of Shimon Even, who passed away on May 1st, 2004. He was a highly influential educator, and played a major role in establishing computer science education in Israel. He did pioneering work in various areas, including parallel and distributed computing. As Oded Goldreich says in his PODC 2004 proceedings eulogy, Shimon Even was a great scientist and a remarkable person. His attitudes toward research have influenced anybody who was fortunate to have an interaction with him, he always followed his own judgment and understanding, rather than the common trend or fashion. He sought simple solutions that uncover the essence of the problem . He spent much time seeking the best way to present his own work as well as the work of others in lectures and writing. This quote comes to mind, about having found a good problem to work on.
Not that I quite know indeed what situations the seeking fabulist does "find'' ; he seeks them enough assuredly, but he discoveries are, like those of the navigator, the chemist, the biologist, scarce more than alert recognitions. He comes upon the interesting thing as Columbus came upon the isle of San Salvador, because he had moved in the right direction for it---also because he knew, with the encounter, what "making land'' then and there represented. -- Henry James
- The 2004 Godel Prize is great news for the distributed computing community: it is shared between two journal papers that discovered a fundamental relation between distributed computing and topology, by Maurice Herlihy and Nir Shavit, and Michael Saks and Fotios Zaharoglou. To celebrate this, I am happy to present personal perspectives by the authors of these papers, and by Elizabeth Borowsky and Eli Gafni, that coauthored a third paper with the discovery, but only in a conference and hence not eligible for the prize. I include perspectives also by other people that produced seminal work on the same subject: Soma Chaudhuri and Shlomo Moran.
The DISC conference is collocated this year, 2004, with GETCO, a workshop on topological methods in concurrency and distributed computing. They will dedicate a joint session to celebrate the prize.
- Volume 35, Number 4, (Whole Number 133), December 2004
This issue consists of:
- An eulogy in memory of Larry Stockmeyer, who passed away on July 31, 2004. Larry did pioneering work in various areas, such as complexity theory, logic, interactive proofs, distributed computing, parallel computing, secure architectures, database privacy, and storage systems. A celebration of Larry's work will be held May 21-22, 2005, in conjunction with STOC 2005 (May 22-24). On May 21, a tutorial by Nick Pippenger (Princeton) on some of Stockmeyer's fundamental results in complexity theory will be followed by lectures by Miki Ajtai (IBM), Anne Condon (UBC), Cynthia Dwork (Microsoft), Richard Karp (UC Berkeley), Albert Meyer (MIT), and Chris Umans (CalTech). Some time will be reserved for personal remarks. If you wish to speak in this part of Larry's commemoration contact Cynthia Dwork (firstname.lastname@example.org). The celebration of Stockmeyer's work will conclude on May 22, with Lance Fortnow giving a keynote address to STOC.
- The survey "Distributed Approximation" by Michael Elkin. Considerable progress has been recently achieved in designing efficient distributed approximation algorithms,
and in demonstrating hardness of distributed approximation for various problems. An overview of the research in this area is presented, including several directions for future research.
This issue consists of:
- "A Short Introduction to Failure Detectors for Asynchronous Distributed Systems,'' an introductory survey by Michel Raynal for readers who want to quickly understand the aim, the basic principles, the power and limitations of the failure detector concept.
- Volume 36, Number 2, (Whole Number 135), June 2005
This issue consists of:
- "Algorithmic Foundations of the Internet,'' a survey by Alejandro LÃ³pez-Ortiz.
- Volume 36, Number 3, (Whole Number 136), September 2005
This issue consists of:
- A review of the SIROCCO conference held in Mont Saint Michel, France, May 23-26, 2005, by Corentin Travers.
- Volume 36, Number 4, (Whole Number 137), December 2005
This issue consists of:
- A review of the DISC conference held in September 26-29, 2005, in Cracow, Poland, by Dariusz Kowalski.
- Volume 37, Number 1, (Whole Number 138), March 2006
This issue consists of:
- “Travelling through Wormholes: a new look at Distributed Systems Models,” by Paulo E. Veríssimo.
Abstract: The evolution of distributed computing and applications has put new challenges on models, architectures and systems. The time facet is explored here, reviewing past and present of distributed systems models, and making the case for the use of hybrid models, as a key to overcoming some of the difficulties faced when asynchronous models meet timing specifications. The Wormholes paradigm is described as the first experiment with hybrid distributed systems models.
Volume 37, Number 2, (Whole Number 139), June 2006
This issue consists of:
- “Distributed Computing in India,” by Sukumar Ghosh.
Volume 37, Number 3, (Whole Number 140), September 2006
This issue consists of:
- "Want Scalable Computing? Speculate!," by Idit Keidar and Assaf Schuster.
Abstract: Distributed computing is currently undergoing a paradigm shift, towards large-scale dynamic systems, where thousands of nodes collaboratively solve computational tasks. Examples of such emerging systems include autonomous sensor networks, data-grids, wireless meshnetwork (WMN) infrastructures, and more. We argue that speculative computations will be instrumental to successfully performing meaningful computations in such systems. Moreover, solutions deployed in such platforms will need to be as local as possible.
- "Security and Composition of Cryptographic Protocols: A Tutorial, (Part I)," by Ran Canetti.
Abstract: What does it mean for a cryptographic protocol to be "secure"? Capturing the security requirements of cryptographic tasks in a meaningful way is a slippery business: On the one hand, we want security criteria that prevent
"all potential attacks" against a protocol; on the other hand, we want our criteria not to be overly restrictive and accept "reasonable protocols." One of the main reasons for flaws is the often unexpected interactions among different protocol instances that run alongside each other in a composite system.
This tutorial studies a general methodology for defining security of cryptographic protocols. The methodology, often dubbed the "ideal model paradigm," allows for defining the security requirements of a large variety of cryptographic tasks in a unified and natural way. We first review more basic formulations that capture security in isolation from other protocol instances. Next we address the security problems associated with protocol composition, and review formulations that guarantee security even in composite systems.
Volume 37, Number 4, (Whole Number 141), December 2006
This issue consists of:
- "Security and Composition of Cryptographic Protocols: A Tutorial (Part II)," by Ran Canetti.
Abstract: What does it mean for a cryptographic protocol to be "secure"? Capturing the security requirements of cryptographic tasks in a meaningful way is a slippery business: On the one hand, we want security criteria that prevent "all potential attacks" against a protocol; on the other hand, we want our criteria not to be overly restrictive and accept those protocols that do not succumb to attacks. The first part of this two-part tutorial presented a general methodology for defining security of cryptographic protocols. The methodology, often dubbed the "trusted party paradigm," allows for defining the security requirements of a large variety of cryptographic tasks in a unified and natural way. We also reviewed a basic formulation of this paradigm. The second part, presented here, concentrates on the often subtle security concerns that arise under protocol composition, namely when a protocol runs alongside other protocols in a larger system. We first assert the limitations of the basic formulation from Part I (in this column of SIGACT News: Volume 37, Number 3, (Whole Number 140), September 2006), in this setting; Next we present a stronger formulation and study its security-preserving composability properties.
Volume 38, Number 1, (Whole Number 142), March 2007
This issue consists of:
- A review of the DISC 2006 conference by Shlomi Dolev, followed by "DISC at its 20th anniversary: Past, Present and Future," by Michel Raynal, Sam Toueg, and Shmuel Zaks.
Abstract: DISC, the International Symposium on DIStributed Computing (formerly WDAG), is an annual forum for presentation of research on all facets of distributed computing, including the theory, design, analysis, implementation, and application of distributed systems and networks. The 20th anniversary edition of DISC was held on September 18-20, 2006, in Stockholm Sweden, attracting approximately one hundred participants. The invited speakers were: Leslie Lamport, Nancy Lynch and Michael Rabin, and a panel by Eli Gafni, Jan van Leeuwen, Michel Raynal, Nicola Santoro and Shmuel Zaks (who were the PC members of the second WDAG, Amsterdam, 1987).
- "Harmful dogmas in fault tolerant distributed computing," by Bernadette Charron-Bost and André Schiper.
Abstract: Consensus is a central problem in fault tolerant distributed computing. A vast number of (positive and negative) results for consensus in various system models have been established. In this paper we isolate three features that all these system models share, and we show that inappropriate modelling choices have led to overcomplicate the approaches to studying the consensus problem, thus yielding too restrictive solutions for real systems.
It is hard to question these modelling choices, as they have gained the status of dogmas. Nevertheless, we propose a simpler and more natural approach that allows us to get rid of these dogmas, and to handle all types of benign fault, be it static or dynamic, permanent or transient, in a unified framework.
Volume 38, Number 2, (Whole Number 143), June 2007
This issue consists of "A Collection of Kinesthetic Learning Activities for a Course on Distributed Computing", by Paolo Sivilotti and Scott Pike.
Volume 38, Number 3, (Whole Number 144), September 2007
This issue consists of "Delayed Password Disclosure", by Markus Jakobsson and Steven Myers.