ACM SIGACT News Distributed Computing ColumnIdit Keidar, EditorSergio Rajsbaum, previous Editor (until September 2007) |
||||
|
|
New columns (from Dec 2007) |
|
Archive (2000-2007) |
|
|---|
| Introduction | 64 |
| "Barbara Liskov's Turing Award" by Rodrigo Rodrigues | 68 |
| Prize for Innovation in Distributed Computing 2009: Nicola Santoro | 69 |
| "A Review of PODC 2009" by Keren Censor and Christoph Lenzen | 71 |
| "A Review of DISC 2009" by Andreas Tielmann | 75 |
| DISC 2009 Workshops | 79 |
"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 |
|
| "Review of SIROCCO 2009" by Shantanu Das | 93 |
| Introduction | 77 |
| "Building Reliable Large-Scale Distributed Systems: When Theory Meets Practice" by Lidong Zhou | 78 |
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!
| Introduction | 67 |
| "Toward a Cloud Computing Research Agenda" by Ken Birman, Gregory Chockler, and Robbert van Renesse | 68 |
| "Trusting the Cloud" by Christian Cachin, Idit Keidar, and Alexander Shraer | 81 |
| "Open-Source Grid Technologies for Web-Scale Computing" by Edward Bortnikov | 87 |
| "Cloud Computing Architecture and Application Programming" by Roger Barga, Jose Bernabeu-Auban, Dennis Gannon, and Christophe Poulain | 94 |
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!
| Introduction | 45 |
| Workshop on Directions in Multicore Programming Education | 46 |
| A Review of ``Synchronization Algorithms and Concurrent Programming'' by Gadi Taubenfeld, reviewed by Danny Hendler | 47 |
| "Teaching about Threading: Where and What?" by Alan Fekete | 51 |
| "Teaching Concurrency" by Leslie Lamport | 58 |
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
| Introduction | 53 |
| The 2008 Edsger W. Dijkstra Prize in Distributed Computing | 54 |
| "A Review of PODC 2008" by Armando Castaneda | 56 |
| "Review of DISC 2008" by Robert Danek, Wojciech Golab, and Wojciech Wawrzyniak | 61 |
| "Review of SPAA'08" by Zvika Guz | 67 |
| "Review of DSN'08" by Gabriel Kliot | 70 |
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
research.
Many thanks to Anne, Alain, Vasil and Gopal for their contributions!
Column 31 Table of Contents
| Introduction | 66 |
| "Can Quantum Mechanics Help Distributed Computing?" by Anne Broadbent and Alain Tapp | 67 |
| "Distributed Quantum Computing: A New Frontier in Distributed Systems or Science Fiction?" by Vasil Denchev and Gopal Pandurangan | 77 |
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
| 2007 SIGOPS Hall of Fame Award | 83 |
| "Distributed Computing in SOSP and OSDI" by Allen Clement | 84 |
| "Modularity: a First Class Concept to Address Distributed Systems" by Roy Friedman, Anne-Marie Kermarrec, and Michel Raynal | 91 |
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
| "Transactions are back - but are they the same? ``Le Retour de Martin Guerre'' (Sommersby)" by Pascal Felber, Christof Fetzer, Rachid Guerraoui, and Tim Harris | 48 |
| "Needed: Foundations for Transactional Memory" by Hagit Attiya | 59 |
| "Distributed Computing and the Multicore Revolution" by Maurice Herlihy and Victor Luchangco | 62 |
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
After some announcements,
this
This
This issue consists of
four parts:
This year was the 20-th
anniversary of PODC, and included a special celebration honoring the
work
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 [115]. 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
Control
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
aspects
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,
topology
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,
alternative
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
currently
underway to provide the necessary software infrastructure. Grid
computing
raises challenging issues in many areas of computer science, and
especially
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
125), December
2002
Postcript
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.
Postcript
- Volume 34, Number 1, (Whole Number 126), March 2003
Postcript
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
Postcript
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
Postcript
This issue consists of the paperAbstract: 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
Postcript
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
Postcript
This issue consists of the paperAbstract: 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
Postcript
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
Postcript
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 (dwork@microsoft.com). 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.
Postcript
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
Postcript
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.