The book "Distributed Algorithms. Intuitive approach "

This book is designed for a course on distributed algorithms for undergraduate and postgraduate students in specialties related to computer science and software engineering. It can also be used as a reference by researchers in these areas. The book focuses on basic algorithms and results obtained in the field of distributed computing. The algorithms considered in it mainly refer to the “classical” ones and were chosen primarily because they are instructive from the point of view of designing algorithms for distributed systems or shed light on key problems in distributed and parallel programming.

The book consists of two parts. The first part is devoted to the interaction of processes through message passing. It was formed on the basis of the course taught at the University of Vrije (Amsterdam), originally based on the textbook on “Introduction to Distributed Algorithms” by Gerard Tel. The second part is dedicated to shared memory architectures.

Introduction

The algorithm is a step-by-step procedure aimed at solving a specific problem with a computer. To become a qualified programmer, you need to have a good understanding of the algorithms. Any educational program in the field of computer science offers one or more courses on the basics of algorithmic. Usually they consider search and sorting algorithms, pattern recognition and finding the shortest paths in the graphs. They teach students to identify such subtasks in their computer programs and solve them effectively. Moreover, students learn to think algorithmically, to prove the correctness of algorithms and to produce the simplest complexity analysis.

Distributed computing is much more complicated than single-processor ones and is very different from them, since the execution of parts of the task on the nodes of the distributed system is interleaved in time. When two nodes in parallel perform some actions, it is impossible to predict which of them will be performed earlier in time. This leads, for example, to the so-called race effect: when two messages arrive at the same node in the network, the behavior of the node may depend on which of the messages comes first. Distributed systems are thus non-deterministic in nature - starting the system twice in the same configuration from the same initial state can lead to different results. In this case, the number of attainable states tends to grow exponentially with an increase in the number of nodes.
')
Another important distinction between distributed and uniprocessor computing is that nodes in a distributed system generally do not have current information about the global state of the system. They know their own local states, but they do not always know about the local states of other nodes or messages that are in the process of being transmitted. For example, the determination of the completion point becomes problematic. It must be determined that all the nodes in the system have completed their work, but even in this case it may turn out that some message is still being sent that will activate the receiving node.

This book offers you a wide range of basic algorithms that solve such key problems in distributed systems as determining the moment of completion of calculations and jointly constructing a picture of the global state of the system by nodes. Its main goal is to form an algorithmic mindset for students so that they can recognize and solve fundamental problems in the field of distributed computing. Their attention is offered a comprehensive review of these problems from a bird's eye view, as well as evidence of correctness on the fingers and approximate methods for assessing complexity.

The two main communication paradigms in distributed computing are messaging, when nodes send messages to each other through channels, and shared memory, when different execution threads can read and write to shared memory areas. The book is divided into two parts, devoted to these two communication paradigms. The remainder of the introduction provides preliminary information applicable to both approaches.

The sets

As usual, S1 ∪ S2, S1 \ S2, and S1 S2 denote the union, difference, and inclusion of sets; s ∈ S means that s is an element of the set S. The sets of natural and real numbers are denoted by and respectively. Boolean (logical) variables are true (true) and false (false). The set can be written in the form {... | ...}, where its elements are indicated to the left of the vertical line, and the condition to which they should be specified is set to the right. For example, {n ∈ | n> 5} is a set of natural numbers greater than 5. An empty set is denoted by Ø. For any finite set S, the number of elements in it is denoted | S |.

Complexity measures

The complexity measures show how resource consumption (messages, time, memory) grows relative to the size of the input data. For example, if in the worst case the algorithm is of O (n2) messages, then for the input data of size n, in the worst case, the order requires the transfer of the order of n2 messages plus or minus constant.




Part I, devoted to the messaging paradigm, basically deals with message complexity. Bit complexity is interesting only when messages can be very long. When analyzing the time complexity, we assume that event handling does not take time and receiving a message takes at most one time unit after sending it. Different launches can lead to different resource consumption. We consider the complexity for the worst case and the average complexity, and for the latter we give a certain probability distribution for all the launches.

Relationship order

A relation of (strict) order on S is an irreflexive, asymmetric, and transitive binary relation on its elements. This means that for any a, b, c ∈ S, a <a; if a <b, then b <a; and if a <b and b <c, then a <c. An order is said to be strict if, for any distinct a, b ∈ S, either a <b or b <a; otherwise, the order is called partial. Let two sets S1 and S2 be given with relations of order <1 and <2, respectively. Then the relation of lexicographic order <on pairs from S1 × S2 is defined as (a1, a2) <(b1, b2), if either a1 <1 b1 or a1 = b1 and a2 <2 b2. If <1 and <2 are strict order relations, then the corresponding lexicographic order relation is a strict order relation.

Modular arithmetic

The integral ring in the natural positive modulus n is represented by the elements {0 ... n - 1}. Every integer k has a representative remainder of division by n, denoted by k mod n, which is the only ℓ ∈ {0 ... n - 1}, such that k - ℓ is divided completely by n. This means that when reaching n, a cyclic return occurs: n mod n is 0, (n + 1) mod n is 1, and so on. Addition and subtraction are transferred to modular arithmetic in a straightforward way: (j mod n) + (k mod n) = (j + k) mod n and (j mod n) · (k mod n) = (j · k) mod n.

Exercises

»More information about the book can be found on the publisher's website.
» Table of Contents
» Excerpt

For Habrozhiteley a 25% discount on the coupon - Algorithms
Unfortunately, the book is available only in paper form.