Bibliography

Issues in distributed and mobile data and software

This page contains references relevant to the 'Issues in distributed and mobile data and software' seminar. Please let me know if you would like to add a reference, abstract, summary, or something or if something is not working.

Most of the papers have been listed with their abstract. To decrease clutter those abstracts are 'hidden', but they can be shown by clicking on the -symbol, and subsequently hidden again by clicking on the -symbol. In addition it is possible to show or hide all abstracts.

Show All | Hide All

Introduction

[WWWK94]: Jim Waldo, Geoff Wyant, Ann Wollrath, Sam Kendall, "A Note on Distributed Computing", Sun Technical Report TR-94-29, 1994.
Abstract:

We argue that objects that interact in a distributed system need to be dealt with in ways that are intrinsically different from objects that interact in a single address space. These differences are required because distributed systems require that the programmer be aware of latency, have a different model of memory access, and take into account issues of concurrency and partial failure.

We look at a number of distributed systems that have attempted to paper over the distinction between local and remote objects, and show that such systems fail to support basic requirements of robustness and reliability. These failures have been masked in the past by the small size of the distributed systems that have been built. In the enterprise-wide distributed systems foreseen in the near future, however, such a masking will be impossible.

We conclude by discussing what is required of both systems-level and application-level programmers and designers if one is to take distribution seriously.

XML Stores

Main readings:

[TBF2002]: Tine Thorn, Anders Baumann, Mikkel Fennestad, "A Distributed, Value-Oriented XML Store", Master's thesis, ITU, 2002.
Abstract:

The XML Store is a distributed, value-oriented storage facility for storing XML documents. This thesis demonstrates that it is possible to design and implement an XML Store based on a peer-to-peer distributed file system. The distributed file system is based on Chord, a routing and location protocol developed at MIT, and provides a distributed hash table for storage of data. The Chord protocol is highly scalable as it looks up data in time logarithmic in the number of servers and requires only logarithmic space for routing information at each node.

The term value-oriented denotes a style of programming where all data are considered immutable. When storing XML documents we employ a storage strategy, splitting XML documents up according to their inherent tree structure. Each subdocument is considered a value and stored separately in the distributed file system. This storage strategy offers many advantages over conventional text based technologies such as SAX and DOM, the most important being the possibility to obtain sharing of identical subdocuments.

We present a simple and flexible value-oriented API for representing and manipulating XML documents. It takes advantage of sharing and uses the proposed storage strategy to handle manipulation of XML documents without having to read and parse the entire document into memory. The value-oriented approach makes it easier to maintain several document versions and simplifies usually complex problems in distributed systems, such as transaction handling, caching- and replication management.

The implemented prototype has been subjected to extensive performance experiments. The experiments demonstrate the superiority of the value-oriented approach when storing modifications of documents. The experiments show that the time taken to store a document is mostly dependant on the number of nodes in a document, and to a lesser degree the size of the nodes. The experiments furthermore reveal that the XML Store prototype does not perform well when storing nodes. This is probably due to the somewhat rough and unoptimised implementation of network communication. With a better implementation it is plausible that the XML Store can be much more efficient, since related systems based on the Chord protocol achieve performance comparable to FTP.

Supplementary readings:

[Tej2002]: Jesper Tejlgaard Pedersen and Kasper Bøgebjerg Pedersen, "Value-oriented XML Store", Master's thesis, DTU, 2002.
Abstract:

XML Store is a distributed value-oriented storage facility for storing XML documents. XML documents stored in XML Store can be accessed and manipulated using the Document Value Model (DVM). This thesis illustrates that such a storage facility can be constructed. The value-oriented programming model, proposed have shown advantages over traditional imperative models for working with persisted and distributed XML document. These advantages are easy caching and replication (as no coherence protocols are needed), lazy loading of documents, transparent persistence and distribution and sharing of documents.
[Bøg2002]: Kasper Bøgebjerg Pedersen and Jesper Tejlgaard Pedersen, "Value-oriented XML Store", Master's thesis, ITU, 2002.
Abstract:

This thesis presents a distributed value-oriented storage facility for storing XML documents called XML Store. XML documents stored in XML Store can be accessed and manipulated using an API, called the Document Value Model (DVM). Value oriented programming is programming with immutable values and references to values.

This thesis identifies key concepts in designing an implementing such a storage facility.

The XML Store prototype presented in this thesis is evaluated by building a sample application and performance testing.

Evaluation showed that the value-oriented programming model have advantages over the traditional imperative model, when programming distributed XML applications.

File systems

Main readings:

[Tho78]: Ken Thompson, "unix Time-Sharing System: unix Implementation", Bell System Technical Journal, vol. 57(6), 1931-1946, 1978.
Abstract:

This paper describes in high-level terms the implementation of the resident unix† kernel. This discussion is broken into three parts. The first part describes how the unix system views processes, users, and programs. The second part describes the I/O system. The last part describes the unix file system.
[MJLF84]: Marshall K. McKusick, William N. Joy, Samuel J. Leffler, and Robert S. Fabry, "A Fast File System for unix". ACM Transactions on Computer Systems, Vol. 2, No. 3, 1984, pp. 181--197.
Abstract:

