This substantial monograph addresses two open problems in the field of distributed computing: the Byzantine agreement problem and the leader election problem. The context is a model that is asynchronous with full information and involves communications via message passing. Up to a constant fraction of processors can be faulty, while the others are nonfaulty. The key contribution of Kapron et al. is the presentation of protocols that are worst-case time polylogarithmic in the number of processors, a major improvement over previous protocols. At the heart of the protocols is the asynchronous universe reduction, a technique that reduces the number of processors under review to a small representative sample. Four open questions are posed at the end of the monograph.

The introductory section gives an effective overview of the monograph’s contents and states the two key theorems that summarize the work. The second section gives more details, necessary for developing the results that follow. The third section addresses the subcommittee election process. The next two sections generate the results for asynchronous Byzantine agreement, including a reduction to polylogarithmic time. The sixth section leverages these techniques and consequences to produce the leader election result.

This paper is effectively organized and developed. The authors do justice to the mathematical and computational complexity details that underlie their work. Researchers with interests in algorithm analysis and computational complexity in a distributed computing setting should find the presentation and results here worth reading and studying.