Издательство Springer, 2005, -364 pp.Due to the development of hardware technologies (such as VLSI) in the early 1980s, the interest in parallel and distributive computing has been rapidly growing and in the late 1980s the study of parallel algorithms and architectures became one of the main topics in computer science. To bring the topic to educators and students, several books on parallel computing were written. The involved textbook Introduction to Parallel Algorithms and Architectures by F. Thomson Leighton in 1992 was one of the milestones in the development of parallel architectures and parallel algorithms. But in the last decade or so the main interest in parallel and distributive computing moved from the design of parallel algorithms and expensive parallel computers to the new distributive reality – the world of interconnected computers that cooperate (often asynchronously) in order to solve different tasks. Communication became one of the most frequently used terms of computer science because of the following reasons:
Considering the high performance of current computers, the communication is often more time consuming than the computing time of processors. As a result, the capacity of communication channels is the bottleneck in the execution of many distributive algorithms.
Many tasks in the Internet are pure communication tasks. We do not want to compute anything, we only want to execute some information exchange or to extract some information as soon as possible and as cheaply as possible. Also, we do not have a central database involving all basic knowledge. Instead, we have a distributed memory where the basic knowledge is distributed among the local memories of a large number of different computers.
The growing importance of solving pure communication tasks in the interconnected world is the main motivation for writing this book. The main goals of this material are:
to provide a monograph that surveys the main methods, results and research problems related to the design and analysis of communication algorithms (strategies) under different technological constraints; and
to provide an introductory textbook in the field of information dissemination in interconnection networks with a special emphasis on broadcast, information collection, gossip, leader election, and related tasks.
Our work is divided into two parts. This first textbook is devoted to the classical, direct communication between connected pairs of nodes of a communication network and to the related communication tasks such as broadcasting, gossiping, and leader election. The forthcoming part focuses on the fast communication via fixed paths between senders and receivers, which is based on new technologies such as optical networks, ATM networks, and wireless networks (for instance, mobile phones and radio networks).
This book aims to be a textbook accessible for students as well as a monograph that surveys the research on communication, presents the border between the known and the unknown, and can so be of interest to researchers and professionals, too.Introduction
Part I The Telegraph and Telephone Modes
Fundamentals
Broadcasting
Gossiping
Systolic Communication
Fault-Tolerance
Part II Distributed Networks
Broadcast on Distributed Networks
Leader Election in Asynchronous Distributed Networks
Fault-Tolerant Broadcast in Distributed Networks