A reimplementation of the unix file system is described. The reimplementation provides substantially higher throughput rates by using more flexible allocation policies that allow better locality of reference and can be adapted to a wide range of peripheral and processor characteristics. The new file system clusters data that is sequentially accessed and provides two block sizes to allow fast access to large files while not wasting large amounts of space for small files. File access rates of up to ten times faster than the traditional unix file system are experienced. Long needed enhancements to the pro-grammers interface are discussed. These include a mechanism to place advisory locks on files, extensions of the name space across file systems, the ability to use long file names, and provisions for administrative control of resource usage.
[RO92]: Mendel Rosenblum and John K. Ousterhout, "The Design and Implementation of a Log-Structured File System", ACM Transactions on Computer Systems, vol. 10(1), 26-52, 1992.
Abstract:

This paper presents a new technique for disk storage management called a log-structured file system. A log-structured file system writes all modifications to disk sequentially in a log-like structure, thereby speeding up both file writing and crash recovery. The log is the only structure on disk; it contains indexing information so that files can be read back from the log efficiently. In order to maintain large free areas on disk for fast writing, we divide the log intosegmentsand use a segment cleaner to compress the live information from heavily fragmented segments. We present a series of simulations that demonstrate the efficiency of a simple cleaning policy based on cost and benefit. We have implemented a prototype log-structured file system called Sprite LFS; it outperforms current unix file systems by an order of magnitude for small-file writes while matching or exceeding unix performance for reads and large writes. Even when the overhead for cleaning is included, Sprite LFS can use 70% of the disk bandwidth for writing, whereas unix file systems typically can use only 5-10%.

Supplementary readings:

[BHS95]: Trevor Blackwell, Jeffrey Harris, and Margo Seltzer, "Heuristic Cleaning Algorithms for Log-Structured File Systems", Proceedings of the 1995 Usenix Technical Conference, 1995.
[Kle86]: S. R. Kleiman, "Vnodes: An Architecture for Multiple File System Types in Sun unix". Proceedings of the 1986 Usenix Conference, June 1986, pp. 238--247.
[MK91]: L. McVoy and S. Kleiman, "Extent-like Performance from a UNIX File System". Proceedings of the 1991 Winter Usenix Conference, 1991.
[MRCWA97]: Jeanna Neefe Matthews, Drew Roselli, Adam M. Costello, Randolph Y. Wang, and Thomas E. Anderson, "Improving the Performance of Log-Structured File Systems with Adaptive Methods", Proceedings of the Sixteenth Symposium on Operating Systems Principles, 1997.
[SBMS93]: Margo Seltzer, K. Bostic, Marshall K. McKusick, and Carl Staelin, "An Implementation of A Log-Structured File System for unix", Proceedings of the 1993 Winter Usenix Conference, 1993.
[SSBCMP95]: Margo Seltzer, Keith A. Smith, Hari Balakrishnan, Jacqueline Chang, Sara McMains, Venkata Padmanabhan, "File System Logging versus Clustering: A Performance Comparison", Proceedings of the 1995 Usenix Technical Conference, 1995.

Modern, journaling file systems:

[Twe98]: Stephen C. Tweedie, "Journaling the Linux ext2fs Filesystem", LinuxExpo 98.
Abstract:

This paper describes a work-in-progress to design and implement a transactional metadata journal for the Linux ext2fs filesystem. We review the problem of recovering filesystems after a crash, and describe a design intended to increase ext2fs s speed and reliability of crash recovery by adding a transactional journal to the filesystem.

File systems resources:

[nondot.org]: "File Systems" (referred September 2002).

Distributed file systems

Main readings:

[LS90]

Eliezer Levy and Abraham Silberschatz, "Distributed File Systems: Concepts and Examples", Computing Surveys, vol 22(4), 1990.

Abstract:

[CDK2001, Chapter 8]

George Coulouris, Jean Dollimore, Tim Kindberg, "Distributed File Systems", Chapter 8 of George Coulouris, Jean Dollimor, Tim Kindberg, "Distributed Systems: Concepts and Design", 3rd edition, Addison-Wesley, 2001.

"Abstract":

Supplementary readings:

[MCM2001]: Athicha Muthitacharoen, Benjie Chen, and David Mazières, "A Low-bandwidth Network File System", In the Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP '01), Chateau Lake Louise, Banff, Canada. October 2001.
Abstract:

Users rarely consider running network file systems over slow or wide-area networks, as the performance would be unacceptable and the bandwidth consumption too high. Nonetheless, efficient remote file access would often be desirable over such networks---particularly when high latency makes remote login sessions unresponsive. Rather than run interactive programs such as editors remotely, users could run the programs locally and manipulate remote files through the file system. To do so, however, would require a network file system that consumes less bandwidth than most current file systems.

