The mastery of distributed applications distributed computation and control, generally called the foundations of the distributed algorithm. The object of this book is to present such foundations as far as synchronization, the key element of parallelism and distribution, is concerned. The work is divided into four chapters, followed by an appendix. An introductory character sets out the different types of synchronization that may be encountered in a parallel application and chapter 2 presents the concept of wave and several of its possible implementations. Chapter 3 deals with the notions of synchronous and asynchronous systems and studies their relationships, aiming to show how a synchronous algorithm is executed on an asynchronization phase, its properties and use. The implementation of all of these concepts of control and synchronization, as well as of the algorithms which arise from them, requires the ability to visit the sites of processes of the application. For methodological reasons, the study of the traversal techniques which can be used and which are based on the distributed construction of a traversal structure (virtual ring, spanning arborescence or tree) using an exploration of the network distributed in depth or in width, is not undertaken in chapters 1 to 4. The study of traversal structures, and distributed algorithms for constructing them, is the subject of an appendix. The algorithms presented throughout the book are described in an event-driven from intended to be self-explanatory - such and such an event produces such and such effects. This work is intended, for those interested in applications and in distributed systems, networks and distributed algorithms.
Part 1 Different forms of synchronization between processes: distributed systems, networks, and networks of processes; synchronization. Part 2 The concept of a wave, and synchronization by wave train: wave algorithms; example of use - computation of a global state function; communication by rendezvous; communication by channels other than FIFO; the case of communication by FIFO channels. Part 3 Synchronization by logic pulsing: the concept of the synchronizer; principle of implementation; the case of networks with limited delays. Part 4 Synchronization by phases: a class of distributed computations; the problem of termination; a general and effective algorithm; some applications of the algorithm. Appendices: construction of structures; arborescence constructed by sequential exploration; construction of spanning tree; construction of a virtual ring.