{"id":37335,"date":"2019-10-31T22:17:01","date_gmt":"2019-10-31T19:17:01","guid":{"rendered":"https:\/\/prohoster.info\/blog\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah\/"},"modified":"2019-10-31T22:17:01","modified_gmt":"2019-10-31T19:17:01","slug":"kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","status":"publish","type":"post","link":"https:\/\/prohoster.info\/en\/blog\/administrirovanie\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","title":{"rendered":"Schr\u00f6dinger's Cat Without a Box: The Consensus Problem in Distributed Systems","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Let's imagine. In a room, five cats are locked in, and in order to wake up their owner, they need to agree among themselves since they can only open the door together by pushing against it. If one of the cats is Schr\u00f6dinger's cat, and the others are unaware of his decision, the question arises: 'How can they do this?' <\/p>\n

In this article, I will explain in simple terms the theoretical aspects of distributed systems and principles of their operation. I will also briefly cover the main idea behind Paxos. <\/p>\n

\"Schr\u00f6dinger's
\n<\/a><\/noindex>
\nWhen developers use cloud infrastructures, various databases, and work in clusters with a large number of nodes, they are confident that the data will be intact, secure, and always accessible. But where do these guarantees come from?<\/p>\n

Essentially, the guarantees we have are the provider's promises. They are described in the documentation something like this: 'This service is reliable, it has a specified SLA, don\u2019t worry, everything will work in a distributed manner as you expect.' <\/p>\n

We tend to believe in the best, as smart folks from big companies assure us that everything will be fine. We don't question why this might actually work. Is there any formal proof of the correctness of such systems?<\/p>\n

Recently, I attended a school on distributed computing<\/a><\/noindex> and was really inspired by this topic. The lectures at the school resembled more of a mathematical analysis class than something related to computer systems. Yet, that\u2019s how the most critical algorithms we use every day were proven, often without us even realizing it. <\/p>\n

Most modern distributed systems use the Paxos consensus algorithm and its various modifications. The coolest part is that the validity and, in general, the very possibility of this algorithm's existence can be proven simply with a pen and paper. At the same time, in practice, the algorithm is applied in large systems running on numerous nodes in the cloud. <\/p>\n

A light illustration of what will be discussed next: the two generals' problem<\/b>Let's warm up by examining the two generals' problem<\/a><\/noindex>. <\/p>\n

We have two armies \u2013 the red and the white. The white forces are based in the besieged city. The red forces, led by Generals A1 and A2, are positioned on either side of the city. The red's objective is to attack the white city and win. However, the army of each red general is individually smaller than the white army.<\/p>\n

\"Schr\u00f6dinger's
\n
\nThe conditions for the red to win: both generals must attack simultaneously to have a numerical advantage over the whites. To do this, Generals A1 and A2 need to agree with each other. If each attacks separately, the reds will lose. <\/p>\n

To reach an agreement, Generals A1 and A2 can send messengers to each other across the territory of the white city. A messenger may successfully reach the allied general or may be intercepted by the enemy. The question is: is there a messaging sequence between the red generals (the sequence of sending messengers from A1 to A2 and back from A2 to A1) that guarantees they will agree to attack at time X? Here, guarantees mean that both generals will have clear confirmation that the ally (the other general) will definitely attack at the appointed time X.<\/p>\n

Suppose A1 sends a messenger to A2 with the message: \"Let\u2019s attack today at midnight!\" General A1 cannot attack without confirmation from General A2. If the messenger from A1 arrives, then General A2 sends confirmation with the message: \"Yes, let\u2019s take down the whites today.\" But now General A2 does not know whether his messenger has arrived or not; he has no guarantees that the attack will be simultaneous. Now General A2 needs confirmation again.<\/p>\n

If we outline their communication further, we find the following: no matter how many cycles of message exchange occur, there is no way to guarantee that both generals will be notified that their messages have been received (provided that any of the messengers can be intercepted).<\/p>\n

The problem of two generals is an excellent illustration of a very simple distributed system, where there are two nodes with unreliable communication. This means that we do not have a 100% guarantee that they will synchronize. Similar problems are discussed in a larger scale in the following article.<\/p>\n

We introduce the concept of distributed systems.<\/h2>\n

\nA distributed system is a group of computers (hereafter referred to as nodes) that can exchange messages. Each individual node is a distinct autonomous entity. A node can independently process tasks, but in order to interact with other nodes, it needs to send and receive messages. <\/p>\n

The specific implementation of messages and the protocols used are not of interest to us in this context. It is important that nodes in a distributed system can exchange data with each other by sending messages.<\/p>\n

The definition itself seems not very complicated, but it is important to note that a distributed system has a number of attributes that will be significant for us.<\/p>\n

Attributes of Distributed Systems<\/h4>\n

<\/p>\n

    \n
  1. Concurrency<\/b> is the possibility of simultaneous or concurrent events occurring in the system. Moreover, we will consider that events occurring on two different nodes are potentially concurrent until we have a clear order of occurrence of these events. Typically, we do not have such an order.<\/li>\n
  2. Absence of Global Clocks<\/b>. We lack a clear order of events due to the absence of global clocks. In the ordinary world, we are accustomed to having clocks and absolute time. Everything changes when it comes to distributed systems. Even highly precise atomic clocks have drift, and there may be situations where we cannot determine which of two events occurred first. Therefore, we cannot rely on time either.<\/li>\n
  3. Independent Failure of System Nodes<\/b>. There is another issue: something might go wrong simply because our nodes are not eternal. A hard drive might fail, a virtual machine in the cloud may reboot, or the network may flicker and messages can be lost. Furthermore, there are situations where nodes are operational but are working against the system. This last class of issues has even been given a specific name: the problem of Byzantine Generals<\/a><\/noindex>. The most popular example of a distributed system facing such a problem is Blockchain. However, we will not be examining this particular class of problems today. We will be interested in situations where just one or more nodes may fail.<\/li>\n
  4. Communication Models (Message Exchange Models) Between Nodes<\/b>We have already established that nodes communicate by exchanging messages. There are two known messaging models: synchronous and asynchronous.<\/li>\n<\/ol>\n

    <\/p>\n

    Communication models between nodes in distributed systems<\/h4>\n

    \nSynchronous model<\/b> \u2013 we know exactly that there is a known finite time delta within which a message is guaranteed to reach from one node to another. If this time has elapsed and the message has not arrived, we can confidently say that the node has failed. In this model, we have a predictable wait time. <\/p>\n

    Asynchronous model<\/b> \u2013 in asynchronous models, we consider that the wait time is finite, but there is no delta time after which we can guarantee that a node has failed. That is, the wait time for a message from a node can be indefinite. This is an important definition, and we will discuss it further. <\/p>\n

    The concept of consensus in distributed systems<\/h2>\n

    \nBefore formally defining the concept of consensus, let's consider an example situation where it is needed, namely \u2013 State Machine Replication<\/b>. <\/p>\n

    We have some distributed log. We would like it to be consistent and contain identical data across all nodes of the distributed system. When one of the nodes learns a new value that it intends to write to the log, its task is to propose this value to all other nodes, so that the log is updated on all nodes, and the system moves to a new consistent state. It is important for the nodes to agree with each other: all nodes must agree that the proposed new value is correct, all nodes must accept this value, and only then can everyone log the new value. <\/p>\n

    In other words: no node objected that it has more up-to-date information, and the proposed value is incorrect. The agreement between nodes and consensus on a single correct accepted value is what consensus in a distributed system is. We will next discuss algorithms that allow the distributed system to reliably achieve consensus.
    \n\"Schr\u00f6dinger's
    \nMore formally, we can define a consensus algorithm (or simply a consensus algorithm) as a function that transitions a distributed system from state A to state B. This state is accepted by all nodes, and all nodes can confirm it. As it turns out, this task is not as trivial as it seems at first glance.<\/p>\n

    Properties of the Consensus Algorithm<\/h4>\n

    \nThe consensus algorithm must possess three properties for the system to continue to exist and make progress in transitioning from state to state:<\/p>\n

      \n
    1. Agreement <\/b> \u2013 all correctly functioning nodes must agree on the same value (this property is also referred to as the safety property in the literature). All nodes that are currently operational (not malfunctioning or disconnected from others) must reach consensus and accept a certain final shared value.\n

      It is important to understand that the nodes in the distributed system we are considering want to come to an agreement. In other words, we are talking about systems where something may fail (for example, some node may fail), but in this system, there are no nodes intentionally working against each other (the Byzantine Generals problem). Thanks to this property, the system remains consistent.<\/li>\n

    2. Integrity <\/b> \u2014 if all correctly functioning nodes propose the same value v<\/b>, then each correctly functioning node must accept that value. v<\/b>. <\/li>\n
    3. Termination <\/b>\u2013 all correctly functioning nodes will ultimately accept some value (the liveness property), allowing the algorithm to make progress within the system. Each individual correctly functioning node must eventually accept a final value and confirm: \u201cFor me, this value is true; I agree with the entire system.\u201d<\/li>\n<\/ol>\n

      <\/p>\n

      Example of Consensus Algorithm Operation<\/h4>\n

      \nWhile the properties of the algorithm may not be entirely clear, let's illustrate with an example what stages the simplest consensus algorithm goes through in a system with a synchronous message exchange model, where all nodes are functioning properly, messages are not lost, and nothing breaks (does this actually happen?).<\/p>\n

        \n
      1. Everything starts with a proposal of marriage (Propose). Let\u2019s assume that a client connects to a node called 'Node 1' and begins a transaction by sending a new value \u2013 O. From this point, we will refer to 'Node 1' proposer<\/b>. As proposer, 'Node 1' now needs to notify the entire system that it has fresh data, and it sends messages to all other nodes: 'Look! I received the value O, and I want to write it! Please confirm that you will also record O in your log.'\n

        \"Schr\u00f6dinger's<\/li>\n

      2. The next stage is voting on the proposed value (Voting). Why is it necessary? It may happen that other nodes have received newer information, and they have data regarding the same transaction.\n

        \"Schr\u00f6dinger's
        \n
        \nWhen 'Node 1' sends its proposal, the other nodes check their logs for data related to this event. If there are no discrepancies, the nodes declare: 'Yes, I have no other data related to this event. The value O is the most recent information we have obtained.' <\/p>\n

        In any other case, the nodes can respond to 'Node 1': 'Listen! I have more recent data on this transaction. Not O, but something better.'<\/p>\n

        At the voting stage, the nodes come to a decision: either everyone accepts the same value, or some vote against it, indicating that they have more recent data. <\/li>\n

      3. If the voting round was successful, and everyone was 'for', the system moves to a new stage \u2013 accepting the value (Accept). 'Node 1' collects all responses from other nodes and reports: 'Everyone agreed on the value O! I hereby declare that O is our new value, unified for all! Please write it down, don\u2019t forget. Log it!'\n

        \"Schr\u00f6dinger's<\/li>\n

      4. The other nodes send confirmation (Accepted) that they have recorded the value O, and nothing new has come in during this time (a form of two-phase commit). After this significant event, we consider that the distributed transaction has been completed.
        \n \"Schr\u00f6dinger's <\/li>\n<\/ol>\n

        \nThus, in a simple case, the consensus algorithm consists of four steps: propose, voting, accept, confirmation of acceptance.<\/p>\n

        If at any point we fail to reach consensus, the algorithm restarts, taking into account the information provided by the nodes that refused to confirm the proposed value.<\/p>\n

        Consensus Algorithm in an Asynchronous System<\/h2>\n

        \nUp until now, everything has been smooth, since we were discussing a synchronous message exchange model. However, we all know that in today's world, we are accustomed to operating asynchronously. So how does a similar algorithm work in a system with an asynchronous message exchange model, where we assume the response time from a node could be indefinitely long (by the way, a node failure can also be considered an example where a node may respond for an arbitrary time)? <\/p>\n

        Now that we understand the basic workings of the consensus algorithm, here\u2019s a question for the curious readers who have made it this far: how many nodes in a system of N nodes with an asynchronous messaging model can fail, while still allowing the system to reach consensus?<\/p><\/blockquote>\n

        \nThe correct answer and reasoning are behind the spoiler.<\/b>The correct answer is: 0<\/b>. If at least one node in an asynchronous system fails, the system cannot achieve consensus. This statement is proven in the well-known theorem FLP (1985, Fischer, Lynch, Paterson, link to the original at the end of the article): \u201cThe impossibility of achieving distributed consensus with the failure of at least one node.\u201d
        \n\"Schr\u00f6dinger's
        \nGuys, then we have a problem, we're used to everything being asynchronous. What now? How do we move forward? <\/p>\n

        We\u2019ve just talked about theory and mathematics. What does it mean that 'consensus cannot be reached' when translating from mathematical language to our engineering perspective? It means that 'it cannot always be achieved', i.e., there exists a case where consensus is unachievable. And what is that case? <\/p>\n

        This is precisely the violation of the liveness property described above. We lack a common agreement, and the system cannot make progress (cannot complete in finite time) when we lack responses from all nodes. Because in an asynchronous system, we do not have a predictable response time, and we cannot know if a node has failed or is simply responding slowly.<\/p>\n

        But in practice, we can find a solution. Let\u2019s say our algorithm can operate for an extended time in case of failures (potentially indefinitely). However, in most situations, when the majority of nodes are functioning correctly, we will see progress in the system. <\/p>\n

        In practice, we deal with partially synchronous communication models. Partial synchrony is understood as follows: generally, we have an asynchronous model, but the concept of 'global stabilization time' is formally introduced, marking a certain moment in time. <\/p>\n

        This moment may be indefinitely delayed, but it must eventually arrive. A virtual alarm will go off, and from that moment, we can predict the time delta for messages to be delivered. From that point, the system transitions from asynchronous to synchronous. In practice, we deal with such systems. <\/p>\n

        The Paxos algorithm addresses consensus problems.<\/h2>\n

        \nPaxos <\/a><\/noindex> is a family of algorithms designed to solve the consensus problem for partially synchronous systems, assuming that some nodes may fail. The author of Paxos is Leslie Lamport<\/a><\/noindex>. He proposed a formal proof of the existence and correctness of the algorithm in 1989. <\/p>\n

        However, the proof turned out to be quite nontrivial. The first publication was released only in 1998 (33 pages) describing the algorithm. As it turned out, it was extremely difficult to understand, and in 2001, a clarification of the article was published, which took 14 pages. The volume of publications is noted to show that the consensus problem is indeed not simple, and behind such algorithms lies the immense work of the smartest individuals.<\/p>\n

        Interestingly, Leslie Lamport himself noted in his lecture that in the second clarifying article, there is one statement, one line (he did not specify which), that can be interpreted differently. Due to this, a large number of modern implementations of Paxos do not work quite correctly. <\/p><\/blockquote>\n

        \nA detailed examination of the Paxos algorithm would require more than one article, so I will try to convey the main idea of the algorithm very succinctly. In the links at the end of my article, you will find materials for further exploration of this topic.<\/p>\n

        Roles in Paxos<\/h4>\n

        \nIn the Paxos algorithm, there is the concept of roles. Let's consider the three main ones (there are modifications with additional roles):<\/p>\n

          \n
        1. Proposers (also referred to as leaders or coordinators)<\/b>These are the guys who learn about a new value from the user and take on the role of leader. Their task is to initiate a round of proposing a new value and coordinate the further actions of the nodes. Moreover, Paxos allows for multiple leaders in certain situations.<\/li>\n
        2. Acceptors (Voters)<\/b>These are the nodes that vote to accept or reject a particular value. Their role is very important, as it is their decision that determines which state the system will transition to (or not) after the next stage of the consensus algorithm.<\/li>\n
        3. Learners<\/b>These are nodes that simply accept and record a newly accepted value when the state of the system changes. They do not make decisions, only receive data and can pass it to the end user. <\/li>\n<\/ol>\n

          \nOne node can combine several roles in different situations. <\/p>\n

          The concept of quorum<\/h4>\n

          \nWe assume that we have a system of N<\/b> nodes. Out of these, at most F<\/b> nodes can fail. If F nodes fail, then we must have at least 2F + 1<\/b> acceptor nodes. <\/p>\n

          This is necessary so that we always, even in the worst situation, have a majority of \"good\" nodes that are functioning correctly. That is, F + 1<\/b> \"good\" nodes that have agreed, and the final value will be accepted. Otherwise, there could be a situation when different local groups accept different values and cannot reach an agreement with each other. Therefore, we need an absolute majority to win the vote.<\/p>\n

          The general idea of the Paxos consensus algorithm<\/h4>\n

          \nThe Paxos algorithm consists of two major phases, which in turn are divided into two steps each:<\/p>\n

            \n
          1. Phase 1a: Prepare<\/b>. At the preparation stage, the leader (proposer) informs all nodes: \"We are starting a new voting phase. We have a new round. The number of this round is n. We will now begin voting.\" For now, he is simply announcing the start of a new cycle, but not disclosing a new value. The objective of this stage is to initiate a new round and inform everyone of its unique number. The round number is important; it must be a value greater than all previous voting numbers from earlier leaders. This is because the round number allows the other nodes in the system to understand how current the leader's data is. It\u2019s likely that the other nodes already possess voting results from much later rounds and will simply inform the leader that he is lagging behind.<\/li>\n
          2. Phase 1b: Promise<\/b>. When the acceptor nodes have received the number of the new voting stage, there are two possible outcomes: \n