This paper presents LBFS, a network file system designed for low-bandwidth networks. LBFS exploits similarities between files or versions of the same file to save bandwidth. It avoids sending data over the network when the same data can already be found in the server's file system or the client's cache. Using this technique in conjunction with conventional compression and caching, LBFS consumes over an order of magnitude less bandwidth than traditional network file systems on common workloads.

Case studies:

[San87]: Russell Sanderg, "The Sun Network Filesystem: Design, Implementation and Experience".
[Sat+90]: Mahadev Satyanarayanan, James J. Kistler, Puneet Kumar, Maria E. Okasaki, Ellen H. Siegel, and David C. Steere, "Coda: A Highly Available File System for a Distributed Workstation Environment", IEEE Trans. on Computers, vol 39(4), 1990.
Abstract:

Coda is a file system for a large-scale distributed computing environment composed of unix workstations. It provides resiliency to server and network failures through the use of two distinct but complementary mechanisms. One mechanism, server replication, stores copies of a file at multiple servers. The other mechanism, disconnected operation, is a mode of execution in which a caching site temporarily assumes the role of a replication site. Disconnected operation is particularly useful for supporting portable workstations. The design of Coda optimizes for availability and performance, and strives to provide the highest degree of consistency attainable in the light of these objectives. Measurements from a prototype show that the performance cost of providing high availability in Coda is reasonable.

Resources:

[Farsite]: Microsoft Farsite pages (referred October 2002).

Basic peer-to-peer systems

Main readings:

[Ora2000]: Andy Oram, "Gnutella and Freenet Represent True Technological Innovation", O'Reilly Network, 2000.
[Napster]: Open Napster, "Napster messages".
[Gnutella]: Distributed Search Solutions, "The Gnutella Protocol Sepcification v0.4".
[CSWH2001]: Ian Clarke, Oskar Sandberg, Brandon Wiley, and Theodore W. Hong, "Freenet: A Distributed Anonymous Information Storage and Retrieval System", in Hannes Federrath (ed), "Designing Privacy Enhancing Technologies: International Workshop on Design Issues in Anonymity and Unobservability", LNCS 2009, Springer, 2001.
Abstract:

We describe Freenet, an adaptive peer-to-peer network application that permits the publication, replication, and retrieval of data while protecting the anonymity of both authors and readers. Freenet operates as a network of identical nodes that collectively pool their storage space to store data files and cooperate to route requests to the most likely physical location of data. No broadcast search or centralized location index is employed. Files are referred to in a location-independent manner, and are dynamically replicated in locations near requestors and deleted from locations where there is no interest. It is infeasible to discover the true origin or destination of a file passing through the network, and difficult for a node operator to determine or be held responsible for the actual physical contents of her own node.
[Rit2001]: Jordan Ritter, "Why Gnutella Can't Scale. No, Really.", 2001.

Distributed garbage collection

Main readings:

[PS95]: David Plainfossé and Marc Shapiro, "A Survey of Distributed Garbage Collection Techniques", International Workshop on Memory Management, Kinross, Scotland (UK), September 1995.
Abstract:

We present the spectrum of distributed garbage collection techniques. We first describe those reference counting-based techniques and compare them, in particular with respect to resilience to message failures. Reference counting-based techniques are acyclic since they are unable to collect cyclic data structures. We then describe a number of hybrid schemes improving over distributed reference counting algorithms in order to collect cyclic garbage. We then describe tracing-based techniques derived from uniprocessor tracing-based techniques. Finally, we discuss the pros and cons of each technique.

Supplementary readings:

[Hug85]: John Hughes, "A Distributed Garbage Collection Algorithm", In Proceedings of the Conference on Functional Programming Languages and Computer Architecture, 1985.
Unfortunately, the paper is not available online (look at the publication date ;-)), but a hard copy can be obtained from the DIKU Library (LNCS 201, pages 256-272) or from Henning's office.
[AR98]: Saleh E. Abdullahi and Graem A. Ringwood, "Garbage collecting the Internet: a survey of distributed garbage collection", Computing Surveys, vol 30(3), 1998.
Abstract:

Internet programming languages such as Java present new challenges to garbage-collection design. The spectrum of garbage-collection schema for linked structures distributed over a network are reviewed here. Distributed garbage collectors are classified first because they evolved from single-address-space collectors. This taxonomy is used as a framework to explore distribution issues: locality of action, communication overhead and indeterministic communication latency.
[UG97]: Christian Ungureanu and Benjamin Goldberg, "Formal models of distributed memory management", In Proceedings of the International Conference Functional Programming, 1997.
Abstract:

We develop an abstract model of memory management in distributed systems. The model is low-level enough so we can express communication, allocation and garbage collection, but otherwise hide many of the lower-level details of an actual implementation.

Recently, such formal models have been developed for memory management in a functional, sequential setting by Morrisett, Felleisen, and Harper. The models are rewriting systems whose terms are programs. Programs have both the "code" (control string) and the "store" syntactically apparent. Evaluation is expressed as conditional rewriting and includes store operations. Garbage collection becomes a rewriting relation that removes part of the store without affecting the behavior of the program.

