Weak System Models for Distributed Agreement Problems

This book investigates theoretical aspects of system models for agreement problems in fault-tolerant distributed computing. A distributed system is a collection of processes that communicate with each other by sending messages over a network. Achieving agreement among these processes despite failures is a difficult but important problem. Care must be taken when choosing a system model as a too restrictive model will be applicable to very few systems, whereas too relaxed assumptions might severely reduce the set of problems that can be solved. Part I of this book provides an introduction to the context of this work, discusses related literature and describes the basic system assumptions. Part II introduces the Asynchronous Bounded-Cycle model which is entirely time-free but nevertheless sufficient to solve fault-tolerant consensus despite Byzantine faults. Part III presents an in-depth treatment of algorithms and models for solving the k-set agreement problem which requires processes to agree on at most k distinct values.

Autorentext

is a research fellow at the Nanyang Technological University in Singapore. He received his PhD, MSc and BSc degrees in Computer Science from the Vienna University of Technology. His research focuses on the theoretical aspects of distributed computing, including agreement algorithms, lower bound proofs and impossibility results.