Distributed Operating Systems & Algorithms [Hardcover]

Randy Chow (Author), Theodore Johnson (Author)

Book Description

ISBN-10: 0201498383 | ISBN-13: 978-0201498387 | Publication Date: March 28, 1997 | Edition: 1st

This book integrates the theory and practice of distributed operating systems and algorithms. It combines coverage of distributed operating systems and distributed algorithms, allowing instructors to cover the algorithms involved in distributed operating systems with optional depth as desired and motivate the study of distributed algorithms by showing how they are applied in operating systems. Currently all books treat these as separate topics. This text includes coverage of parallel systems, distributed systems, real-time systems, computer networks and algorithms for asynchronous distributed systems, and uses examples from many commercial and experimental operating systems. Included in the book are a number of programming projects.

Editorial Reviews

From the Inside Flap

PREFACE

This book has developed from a set of lecture notes we used to teach a graduate two-coursesequence on operating systems. We had difficulties finding a textbook that hadbalanced coverage of concepts and theories and sufficient detail for a graduate-levelclass. After using research papers and selected book chapters for several semesters (whichstudents hate), we developed lecture notes for the students and then developed the notesinto this book.

The key idea behind the book is to integrate the theory and practice of distributedoperating systems. Many texts provide an overview of distributed systems with a vaguedescription of the algorithms. It is difficult to teach an in-depth course from thesebooks. Other texts focus on algorithms. However, it is hard to motivate students to studyalgorithms if they do not have a picture of what is needed in practice. For example,understanding the need for naming and directory services clarifies the need for causalmessage passing and update propagation.

The first part of the book (Chapters 1 through 8) is intended to be used for a coregraduate course on operating systems. It provides a broad discussion of modern operatingsystems. Since we assume that the student readers already have taken an undergraduatecourse on operating systems, we do not include many topics, such as memorymanagement, deadlocks, and device drivers, that are typically covered by undergraduatecourses and that are well covered by existing texts. Instead, we concentrate on issuesand implementations of modern operating systems for parallel systems, distributed systems,real-time systems, and computer networks. The programming projects in this partconcentrate on using tools, such as sockets, RPC, and threads.

The second part of the book (Chapters 9 through 13) is intended for an advanced courseon distributed operating systems, focusing on algorithms for asynchronous distributedsystems. The material provides a framework for thinking about distributed systems, precisealgorithm descriptions, and an understanding of why the algorithms were developed andwhy they are correct. The theme behind much of the material presented in this sectionis providing the framework for implementing a replicated server-- a prototype forimplementing a fault-tolerant and highly available distributed system. The projects inthis part use the tools presented in the first part to implement the algorithms.

The different focuses of the two parts of the book complement each other, with thefirst part supplying background and the second part supplying theory. While the book isintended for a two-course sequence, it also works well for a graduate operating systemor an advanced distributed systems class alone. Although each of the two parts is self-contained,extensive cross-referencing allows the reader to emphasize either theory orimplementation or to cover both elements of selected topics. With the widespread exposureof the Internet, we envision that the book could also be of interest to undergraduatestudents and can be tailored to undergraduate classes. Furthermore, the combined bookmakes an excellent reference for the practitioner who has some working experience onoperating systems.BOOK ORGANIZATION

The book is structured to present the important concepts of distributed operating systems.We make many references to commercial and experimental systems to illustrate theconcepts and the implementation issues. In addition, each chapter provides an extensiveannotated bibliography that points the interested reader to recent developments indistributed computing theory, technology, and practice. In the following we give a briefdescription of the content of each chapter.

Part I of the textbook is a pragmatic presentation of the basic concepts and implementationissues of a distributed operating system. It is organized in three major components:fundamental concepts, distributed processes, and distributed resources.Fundamental Concepts (Transparency, Service, and Coordination)

Chapter 1 introduces a classification of centralized operating system, network operatingsystem, distributed operating system, and cooperative autonomous systems, usingthe key characteristics of virtuality, interoperability, transparency and autonomicity,respectively, for each system. It illustrates the evolution that led to the development ofmodern distributed operating systems and explains the emerging need for distributedsoftware and the importance of distributed coordination algorithms.