By using techniques developed for communicating and concurrent systems such as Milner's CCS, we extend the model for a distributed environment. Sending and receiving messages is also made apparent at the syntactic level. A very general garbage collection rule based on reachability is introduced and proved correct. Now, proving correct a specific collection strategy is reduced to showing that the relation between programs defined by the strategy is a subrelation of the general relation. Any actual implementation which is capable of providing the transitions (including their atomicity constraints) specified by the strategy is therefore correct.
[LQP92]: Bernard Lang, Christian Queinnec, and Jose Piquer, "Garbage collecting the world", In Proceedings of Principles of Programming Languages, 1992.
Abstract:

Distributed symbolic computations involve the existence of remote references allowing an object, local to a processor, to designate another object located on another processor. To reclaim inaccessible objects is the non trivial task of a distributed Garbage Collector (GC). We present in this paper a new distributed GC algorithm which (i) is fault-tolerant, (ii) is largely independent of how a processor garbage collects its own data space, (iii) does not need centralized control nor global stop-the-world synchronization, (iv) allows for multiple concurrent active GCs, (v) does not require to migrate objects from processor to processor and (vi) eventually reclaims all inaccessible objects including distributed cycles. These results are mainly obtained through the concept of a group of processors (or processes). Processors of a same group cooperate together to a GC inside this group; this GC is conservative with respect to the outside of the group. A processor contributes to the global GC of all groups to which it belongs. Garbage collection on small groups reclaims quickly locally distributed garbage clusters, while garbage collection on large groups ultimately reclaims widely distributed garbage clusters, albeit more slowly. Groups can be reorganized dynamically, in particular to tolerate failures of some member processors. These properties make the algorithm usable on very large and evolving networks of processors. Other than distributed symbolic computations, possible applications include for example distributed file or database systems.

Uniprocessor garbage collection:

[JL96]: Richard Jones and Rafael Lins, "Garbage collection: Algorithms for Automatic Dynamic Memory Management", Wiley, 1996.
[Wil92]: Paul R. Wilson, "Uniprocessor Garbage Collection Techniques", in International Workshop on Memory Management, 1992.
[Wil95]: Paul R. Wilson, "Uniprocessor Garbage Collection Techniques", to appear in Computing Surveys, 1995.

Peer-to-peer systems: naming and routing

Main readings:

[SMKKB2001]: Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan, "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications", ACM SIGCOMM 2001, 149-160, 2001.
Abstract:

A fundamental problem that confronts peer-to-peer applications is to efficiently locate the node that stores a particular data item. This paper presents Chord, a distributed lookup protocol that addresses this problem. Chord provides support for just one operation: given a key, it maps the key onto a node. Data location can be easily implemented on top of Chord by associating a key with each data item, and storing the key/data item pair at the node to which the key maps. Chord adapts efficiently as nodes join and leave the system, and can answer queries even if the system is continuously changing. Results from theoretical analysis, simulations, and ex-periments show that Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with the number of Chord nodes.
[ZKJ2001]: Ben Y. Zhao and John D. Kubiatowicz and Anthony D. Joseph, "Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing". U. C. Berkeley Technical Report UCB//CSD-01-1141, 2000.
Abstract:

In today s chaotic network, data and services are mobile and replicated widely for availability, durability, and locality. Components within this infrastructure interact in rich and complex ways, greatly stressing traditional approaches to name service and routing. This paper explores an alternative to traditional approaches called Tapestry. Tapestry is an overlay location and routing infrastructure that provides location-independent routing of messages directly to the closest copy of an object or service using only point-to-point links and without centralized resources. The routing and directory information within this infrastructure is purely soft state and easily repaired. Tapestry is self-administering, fault-tolerant, and resilient under load. This paper presents the architecture and algorithms of Tapestry and explores their advantages through a number of experiments.

Supplementary readings:

[Rat+2001]: Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker, "A Scalable Content-Addressable Network", Proc. ACM SIGCOMM 2001.
Abstract:

Hash tables which map keys onto values are an essential build-ing block in modern software systems. We believe a similar functionality would be equally valuable to large distributed systems. In this paper, we introduce the concept of a Content-Addressable Network (CAN) as a dis-tributed infrastructure that provides hash table-like functionality on Internet-like scales. The CAN design is scalable, fault-tolerant and completely self-organizing, and we demonstrate its scalability, robustness and low-latency properties through simulation.
[RD2001a]: Antony Rowstron and Peter Druschel, "Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems", IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), Heidelberg, Germany, pages 329-350, November, 2001.
Abstract:

This paper presents the design and evaluation of Pastry, a scalable, distributed object location and routing substrate for wide-area peer-to-peer applications. Pastry performs application-level routing and object location in a potentially very large overlay network of nodes connected via the Internet. It can be used to support a variety of peer-to-peer applications, including global data storage, data sharing, group communication and naming.

