Distributed Algorithms
A Verbose Tour
Fourr Sigs
2019 Fourr Sigs
All rights reserved.
No parts of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying,recording or otherwise, without the prior permission of the publishers.
Disclaimer: The Contents of this book are written by the author. The originality, authenticity of the contents, the interpretation and views expressed therein are the sole responsibility of the author. Although every care has been taken to avoid errors and omission, this compendium is being published on the condition and understanding that the information given in the book is merely for reference and must not be taken as having authority of or binding in any manner on the author, editor(s) of publisher.
The publisher believes that the content of this book does not violate any existing copyright/intellectual property of others in any manner whatsoever. However, in case any source has not been duly attributed, the publisher may be notified in writing for
necessary action.
To the incorrigible disposition of a lazy bum: thanks for being my worst critic and best pal
Table of contents
note on intended audience
Preface
Introduction
We live in an age where distributed computing environments are everywhere. They have become absolutely and incontrovertibly all-pervasive in the technical infrastructures that aid and manage just about every facet of our daily lives. It will soon be impossible, if not already, to point out an effective service implementation that handles non-trivial load while being implemented in a monolithic fashion. The focus of this book is the study of algorithms designed to be executed in a distributed environment; i.e. the study of distributed algorithms. The intention of this preface to the book is broadly two-fold: describe the target audience of the book and shed some light on the structure and style adopted for the books content. Indeed, we will be expounding on two highly interrelated subjects where each determines the other to a good extent.
A note on intended audience
The twenty chapters of this book cover a wide range of material - starting with an introduction to distributed systems, we describe, analyse, and prove scores of distributed algorithms and impossibility results that vary from the simplest to the complex, including several ground-breaking works in the field of distributed computing. The book does not restrict itself to a beginners guide, though it does take elaborate care to present the various topics in a highly newbie-friendly manner. One specific aim of the book is to function as a smooth, easy, and illuminating read while also being useful as a quick reference for a hands-on professional. Whether you are a seasoned system designer or a programmer with many years of experience in distributed computing, or a student, or someone new to the industry, or an experienced professional who has spent many years on monolithic systems and now planning to make a quick transition to the distributed way of doing things, you are a part of the target audience for this book. Following up on that last statement, please note a critical differentiator: while the contents of the book are varied enough that they cater to all mentioned classes of readers, the style of presentation is expressly chosen with the last three in mind. The next sections will cover this topic in further detail.
Structure and style of presentation
Let us talk about structure first. The book adopts a similar structure as many popular publications on the topic of distributed algorithms: network algorithms and shared memory ones are handled in separate parts of the book. As a result, multiple problem contexts are revisited in the final part of the book which is dedicated to shared memory algorithms. However, we choose not to assign individual parts or sections to synchronous and asynchronous algorithms - the intention is to allow readers to better contrast the behaviours of the synchronous and asynchronous variants of an algorithm by having them rather close by to each other. The first part of the book is the briefest of all three and is used to provide a quick orientation on distributed systems in general and some of their key properties in particular. The second part is dedicated to network algorithms and is the longest of the three by a stretch.
Let us consider the presentation style next. In brief, the style is anything but terse. Indeed, this is hinted at in a rather broad manner by the subtitle of the book: a verbose tour . There is a constant effort throughout the book to avoid an excess of mathematical language and notations altogether whenever possible and be kept to a minimum when a total avoidance might take something away from the proof or analysis at hand. Let us also note here, then, that we do give up something when we deviate from a terse manner of description: a terse style does reduce the chances of ambiguity. A verbose approach on the other hand, while lending a quality of light reading, can at times leave itself vulnerable to multiple interpretations - the imbibed meaning at times even dependent on the readers state of mind, mental makeup, or any preconceptions on the topic being addressed. The book attempts to find a suitable balance by backing up its expansive style with a plenitude of examples, flowcharts, and diagrammatic representations. In short, the verbose nature of presentation is aimed at readability while any consequent ambiguity is resolved by following up the presentation and analysis of a topic with examples and visual representations. Now, this does bring us to the topic of examples.
Good examples need to tread a fine line when it comes to handling complexity. How do we rationalise that statement? To begin with, we can safely assume that an example becomes necessary only when the subject matter at hand approaches a certain level of complexity. The very idea of an example is to present a story that is similar to the topic being exemplified while at the same time existing at a lower level of complexity. Now, an example that is too simple will lose too many details as to deviate significantly from the subject matter. Next, consider the other extreme: an example that (too) closely resembles the topic being exemplified will exist at a similar level of (undesirable) complexity, thus defeating its purpose. Indeed, a fine balance is needed. In this book, when faced with a choice the effort always is to err on the side of simplicity. As a result, a few examples do take creative liberties while opting to maintain a loose connection with the topic at hand. The idea in such cases is to let the example provide only a sharp hint or two in the right direction; the reader is trusted to work out the rest of the details once the correct direction of comprehension is pointed out.
To conclude, a quick note on how to approach reading this book: the first four chapters of the book are oriented towards beginners on the subject, so others might prefer to skip them and refer back later in case of a specific need. From the fifth chapter onwards, the complexity of the contents (algorithms in particular) start stepping up all the way to a few industrial-strength protocols being analysed in a rather detailed fashion towards the end of the second part of the book. Up until that point, no familiarity with computer programming is assumed. The last and third part of the book, however, does presuppose a basic level of programming experience or knowledge. There is a certain abundance of code (and pseudo code) in the chapters on shared memory algorithms; readers who are not particularly interested in code are still encouraged to make use of the accompanying descriptions and treatment, because the overall style remains the same as elsewhere in the book - fairly verbose and voluble.