Chapter 2 begins the discussion of distributed operating systems. It presents theconcepts of transparency and services. Distributed systems and their underlyingcommunication architectures are introduced. The chapter concludes with a list ofmajor system design issues that establishes an order for the presentation of thesubsequent chapters.Distributed Processes (Synchronization, Communication, andScheduling)

Chapter 3 describes concurrent processes and programming. It defines processes andthreads and shows how their interaction can be modeled by using some fundamentalconcepts such as a graph, a logical clock, and the client and server model. Both sharedmemory and message passing for synchronization and communication are addressed.They are presented along with the development of concurrent language constructs.A taxonomy of these language mechanisms and their implementation is given. Thischapter presents an integrated view of synchronization and communication.

Chapter 4 extends the discussion of process interaction from synchronization tocommunication and to distributed process coordination using message passing communication.Three communication models, message passing (socket), request/reply(RPC), and transaction communication, are presented. A special emphasis is placedon group communication and coordination. Two classical distributed coordinationproblems, mutual exclusion and leader election using message passing interprocesscommunication, are introduced. These problems are further studied in Chapters 10 and11 in Part II of the textbook. The chapter also includes a presentation of name service,an essential facility for communication in distributed systems.

Chapter 5 turns to the third process management issue, that of process scheduling. Theeffect of communication on both static and dynamic process scheduling is emphasized.The chapter describes distributed computation through dynamic redistribution ofprocesses by using remote execution and process migration techniques. It also addressesseveral unique issues in real-time scheduling.Distributed Resources (Files and Memory)

Chapter 6 discusses the distributed implementation of file systems, the first of thetwo important distributed resources: files and memory. It demonstrates the use of theconcept of transparency and service in the design of distributed file systems. Twomajor implementation issues, data caching and file replication, are discussed in thischapter. The chapter also covers distributed transactions as part of the file service.Since management of replicated data touches upon both data and communication,two central issues in distributed systems, it is further detailed in Chapter 12.

Chapter 7 covers distributed shared memory systems that simulate a logical sharedmemory on a physically distributed memory system. The issues studied are coherenceand consistency of data due to memory sharing. The chapter describes implementationstrategies for different memory consistency requirements. It also shows the significanceof the object-based data sharing models.

Chapter 8 addresses unique security issues in network and distributed environments.These issues are divided into two areas: authorization and authentication. Authorizationincludes the study of distributed access and flow control models. Authenticationcovers cryptography and its applications for mutual authentication and key distributionprotocols. Implementations of some security features in modern systems areillustrated.

Part II of the textbook discusses distributed algorithms. The discussion is pragmaticand is intended to give the reader a solid understanding of common problems andsolution techniques. The topics are organized in five chapters.Distributed Algorithms

Chapter 9: introduces the concepts of time and global states in a distributed system.The fundamental problem of distributed algorithms is a lack of a global clock and aglobal state. Recent research on vector time and distributed predicates has developedunified models for thinking about distributed time and the distributed state. Thischapter presents the concepts of causality, vector timestamps, and global states. Thealgorithms for implementing these concepts are presented. The connections betweenthe different models are explored. Finally, a model for proving the correctness ofdistributed algorithms is presented.

Chapter 10: covers distributed synchronization and distributed election. While thedistributed synchronization algorithms are not considered pragmatic, they illustrateimportant algorithm design techniques. For example, voting algorithms for replicateddata management are foreshadowed in Maekawa's algorithm, and the Chang-Singhal-Liualgorithm illustrates the ideas behind distributed shared memory (and distributedobject) algorithms. The chapter concludes with algorithms for electing a computationleader. Election is a critical component of many systems. The invitation algorithmviiin particular is a prototype for handling failures in an asynchronous system andforeshadows the group view maintenance algorithms of Chapter 12.

Chapter 11 discusses the abstract distributed agreement problem. First, Byzantineagreement is discussed. Next, the Fischer-Lynch-Paterson (FLP) result that no algorithmsolves distributed agreement problems in an asynchronous system is coveredin detail. This is the appropriate point to introduce the FLP result, because the nextchapter covers replicated data management and must solve distributed agreement inasynchronous systems. The FLP result leaves open three ways to achieve distributedagreement in an asynchronous system: hope that it happens, use relative agreement,or use a randomized algorithm. The chapter discusses these implications of the FLPresult and concludes with some randomized agreement protocols.