Each node in the Pastry network has a unique identifier (nodeId). When presented with a message and a key, a Pastry node efficiently routes the message to the node with a nodeId that is numerically closest to the key, among all currently live Pastry nodes. Each Pastry node keeps track of its immediate neighbors in the nodeId space, and notifies applications of new node arrivals, node failures and recoveries. Pastry takes into account network locality; it seeks to minimize the distance messages travel, according to a to scalar proximity metric like the number of IP routing hops.

Pastry is completely decentralized, scalable, and self-organizing; it automatically adapts to the arrival, departure and failure of nodes. Experimental results obtained with a prototype implementation on an emulated network of up to 100,000 nodes confirm Pastry s scalability and efficiency, its ability to self-organize and adapt to node failures, and its good network locality properties.

Peer-to-peer systems: storage

Main readings:

[Kub+2000]: John Kubiatowicz, David Bindel, Yan Chen, Steven Czerwinski, Patrick Eaton, Dennis Geels, Ramakrishna Gummadi, Sean Rhea, Hakim Weatherspoon, Westley Weimer, Chris Wells, and Ben Zhao, "OceanStore: An Architecture for Global-Scale Persistent Storage", Appears in Proceedings of the Ninth international Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), November 2000.
Abstract:

OceanStore is a utility infrastructure designed to span the globe and provide continuous access to persistent information. Since this infrastructure is comprised of untrusted servers, data is pro-tected through redundancy and cryptographic techniques. To im-prove performance, data is allowed to be cached anywhere, any-time. Additionally, monitoring of usage patterns allows adapta-tion to regional outages and denial of service attacks; monitoring also enhances performance through pro-active movement of data. A prototype implementation is currently under development.
[DKKMS2001]: Frank Dabek, M. Frans Kaashoek, David Karger, Robert Morris, Ion Stoica, "Wide-Area Cooperative Storage with CFS", Proceedings of the 18th ACM Symposium on Operating Systems Principles, 202-215, 2001.
Abstract:

The Cooperative File System (CFS) is a new peer-to-peer read-only storage system that provides provable guarantees for the ef-ficiency, robustness, and load-balance of file storage and retrieval. CFS does this with a completely decentralized architecture that can scale to large systems. CFS servers provide a distributed hash table (DHash) for block storage. CFS clients interpret DHash blocks as a file system. DHash distributes and caches blocks at a fine granu-larity to achieve load balance, uses replication for robustness, and decreases latency with server selection. DHash finds blocks using the Chord location protocol, which operates in time logarithmic in the number of servers.

CFS is implemented using the SFS file system toolkit and runs on Linux, OpenBSD, and FreeBSD. Experience on a globally de-ployed prototype shows that CFS delivers data to clients as fast as FTP. Controlled tests show that CFS is scalable: with 4,096 servers, looking up a block of data involves contacting only seven servers. The tests also demonstrate nearly perfect robustness and unimpaired performance even when as many as half the servers fail.

Supplementary readings:

[Dab2001]: Frank Dabek, "A Cooperative File System", Master's Thesis, MIT, 2001.
[RD2001b]: Antony Rowstron and Peter Druschel, "PAST: A large-scale, persistent peer-to-peer storage utility",HotOS VIII, Schoss Elmau, Germany, May 2001.
Abstract:

This paper sketches the design of PAST, a large-scale, Internet-based, global storage utility that provides scala-bility, high availability, persistence and security. PAST is a peer-to-peer Internet application and is entirely self-organizing. PAST nodes serve as access points for clients, participate in the routing of client requests, and contribute storage to the system. Nodes are not trusted, they may join the system at any time and may silently leave the system without warning. Yet, the system is able to provide strong assurances, efficient storage access, load balancing and scalability.

Among the most interesting aspects of PAST s design are (1) the Pastry location and routing scheme, which reliably and efficiently routes client requests among the PAST nodes, has good network locality properties and automatically re-solves node failures and node additions; (2) the use of ran-domization to ensure diversity in the set of nodes that store a file s replicas and to provide load balancing; and (3) the op-tional use of smartcards, which are held by each PAST user and issued by a third party called a broker. The smartcards support a quota system that balances supply and demand of storage in the system.

Replication

Main readings:

[CDK2001, Chapter 14]: George Coulouris, Jean Dollimor, Tim Kindberg, "Replication", Chapter 14 of George Coulouris, Jean Dollimor, Tim Kindberg, "Distributed Systems: Concepts and Design", 3rd edition, Addison-Wesley, 2001.
"Abstract":

Replication is a key to providing high availability and fault tolerance in distributed systems. High availability is of increasing interest with the tendency towards mobile computing and consequently disconnected operation. Fault tolerance is an abiding concern for services provided in safety-critical and other important systems.

The first part of the chapter considers systems that apply a single operation at a time to collections of replicated objects. The chapter begins with a description of architectural components and a system model for services that employ replication. We describe the integration of group membership management as part of group communication, which is particularly important for fault-tolerant services.

