Distributed System Design

Jie Wu

• Chapter 1 introduces some basic concepts, discusses the motivation of distributed computing systems, and presents the scope of distributed computing systems. A brief overview of the book is also provided. -- Chapter 2 surveys general distributed programming languages and introduces a CSP-like distributed control description language (DCDL). This language is used to describe several control issues such as expressing parallelism, interprocess communication and synchronization, and fault-tolerant design. A list of commonly used symbols in DCDL appears in the Appendix. -- Chapter 3 treats distributed systems in a formal way. Several concepts such as clock, event, and state are introduced as well as two approaches that describe a distributed system: the time-space view and the interleaving view. -- Chapter 4 addresses the problem of mutual exclusion which is the key issue for distributed systems design. Mutual exclusion ensures that mutually conflicting concurrent processes can share resources. We also discuss three issues that are related to the mutual exclusion problem: election, bidding, and self-stabilization. -- Chapter 5 studies prevention and detection of deadlock in a distributed system. Distributed systems, in general, exhibit a high degree of resource and data sharing; a situation in which deadlocks may happen. This chapter discusses several solutions to deadlock problems that are unique in distributed systems. -- Chapter 6 studies efficient interprocessor communication mechanisms that are essential to the performance of distributed systems. Three types of communications: one-to-one {unicast), one-to-many (multicast), and one to- all (broadcast), as well as their performance, are studied in this chapter. -- Chapter 7 covers interprocessor communication mechanisms without specific constraints such as adaptiveness, deadlock-freedom, and fault tolerance. Concepts of virtual channels and virtual networks are introduced to achieve various objectives. -- Chapter 8 deals with the reliability issue in distributed systems. An important objective of using distributed systems to achieve high dependability includes reliability, safety, and security. A fundamental issue is to detect and handle faults that might appear in the system. In this chapter we study various methods of handling node, communication, Byzantine, and software faults in a distributed system. -- Chapters 9 and 10 include load distribution problems in a distributed system. Load distribution is a resource management component of a distributed system that focuses on judiciously and transparently redistributing the load of the system among the processors such that overall performance of the system is maximized. Chapter 9 studies static load distribution where decisions of load distribution are made by using a priori knowledge of the system and loads cannot be redistributed during the run time. -- Chapter 10 deals with dynamic load distribution algorithms that use system state information {the loads at nodes), at least in part, to make load distribution decisions. -- Chapter 11 describes distributed data management issues. Two specific issues are covered: {l) synchronization of access to shared data while supporting a high degree of concurrency and {2) reliability. -- Chapter 12 contains applications of distributed design in operating sys terns, file systems, shared memory systems, database systems and heterogeneous processing. Possible future research directions are also listed. The Appendix includes a list of common symbols in DCDL.