Distributed Computing Pearls. Gadi Taubenfeld

10.7 Self Review

       Bibliography

       Author’s Biography

       Index

       Preface

      The design of distributed systems where computing devices (like computers, smartphones, sensors) interact with one another is one of the most challenging problems in computer science. In this book, I have tried to gently introduce the general reader to some of the most fundamental issues and classical results of computer science underlying the design of algorithms for distributed systems, so that the reader can get a feel of the nature of this exciting and interesting field. The book will appeal to the educated layperson and requires no computer-related background at all. I strongly suspect that also most computer-knowledgeable readers will be able to learn something new.

      While humans can see and hear each other, computing devices usually communicate by sending messages or reading from and writing to shared memory locations. As a result, it is far more difficult to synchronize interactions between computers than between humans. Based on this observation, fundamental principles that relate to interactions between computing devices that involve concurrency and synchronization are explained throughout the book.

      Each chapter deals with a specific topic presented in terms of a story. I have compared the issues that arise when dealing with groups of computing devices to those that arise when a group of people has to share their resources and work as a team in order to solve various problems together. Most chapters can be read in isolation, but there is a logical grouping to the complete set of chapters. The topics covered are not an exhaustive survey of the field of distributed computing, but largely a subjective sampling of its highlights.

      One hint about reading this book—do not go too fast, try to read at most one chapter per sitting. Most of the problems presented look deceptively simple at first glance. The only way to understand their tricky nature is by trying to solve them yourself. For that reason, I suggest that, as soon as a problem is posted, you stop reading and try to solve it yourself. Only after you have butted your head against a problem for some time, can you appreciate its beauty. I hope you will enjoy reading the book!

      Contact Information: Please feel free to contact me with any criticism or comments which you might have. I would be glad to hear from you! I can be reached by email at [email protected] or by sending hardcopy mail to Prof. Gadi Taubenfeld, The Interdisciplinary Center, P.O.Box 167, Herzliya 46150, Israel.

      Gadi Taubenfeld

      May 2018

       Acknowledgments

      I would like to thank many of my colleagues for the influence they had on my work and therefore on this book. I thank Jennifer L. Welch and Michel Raynal for their helpful comments on a draft of the book. Most importantly, I thank my family for their love and support.

      Gadi Taubenfeld

      May 2018

      CHAPTER 1

       Distributed Computing

      Two major developments that have happened in recent years are dramatically and irrevocably changing the computer landscape: the dramatic expansion in the use of the Internet, and the design of multicore computers where a single computer has multiple processors. A processor is the “brain” of the computer, and modern computers are now built with multiple “brains.” In each one of these cases, processors on the same or different computers have to work together as a team to achieve common goals.

      In addition to personal computers, smartphones, laptops, tablets, and webcams, the Internet offers connectivity between many other computing devices. A few examples are sensors which enable environmental monitoring applications; sensors which are used for monitoring changes in structural conditions of infrastructures like bridges; wearable sensors that can remotely read a patient’s biometrics and send them to the patient’s physician; infant monitors that provide parents with real-time information about their babies; and much more.

1.1 WINDS OF CHANGE

      Computers and computer networks are one of the most incredible inventions of the 20th century, having an ever-expanding role in our daily lives by enabling complex human activities in areas such as entertainment, education, and commerce. One of the most challenging problems in computer science for the 21st century is to improve the design of systems where communicating devices interact with one another, and in particular, to invent new applications that will take advantage of these new capacities.

      The fundamental changes in computing architectures, where the whole hardware industry shifted to both mobile and multicore platforms expanding the arena of communicating devices to an unprecedented scale, require a fundamental change in how applications are written for computer networks and multicore computers. Concurrency and synchronization are fundamental issues that are critical for the design of such applications—the Internet could not work without synchronized protocols, database systems would be unthinkable without them, operating systems would crash even more frequently, and concurrent programming would be an impossibility.

      Concurrency exists, of course, not only in computer systems but also in nature and living organisms. We can find concurrency at the molecular level as well as at those of cells, organs, individuals, communities, and ecological systems. Much of the future of computers in the 21st century will be told by how well programmers can take advantage of concurrency.

      This book gently introduces the general reader to some of the basic principles and some of the fascinating results of computer science which involve interactions between computing devices (or processors on the same or different devices), so that the reader can get a feel of the nature of this exciting and interesting field called distributed computing. These fundamental principles and results, underlying the design of algorithms for distributed systems, are presented by comparing issues that arise when dealing with groups of computing devices to those that arise when a group of people has to share their resources and work as a team to solve various problems. The book is self-contained; no reliance is made on previous knowledge in computer science. In particular, all the figures in the book which include code segments can be skipped without loss of continuity.

1.2 THE INTERNET

      The Internet is a vast collection of computer networks which are connected into a single huge network. It is used for the transport of data and messages across distances which can be anywhere from the same room to anywhere in the world. It provides an infrastructure for the use of E-mail, banking, commerce, education, entertainment, telecommunications, manufacturing, and social networks and enables the sharing of remote resources such as databases, files, discs, printers, and computational resources. It also enables several computers to solve problems together much faster than any computer can do alone.

      Historically, the Internet was designed as a research network without the expectation that it would have a significant role in our daily lives. The scale and heterogeneity of the Internet have far surpassed all expectations. As the Internet continues to grow, more and more business-critical functions rely on its availability. The vast majority of communications traffic, including telephone, television, radio, business data, and government data, rely on an Internet infrastructure that is available and secure.

      Many applications of large-scale computer networks, such as the Internet, require a high level of reliability and security, for example, an air traffic control system, spacecraft navigation systems, or an integrated corporate management system. As the system size increases, so does the need to design fault-tolerant applications, for the probability