The chapter then describes approaches to achieving fault tolerance. It introduces the correctness criteria of linearizability and sequential consistency. Then two approaches are introduced and discussed: passive (primary-backup) replication, in which clients communicate with a distinguished replica; and active replication in which client communicate by multicast with all replicas.

Three systems for highly available services are considered. In the gossip and Bayou architectures, updates are lazily propagated between replicas of shared data. In Bayou, the technique of operational transformation is used to enforce consistency. Coda is an example of a highly available file service.

The chapter ends by considering transactions - sequences of operations - upon replicated objects. It considers the architectures of replicated transactional systems and how these systems handle server failures and network partitions.

Supplementary readings:

[Pet+97]: K. Petersen, M. J. Spreitzer, D. B. Terry, M. M. Theimer, and A. J. Demers, "Flexible Update Propagation for Weakly Consistent Replication", Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP-16), Saint Malo, France, October 5-8, 1997, pages 288-301.
Abstract:

Bayou's anti-entropy protocol for update propagation between weakly consistent storage replicas is based on pair-wise communication, the propagation of write operations, and a set of ordering and closure constraints on the propagation of the writes. The simplicity of the design makes the protocol very flexible, thereby providing support for diverse networking environments and usage scenarios. It accommodates a variety of policies for when and where to propagate updates. It operates over diverse network topologies, including low-bandwidth links. It is incremental. It enables replica convergence, and updates can be propagated using floppy disks and similar transportable media. Moreover, the protocol handles replica creation and retirement in a light-weight manner. Each of these features is enabled by only one or two of the protocol's design choices, and can be independently incorporated in other systems. This paper presents the anti-entropy protocol in detail, describing the design decisions and resulting features.
[Ter+95]: D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, M. J. Spreitzer, and C. Hauser, "Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System", Proceedings 15th Symposium on Operating Systems Principles (SOSP-15) , Cooper Mountain, Colorado, December 1995, pages 172-183.
Abstract:

Bayou is a replicated, weakly consistent storage system designed for a mobile computing environment that includes porta- ble machines with less than ideal network connectivity. To maxi- mize availability, users can read and write any accessible replica. Bayou's design has focused on supporting application-specific mechanisms to detect and resolve the update conflicts that natu- rally arise in such a system, ensuring that replicas move towards eventual consistency, and defining a protocol by which the resolu- tion of update conflicts stabilizes. It includes novel methods for conflict detection, called dependency checks, and per-write con- flict resolution based on client-provided merge procedures. To guarantee eventual consistency, Bayou servers must be able to roll- back the effects of previously executed writes and redo them according to a global serialization order. Furthermore, Bayou per- mits clients to observe the results of all writes received by a server, including tentative writes whose conflicts have not been ultimately resolved. This paper presents the motivation for and design of these mechanisms and describes the experiences gained with an initial implementation of the system.
[Her90]: Maurice Herlihy, "Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types", ACM Transactions on Database Systems, vol. 15(1), 96-124, 1990.
Abstract:

An optimistic concurrency control technique is one that allows transactions to execute without synchronization, relying on commit-time validation to ensure serializability. Several new optimistic concurrency control techniques for objects in decentralized distributed systems are described here, their correctness and optimality properties are proved, and the circumstances under which each is likely to be useful are characterized. Unlike many methods that classify operations only as Reads or Writes, these techniques systematically exploit type-specific properties of objects to validate more interleavings. Necessary and sufficient validation conditions can be derived directly from an object's data type specification. These techniques are also modular: they can be applied selectively on a per-object (or even per-operation) basis in conjunction with standard pessimistic techniques such as two-phase locking, permitting optimistic methods to be introduced exactly where they will be most effective. These techniques can be used to reduce the algorithmic complexity of achieving high levels of concurrency, since certain scheduling decisions that are NP-complete for pessimistic schedulers can be validated after the fact in time, independent of the level of concurrency. These techniques can also enhance the availability of replicated data, circumventing certain tradeoffs between concurrency and availability imposed by comparable pessimistic techniques.
[Gra+96]: Jim Gray, Pat Helland, Patrick O'Neil, and Deniis Shasha, "The Dangers of Replication and a Solution", In Proceedings of the ACM SIGMOD Conference, volume 25(2), pages 173-182, 1996.
Abstract:

Update anywhere-anytime-anyway transactional replication has unstable behavior as the workload scales up: a ten-fold increase in nodes and traffic gives a thousand fold increase in deadlocks or reconciliations. Master copy replication (primary copy) schemes reduce this problem. A simple analytic model demonstrates these results. A new two-tier replication algorithm is proposed that allows mobile (discon-nected) applications to propose tentative update transactions that are later applied to a master copy. Commutative update transactions avoid the instability of other replication schemes.
[Pag+98]: T. W. Page Jr., R. G. Guy, J. S. Heidemann, D. H. Ratner, P. L. Reiher, A. Goel, G. H. Kuenning, G. J. Popek, "Perspectives on optimistically replicated, peer-to-peer filing", Software: Practice and Experience, volume 28(2), 1998.
Abstract:

