Blockchain Technology Comprehension. A Survey On Distributed Systems -Part 2

^{Licensed under Creative Commons Attribution-Share Alike 4.0 International license. Source}

Safety and Liveness

When executing a program it can run a single isolated set of operations, or it can run several sets simultaneously. Thus, we have sequential programs and concurrent programs. A concurrent program is one in which several streams of operations are executed simultaneously, those streams can communicate and interfere with each other. Those sequences of instructions are called threads, that is why sequential programs are often called single-threaded programs

Even so, any program π can by specified in terms of its sets of atomic actions (A_π) and a predicate (Init_π) that describes its possible initial states. An execution of such a program can be thought of as an infinite series of states:

State S ₀ satisfies Init_π, the program changes its actual state as the result of the application of a single atomic operation from A_π to the current state. Following this reasoning, we have that a termination execution is one in which an infinite sequence is obtained by repeating the final state. That is, after some finite time we have a constant state on our infinite sequence.

Since a Property is a set of sequences of infinite states, and a program also defines a set of such sequences, it is said that a Property "holds" for a program if the set of infinite series of states defined by the program are contained within the Property.

Now, let S be the set of program states, S ^* the finite sequence of program states, and S^w the set of infinite sequences of program states. An execution of the program has to be contain in S^w, thus elements of S^w are also called program executions, and elements of S ^* are called partial program executions. When a execution σ is in property P it is denoted as σ|=P, and σ_i are the elements of the partial execution of σ containing the first i elements of execution σ.

Safety

For P to be a safety property, if P does not hold for an execution, then at some point some "bad thing" must happen. Thus, P is a safety property if the following holds:

Then the definition stipulates that if "something bad" does occur, there is some identifiable point i at which it happens.

Liveness

For a property P to be a liveness property, we must verify that:

A liveness property states that when executing a program eventually the expected outcome does occur.

Once we are done considering these concepts, it is clear that Availability is a Liveness property. When we say that we have availability we state that eventually, we will receive a response from the network (something good eventually happens). Also, we can state that Consistency is a Safety property. Remember that we label a system as one with high consistency if the answer obtained from it is always what we were expecting (something bad never happens).

In an asynchronous system, there are three conditions that must be met in order to reach consensus. First, agreement: every process must output the same value; validity: every value output must have been provided as the input for some process; and termination: eventually, every process must output a value. From the above definitions of, it is clear that agreement and validity both states that for the property to hold, the expected outcome must occur! It is equivalent to stating that for the property to hold no unexpected outcomes occur, thus they are safety properties. Similarly, terminations conditions are clearly those of a liveness property.

Dealing with the Safety/Liveness trade-off: Synchrony

In order to determine what levels of reliability are required to avoid the inherent trade-off between safety and liveness, the degree of synchrony on a network should be analyzed. A synchronous network must have these characteristics: first, all the process within the network has a clock and all the clocks are synchronized; second, messages are delivered within a determined and known amount of time; and third, each process of the networks perform a task at an invariant and known rate. This system can be considered to operate in rounds of repeated and synchronized steps. In those rounds, each process sends some messages, receive the messages sent to them in that round, and perform some individual computation.

Consensus requires f + 1 rounds if up to f processes might crash in a synchronous network. In an asynchronous network, consensus is unfeasible if there is only one crash failure. Fortunately, a mean point is usually achieved for real systems. Most real systems reach Eventual Synchrony, it is achieved when a process has some periods of synchrony and some periods of asynchrony, such processes can reach consensus if the synchronous interval lasts long enough. Eventual synchronous system reaches consensus if at least f + 2 rounds are executed within the synchrony interval. Also, crash-fault tolerance is achieved if there are <n/2 crash failures, where "n" is the number of servers.

Some other approaches lead to the implementation of an Oracle, this process executes a leader election service and provides sufficient information to reach consensus in an asynchronous crash-prone system. Moreover, there is a perspective focused on establishing the lower reliability levels of linking between the process in the network and the minimal synchrony assumptions to reach consensus in an asynchronous system.

How consistent a lively, partition-prone network can be?

The consensus problem requires that an asynchronous and distributed set of process agree on a common value among themselves. Additionally, this has to be done in the presence of a number of faulty processes and all processes must output some value and terminate.

Set-agreement is a "weaker" agreement condition in which process must not agree on a single value but in a set of values. In this condition, each process begins with a certain value v_i and eventually, every process outputs one of the initial values as the result of an execution. In k-set consensus, each process decides on a single value such that the set of agreed values in any run is of size at must k. K-set agreement can be solved if the number of crash failures is equal or lesser than k-1 and is the higher consistency that can be reached without giving up availability in a system with k-1 failures.

Distributed systems have major theoretical limitations, those limitations have to be dealt ingeniously to achieve the desired levels of reliability in blockchain technology. Major advances have been made from the initials operations with bitcoin to the present times. Several hundreds of projects have implemented subtle variations on consensus algorithms to reach the fittest balance of safety/liveness trade-off for their individual goals. A solid foundation on the theoretical concepts that determine the nature of this trade-off is a key aspect to fully understand the blockchain technology.

References

• Seth Gilbert and Nancy Lynch. Perspectives on the CAP Theorem. IEEE Computer Society Press, February 2012.
• S. Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Information & Computation, 105(1):132–158, 1993
• Fischer M, Lynch N, and Paterson N. Impossibility of Distributed Consensus with One Faulty Process, in "ACM Symposium on Principles of Database Systems". April 1985
• Bowen Alpern and Fred B. Schneider. Recognizing safety and liveness. Distributed Computing September 1987, Volume 2, Issue 3, pp 117–126