Chapter 12 covers replicated data management. Since providing replicated servers reducesto replicating the state of the servers, this section also discusses the problems andconcepts of replication. We cover three main approaches: the transaction approach,the reliable multicast approach, and the log propagation approach. The transactionapproach includes discussion of two-phase commit, three-phase commit, one-copyserializability, voting, and dynamic voting protocols. The reliable multicast approachincludes discussion of virtual synchrony, algorithms for implementing reliable andcausal multicast, algorithms for totally ordered multicast, and consistent multicastgroup maintenance algorithms. The log propagation approach covers naive log propagation,epidemics, and causal log propagation. This chapter is the culmination of PartII of the text and draws together the results presented in previous chapters.

Chapter 13 covers distributed rollback and recovery. These techniques are critical forimplementing fault-tolerant systems and are complimentary to the replicated datamanagement techniques of the previous chapter. By using the theory developed in theprevious chapters (especially Chapter 9), different rollback and recovery algorithmsare presented in a unified manner and are related to algorithms discussed previously.SUGGESTED COVERAGE

The book contains sufficient materials for a two-semester operating system (or distributedsystem) course sequence. To use the book for an one-semester course, we recommend thefollowing two options for coverage with different orientations.

Distributed Operating Systems: This option covers the entire Part I with supplementalSections 9.1, 9.2, 10.1.2, 10.1.3, 10.1.4, 10.2, 12.1, and 12.1.3 from Part II. The coursewill focus on the implementation issues of the major components in a distributedoperating system. The supplemental sections in Part II extend the discussion ofdistributed coordination algorithms.

Distributed Algorithms: This option uses the entire Part II with Sections 4.1-4.4,6.1-6.3, and 7.1-7.4 from Part I. The course will emphasize the design of distributedalgorithms in distributed systems. The selected sections in Part I serve as thebackground and motivations for the discussion of distributed algorithms in Part II.ACKNOWLEDGEMENTS

The authors wish to acknowledge the COP5615 (Operating System Principles) and theCOP6635 (Distributed Operating Systems) classes for allowing them to test preliminaryversions of the book. Special thanks go to Anthony Bridgewater, Raja Chatterjee, WilliamChow, Roger Collins, Darin Davis, Carlos Guerra, Steve Greenwald, Vanja Josifovski, EricShaffer, and Shiby Thomas for finding errors in the examples and algorithms.

Several topics of discussion use the research work from theses and dissertations bystudents at the University of Florida. Frank Anger and J. J. Hwang contributed themultiprocessor scheduling models and algorithms. The LAM distributed shared memorysystem was given by Roger Denton. I-Lung Kao shared the discussion of the complexsecurity policies. Lionel Maugis contributed the start of the bibliography and the totalordering algorithm from his thesis.

The comments and feedback from the reviewers were enormously valuable. We wish toshow our appreciation to them for providing their expertise to improve the quality of thebook. They are: Warren R. Carithers of Rochester Institute of Technology, Prasun Dewanof University of North Carolina, Peter G. Drexel of Plymouth State College, Gary Harkin ofMontana State University, Eric H. Herrin, II of University of Kentucky, Mark A. Hollidayof Western Carolina University, Michael A. Keenan of Columbus State University, WilliamF. Klostermeyer of West Virginia University, Bruce Maggs of Carnegie-Mellon University,James Purtilo of University of Maryland, Gurdip Singh of Kansa State University, andSalih Yurttas of Texas A&M University.

The book cover design was inspired by the "turtles all the way down" anecdote whichwas believed to originate from WilliamJames and retold by many philosophers includingBertrand Russell and Steve Hawking. We added the stack of "gators" to show anotherlayered-structured autonomous system. The art work was contributed by Sheng-Wan Hu.Special thanks go to Michael Downes and S. Y. Cheng who helped to solve many Latextechnical problems.

We started writing the book when our wives complained that they did not have anybook dedicated to them as many others do. We would thank Johna and Taiying for givingus such great motivation to write the book. This book is dedicated to them. 0201498383P04062001

From the Back Cover

Distributed Operating Systems and Algorithms integrates into one text both the theory and implementation aspects of distributed operating systems for the first time. This innovative book provides the reader with knowledge of the important algorithms necessary for an in-depth understanding of distributed systems; at the same time it motivates the study of these algorithms by presenting a systems framework for their practical application.