This research proposes and tests an approach to engineering distributed file systems that are aimed at wide-scale, Internet-based use. The premise is that replication is essential to deliver performance and availability, yet the traditional conservative replica consistency algorithms do not scale to this environment. Our Ficus replicated file system uses a single-copy availability, optimistic update policy with reconciliation algorithms that reliably detect concurrent updates and automatically restore the consistency of directory replicas. The system uses the peer-to-peer model in which all machines are architectural equals but still permits configuration in a client-server arrangement where appropriate. Ficus has been used for six years at several geographically scattered installations. This paper details and evaluates the use of optimistic replica consistency, automatic update conflict detection and repair, the peer-to-peer (as opposed to client-server) interaction model, and the stackable file system architecture in the design and construction of Ficus. The paper concludes with a number of lessons learned from the experience of designing, building, measuring, and living with an optimistically replicated file system.
[GPP93]: R. G. Guy, G. J. Popek, T. W. Page, Jr., "Consistency Algorithms for Optimistic Replication", Proceedings of the First International Conference on Network Protocols, 1993.
Abstract:

The need for replication of information storage, with system support for maintaining consistency among the various copies, has been widely recognized. However, earlier work guaranteed that copies would be consistent by assuring that conflicting updates could not occur. Such an approach decreases availability for update, often at precisely the point when availability is desired. Further, there is increasing data that conflicting updates are extremely rare in many situations of interest.

This paper presents a practical set of algorithms for maintaining the consistency of a replicated file system with an optimistic update policy. These algorithms permit a system which allows updates to an object so long as any copy is available; the algorithms then return the various copies to consistency at their first opportunity. These algorithms have been used to build the Ficus replicated file system.

Data merging

Main readings:

[BP98]: Sundar Balasubramaniam and Benjamin C. Pierce, "What is a File Synchronizer", Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking, 1998.
Abstract:

