Distributed Algorithms

These lecture notes describe a course on distributed algorithms I taught in the department of computer science at the Technion during Spring, 1993. The course consisted of thirteen 1.5 hour lectures.My goal in the course was not to provide comprehensive coverage of the area of distributed systems, and not even of the (more restricted) area of theory of distributed algorithms. Rather I wanted to present what I think are the rudiments of this area: the fundamental models, the canonical problems, and the basic methods. In many cases, I decided to present results that are not optimal when I thought they could shed light on the inherent features of some model, problem, or technique. In most of these cases, I mention the better results in the bibliographic notes at the end of the appropriate chapter.The students have scribed the lectures based on my own notes and the original papers. Almost in all cases, they have filled in details and improved the rigor of the presentation. In several cases, they have fixed bugs and suggested simpler ways to present the material. Based on their scribed notes, I have prepared this manuscript. I have tried to unify notation and terminology and to point out similarities and relationships in the material.