The first part of the book is intended for use in an advanced course on operating systems and concentrates on parallel systems, distributed systems, real-time systems, and computer networks. The second part of the text is written for a course on distributed algorithms with a focus on algorithms for asynchronous distributed systems. While each of the two parts is self-contained, extensive cross-referencing allows the reader to emphasize either theory or implementation or to cover both elements of selected topics.

Features:

• Integrates and balances coverage of the advanced aspects of operating systems with the distributed algorithms used by these systems.
• Includes extensive references to commercial and experimental systems to illustrate the concepts and implementation issues.
• Provides precise algorithm description and explanation of why these algorithms were developed.
• Structures the coverage of algorithms around the creation of a framework for implementing a replicated server-a prototype for implementing a fault-tolerant and highly available distributed system.
• Contains programming projects on such topics as sockets, RPC, threads, and implementation of distributed algorithms using these tools.
• Includes an extensive annotated bibliography for each chapter, pointing the reader to recent developments.
• Solutions to selected exercises, templates to programming problems, a simulator for algorithms for distributed synchronization, and teaching tips for selected topics are available to qualified instructors from Addison Wesley.

0201498383B04062001

See all Editorial Reviews

Product Details

• Hardcover: 570 pages
• Publisher: Addison Wesley; 1st edition (March 28, 1997)
• Language: English
• ISBN-10: 0201498383
• ISBN-13: 978-0201498387
• Product Dimensions: 9.5 x 7.7 x 1.1 inches
• Shipping Weight: 2.5 pounds (View shipping rates and policies)
• Average Customer Review: 1.7 out of 5 stars  See all reviews (7 customer reviews)
• Amazon Best Sellers Rank: #385,170 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

9 of 9 people found the following review helpful:

2.0 out of 5 stars Lists a few basic ideas, but is dull and simplistic, May 3, 2001

By 

Ramon Kranzkuper (Gainesville, FL) - See all my reviews

This review is from: Distributed Operating Systems & Algorithms (Hardcover)

This book is probably useful only at the University of Florida, since it follows the course lectures exactly - and that, because the first author is the instructor.

The book reads like a series of lecture notes, nothing more, nothing less. Several ideas that a student of operating systems may need to take note of, when making the transition from single-machine systems to multi-machine, are listed here. You can think of this book as a listing of a few basic ideas, with small expansions of each - as in a slideshow presentation. The merit of the book ends there.

The topics covered - in other words, the expansions of the listed ideas - are treated in a confused, sketchy manner. The material is insubstantial and hardly thought provoking. Motivation is absent, and pedagogical methods seem a distant concept. There is a near-total isolation of concepts and practice, and reading the book gives the feeling of being isolated in a dreamy sphere that belongs only to the author.

One could go on about such demerits, but to summarize, you don't need to buy this book unless it's required for your class. It's a slideshow in hardcover format.

5 of 5 people found the following review helpful:

2.0 out of 5 stars "Good Rough Draft", August 10, 2003

By 

Ted (United States) - See all my reviews
(REAL NAME)   

Amazon Verified Purchase

This review is from: Distributed Operating Systems & Algorithms (Hardcover)

The best way to explain this book is, its a "good rough draft". Now go work on it some more. As is, the book is extremely hard to read. Crucial concepts are stated matter of factly, succinctly, and with little detail as possible, ie, just enough to get the point across (and that might be a stretch). The authors could make this a very good book, but they need to take much more time with every subject, and give more than one example. Furthermore the diagrams are sub-par. These diagrams could be greatly enhanced by professional technical artists. Also, the 2nd half of the book might be better interspersed with the 1st half. A *much* better read, with better diagrams, and a gentler approach on the exact same subject is "Distributed Operating Systems" by Andrew Tannenbaum.

5 of 6 people found the following review helpful:

2.0 out of 5 stars disappointing, September 8, 2000

By 

ING. PETER MELISEK (Bratislava Slowakei) - See all my reviews

This review is from: Distributed Operating Systems & Algorithms (Hardcover)

I bought this book expecting that I can learn some fundamentals on distributed systems and algos. The author touched many areas - but even stuff that I know pretty well ( security ) wasn't explained in an easy-to-understand manner, sometimes too much prose to no avail. Even worse, sometimes I was a bit confused. I can only guess that the rest follows this way. If you are looking for GOOD book, better look for something else.