Mobile computing devices intended for disconnected operation, such as laptops and personal organizers, must employ optimistic replication strategies for user files. Unlike traditional distributed systems, such devices do not attempt to present a "single filesystem" semantics: users are aware that their files are replicated, and that updates to one replica will not be seen in another until some point of synchronization is reached (often under the user's explicit control). A variety of tools, collectively called file synchronizers, support this mode of operation.

Unfortunately, present-day synchronizers seldom give the user enough information to predict how they will behave under all circumstances. Simple slogans like "Non-conflicting updates are propagated to other replicas" ignore numerous subtleties--e.g., Precisely what constitutes a conflict between updates in different replicas? What does the synchronizer do if updates conflict? What happens when files are renamed? What if the directory structure is reorganized in one replica?

Our goal is to offer a simple, concrete, and precise framework for describing the behavior of file synchronizers. To this end, we divide the synchronization task into two conceptually distinct phases: update detection and reconciliation. We discuss each phase in detail and develop a straightforward specification of each. We sketch our own prototype implementation of these specifications and discuss how they apply to some existing synchronization tools.

Supplementary readings:

[HM75]: J.W. Hunt, and M.D. McIlroy, "An Algorithm for Differential File Comparison" (figures 1 and 2), Bell Laboratories, N.J., Computing Science Technical Report No.41, 1975.
Abstract:

The program diff reports differences between two files, expressed as a minimal list of line changes to bring either file into agreement with the other. Diff has been engineered to make efficient use of time and space on typical inputs that arise in getting version-to-version changes in computer-maintained or computer-generated documents. Time and space usage are observed to vary about as the sum of the file lengths on real data, although they are known to vary as the product of the file lengths in the worst case.

The central algorithm of diff solves the 'longest common subsequence problem' to fine the lines that do not change between files. Practical efficiency is gained by attending only to certain critical 'candidate' matches between the files, the breaking of which would shorten the longest subsequence common to some pair of initial segments of the two files. Various techniques of hashing, presorting into equivalence classes, merging by binary search, and dynamic storage allocation are used to obtain good performance.
[Lin2001]: Tancred Lindholm, "A 3-Way Merging Algorithm for Synchronizing Ordered Trees: The 3DM Merging and Differencing Tool for XML", Master's thesis, Helsinki University of Technology, 2001. The 3DM web site.
Abstract:

Keeping data synchronized across a variety of devices and environments is becoming more and more important as the number of computing devices per user increase. Of particular interest are situations when the sets of data that need to be synchronized have structure, but not the exact same stucture.

In the thesis we approach these situations trough a number of use cases, which are set in a future, more ubiquitous, computing environment. The use cases are subsequently analyzed, and in combination with the characteristics of a ubiquitous computing environment used to derive requirements for a synchronization tool. Although the focus is on future computing environments, we find that a synchronization tool fulfilling the requirements is well suited for present-day synchronization tasks as well.

We find that the requirements call for a tool capable of performing a 3-way merge of general ordered trees without any additional tree metadata, such as edit histories or unique node identifiers, that describe how the trees participating in the merge are related. The main research problem of the thesis is to design such an algorithm, given that no suitable algorithms exist.

The design of the algorithm is preceded by stating a definition of desired merging behaviour derived from the use cases as well as a relatively large number of small hand-written merging examples. Further on, the design task is divided into the design of a tree matching algorithm, and an algorithm for merging matched trees. The matching algorithm also gives us the ability to easily find the difference between ordered trees.

The designed merging, matching and differencing algorithms for ordered trees are implemented as a merging and differencing tool for XML, and their functionality is verified against the use cases as well as the merging examples. The evaluation of the algorithms shows promising results regarding the applicability of the tool to real-world situations.
[RC2001]: Norman Ramsey, Elod Csirmaz, "An Algebraic Approach to File Synchronization", Foundations of Software Engineering, 175-185, 2001.
Abstract:

A file synchronizer restores consistency after multiple replicas of a filesystem have been changed independently. We present an algebra for reasoning about operations on filesystems and show that it is sound and complete with respect to a simple model. The algebra enables us to specify a file-synchronization algorithm that can be combined with several different conflict-resolution policies. By contrast, previous work builds the conflict-resolution policy into the specification, or worse, does not specify the synchronizer's behavior precisely. We classify synchronizers by asking whether conflicts can be resolved at a single disconnected replica and whether all replicas are identical after synchronization. We also discuss timestamps and argue that there is no good way to propagate timestamps when there is severe clock skew between replicas.

Concurrency control

Main readings:

[Her91]: Maurice Herlihy, "Wait-Free Synchronization", ACM Transactions on Programming Languages and Systems, vol. 13(1), 124-149, 1991.
Abstract:

A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes. The problem of constructing a wait-free implementation of one data object from another lies at the heart of much recent work in concurrent algorithms, concurrent data structures, and multiprocessor architectures. First, we introduce a simple and general technique, based on reduction to a concensus protocol, for proving statements of the form, ?there is no wait-free implementation of X by Y.? We derive a hierarchy of objects such that no object at one level has a wait-free implementation in terms of objects at lower levels. In particular, we show that atomic read/write registers, which have been the focus of much recent attention, are at the bottom of the hierarchy: thay cannot be used to construct wait-free implementations of many simple and familiar data types. Moreover, classical synchronization primitives such astest&set and fetch&add, while more powerful than read and write, are also computationally weak, as are the standard message-passing primitives. Second, nevertheless, we show that there do exist simple universal objects from which one can construct a wait-free implementation of any sequential object.

Programming languages for distributed systems

General:

[BST89]: Henri E. Bal, Jennifer G. Steiner, and Andrew S. Tanenbaum, "Programming Languages for Distributed Computing Systems", Computing Surveys, vol 21(3), 1989.
Abstract:

When distributed systems first appeared, they were programmed in traditional sequential languages, usually with the addition of a few library procedures for sending and receiving messages. As distributed applications became more commonplace and more sophisticated, this ad hoc approach became less satisfactory. Researchers all over the world began designing new programming languages specifically for implementing distributed applications. These languages and their history, their underlying principles, their design, and their use are the subject of this paper. We begin by giving our view of what a distributed system is, illustrating with examples to avoid confusion on this important and controversial point. We then describe the three main characteristics that distinguish distributed programming languages from traditional sequential languages, namely, how they deal with parallelism, communication, and partial failures. Finally, we discuss 15 representative distributed languages to give the flavor of each. These examples include languages based on message passing, rendezvous, remote procedure call, objects, and atomic transactions, as well as functional languages, logic languages, and distributed data structure languages. The paper concludes with a comprehensive bibliography listing over 200 papers on nearly 100 distributed programming languages.
[Whi96]: James E. White, "Mobile Agents White Paper", General Magic white paper, 1996.
[Whi97]: James E. White, "Mobile Agents", in Jeffrey M. Bradshaw (ed.), "Software Agents", Chapter 18, 437-472, MIT Press, 1997.

Actors:

[Agh86]: Gul Agha, "Actors: A Model of Concurrent Computation In Distributed systems", MIT Press, 1986.
[AMST97]: Gul A. Agha, Ian A. Mason, Scott Smith, Carolyn Talcott, "A Foundation for Actor Computation", Journal of Functional Programming, vol. 7, 1-72, 1997.

Obliq:

[Car95]: Luca Cardelli, "A Language With Distributed Scope", Computing System, vol. 8(1), 27-59, 1995.
Abstract:

Obliq is a lexically-scoped, untyped, interpreted lan- guage that supports distributed object-oriented computation. Obliq objects have state and are local to a site. Obliq computations can roam over the network, while maintaining network connections. Distributed lexical scoping is the key mechanism for managing distributed computations.

Telescript:

[GM95a]: General Magic, "Telescript Language Reference", General Magic, 1995.
[GM95b]: General Magic, "Telescript Programming Guide", General Magic, 1995.

Last updated: Dec 17, 2002 (hniss)