Distributed Algorithms

Table of Contents

Instructions for online access

Cover

Title Page

Dedication

Copyright

Preface

Chapter 1: Introduction

1.1 The Subject Matter

1.2 Our Viewpoint

1.3 Overview of Chapters 2–25

1.4 Bibliographic Notes

1.5 Notation

Part I: Synchronous Network Algorithms

Chapter 2: Modelling I

2.1 Synchronous Network Systems

2.2 Failures

2.3 Inputs and Outputs

2.4 Executions

2.5 Proof Methods

2.6 Complexity Measures

2.7 Randomization

2.8 Bibliographic Notes

Chapter 3: Leader Election in a Synchronous Ring

3.1 The Problem

3.2 Impossibility Result for Identical Processes

3.3 A Basic Algorithm

3.4 An Algorithm with O (n log n) Communication Complexity

3.5 Non-Comparison-Based Algorithms

3.6 Lower Bound for Comparison-Based Algorithms

3.7 Lower Bound ...