Distributed Algorithms

Chapter 23 Modelling V: Partially Synchronous System Models

The final three chapters of this book comprise a short introduction to the study of partially synchronous, or timing-based, distributed algorithms. Recall that Part I (Chapters 2–7) examined synchronous distributed algorithms, while Part II (Chapters 8–22) dealt with asynchronous distributed algorithms. It turns out that there is an interesting class of models and algorithms between these two extremes, which we call partially synchronous. In a partially synchronous system, the components have some information about time, although the information might not be exact. For example, processes in a partially synchronous network might have access to almost-synchronized clocks, or might know ...