Book “Distributed Algorithms. Intuitive approach "

    imageThis book is designed for a course on distributed algorithms for undergraduate and graduate 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 are mainly “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 the transmission of messages. It was formed on the basis of a course taught at Vrije University (Amsterdam), originally based on the textbook “Introduction to Distributed Algorithms” by Gerard Tel. The second part is dedicated to shared memory architectures.

    Introduction


    An algorithm is a step-by-step procedure aimed at solving a specific problem by a computer. To become a qualified programmer, you must have a good understanding of the algorithms. Every educational program in the field of informatics offers one or several courses on the basics of algorithmization. Usually they consider algorithms for searching and sorting, pattern recognition and finding the shortest paths in graphs. They teach students to identify such subtasks in their computer programs and solve them effectively. Moreover, students learn to think algorithmically, prove the correctness of algorithms and produce a simple complexity analysis.

    Distributed computing is much more complicated than uniprocessor ones and they are very different from them, because the execution of parts of a task at the nodes of a distributed system is time-varying. When two nodes simultaneously 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 racing effect: when two messages arrive at one node on the network, the behavior of the node may depend on which message arrives earlier. 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. Moreover, the number of reachable states tends to grow exponentially with an increase in the number of nodes.

    Another important difference between distributed and uniprocessor computing is that the nodes in a distributed system in the general case do not have relevant 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 transmission. For example, it becomes problematic to determine when execution is complete. It should be established that all nodes in the system have completed work, but even in this case it may turn out that some message is still being transmitted, which will cause activation of the receiving node.

    This book offers you a wide range of basic algorithms that solve such key problems in distributed systems, such as determining when the calculations are completed and when the nodes build a joint picture of the global state of the system. Its main goal is to form students' algorithmic mindset so that they can recognize and solve fundamental problems in the field of distributed computing. Their attention is invited to a comprehensive overview 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, where nodes send messages to each other through channels, and shared memory, when different executable threads can read and write to common areas of memory. 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.

    Many


    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 S. The sets of natural and real numbers are denoted and, respectively. Boolean (boolean) variables have the values ​​true (true) and false (false). A 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 must satisfy is set to the right. For example, {n ∈ | n> 5} represents a set of natural numbers greater than 5. An empty set is denoted by the symbol Ø. For any finite set S, the number of elements in it is denoted by | S |.

    Complexity measures


    Complexity measures show how the consumption of resources (messages, time, memory) grows relative to the size of the input data. For example, if in the worst case the algorithm has O (n2) message complexity, then for input data of size n the algorithm in the worst case requires transmission of the order of n2 messages plus or minus a constant.

    image

    image

    Part I, on the messaging paradigm, mainly addresses message complexity. Bit complexity is only interesting when messages can be very long. In the analysis of time complexity, we assume that event processing does not require time and receiving a message takes a maximum of one unit of time after it is sent. 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 over all runs.

    Relationships of Order


    A relation of (strict) order on a set 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 called strict if, for any different 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 lexicographic ratio <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> will be a strict order relation.

    Modular arithmetic


    A holistic ring modulo positive integer 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 divisible entirely by n. This means that upon reaching n, a cyclic return occurs: n mod n is 0, (n + 1) mod n is 1, etc. Addition and subtraction are transferred to modular arithmetic in a straightforward manner: (j mod n) + (k mod n) = (j + k) mod n and (j mod n) · (k mod n) = (j · k) mod n.

    Exercises


    image

    »More information on the book can be found on the publisher’s website
    » Contents
    » Excerpt

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

    Also popular now: