Understanding Block chain for Enterprises: Permissioned Block chain: Permissioned model and use cases, Design issues for Permissioned block chains, Execute contracts, State machine replication, Overview of Consensus models for permissioned block chain- Distributed consensus in closed environment, Paxos, RAFT Consensus, Byzantine general problem, Byzantine fault tolerant system, Lamport-Shostak-Pease BFT Algorithm, BFT over Asynchronous systems.

State machine replication

State machine replication is usually defined through a set of clients submitting commands
to a set of replicas behaving as a “centralized” service, or a replicated state machine
(RSM).

Understanding of State Machine Concept

State Machine is characterized by a set of parameters such as set of Inputs, set of Outputs, and the Transition States. 

• A set of state (S) based on the system design
• A set of inputs (I)
• A set of outputs (O)
• A transition function S x I –> S; takes the current state and input value and produces a set as the output.
• A output function S x I –> O
• A start state

▪Ensure correct replicas step through the same sequence of state transitions

▪Need distributed consensus (PAXOS?) to ensure same sequence of input requests to all replicas Client Network Replica

Some problems with SMR systems

1.Cannot handle ‘multi-threaded’ programs (which most server programs are!) – Sources of non-determinism: thread interleaving, scheduling, environment variables etc.

2.Narrowly defined consensus interfaces and require program modification. – Often tailor-made to fit requirements – e.g Chubby – a locking service.

Solution: CRANE (Correctly ReplicAting Nondeterministic Executions)

• A ‘transparent’ SMR system.
• Focus on functionality (not replication) – run any program on top of CRANE without any modification.

Now to ensure that you need to have a kind of consensus algorithm in the system now why do we apply this kind of state machine replication-based consensus algorithm in a permission model in contrast to the challenge response-based consensus model which we applied for the permissionless setting.

• There are certain natural reasons to use state machine-based consensus algorithms over permission blockchain.
• The first reason is that the network is closed so when the network is closed every individual node they know each other.
• State replication is possible among the known nodes.
• If you know that who are your peers, you can always replicate your state machine with the current state to your peers the second thing is that this state machine replication-based scenario it avoids the overhead of mining.
• Mining has a sign over it in terms of the system power that you are using in terms of the time that you are providing and amount of Bitcoin that you are you may apply for this kind of proof of state-based mechanism so or proof of elapsed time best mechanism.
• It is like that either in case of a challenge-response method either you have to spend your physical assets, or you have to spend your digital assets and it will take a certain time to solve that particular challenge.
• That has significant kind of over it in case of a permissionless setting but in case of a permission model because we know the participant each other and in case of a state machine replication you do not have this kind of over it where you must spend your physical asset or some kind of virtual assets rather what you have to do that you have to employ certain kind of message passing algorithm in the system.
• You can avoid the overhead of mining by applying this kind of state machine replication-based method but as I have mentioned that consensus is still required on top of the state machine replication because the machines can be faulty, or they can behave maliciously.

Distributed consensus in closed environment

So what is a consensus in a distributed system?

Concept of consensus is an interesting topic in a decentralized or in a distributed network. consensus means it is a procedure to reach in a common agreement in a decentralized or in a distributed platform. It is important for the message passing system.

Example:

• An army there are 4 generals and a generals are taking some kind of decisions.
• And when the generals are taking the decisions in a decentralized on a distributed way; that means, they have their own policies to take the decision they can either make an attack or can reflect from the attack.
• These generals individually they express their opinion their individual opinion.
• Applying opinion some kind of choice function, which can be the majority decision in this particular case.
• 3 generals they are making a choice towards attack. So, with the majority principle the system can come to a consensus that a they should make a attack collectively.
• When the number of decision involving the agreement goes higher, the complexity of achieving consensus is going higher too.

What is a Distributed System

• Collection of independent computers that appear to its users as a single coherent system. • Every system has its own memory and its own set of resources and they can share some common peripheral devices such as a printer.

• Systems are organized in such a manner so as to hide their existence from the end user. • Transparency is to be maintained-ISO(8 kind of transperanacy)

• Message passing or RPC technique through communication technology such as TCP/IP.

Examples – 

• Commit a transaction in a database
• State machine replication
• Clock synchronization.

Why distributed consensus?

• Nodes in distributed systems are trying to achieve some common goal (maybe processing a large computation). Then they need some kind of coordination among them.
• They need to know the effect of their doings to the whole system. That’s where distributed systems need a consensus protocol.
• In any distributed consensus protocol a node can say “Guys, I SUGGEST value v. Do you all agree?” 💡. Only after all of the other nodes AGREED 🤝 on v, each node (including suggesting node) can carry on their work keeping “v is decided” in their mind.
• ·Another node can also say “I prefer w.” and SUGGEST another value(w) before the system decides v. Then the distributed system should choose either v or w. In such a case, achieving consensus is a bit complicated process.

Features

• It ensures reliability and fault tolerance in distributed systems.
• In the presence of faulty individuals, it is Ensure correct operations.

Types of Failure in a Distributed consensus

Distributed consensus: Properties

There are some conditions that need to be followed in order to achieve distributed consensus.

• Termination –
  Every non-faulty process must eventually decide.
• Agreement –
  The final decision of every non-faulty process must be identical.
• Validity –
  Every non-faulty process must begin and ends with the same value.
• Integrity –
  Every correct individual decides at most one value, and the decided value must be proposed by some individual.

The correctness of Distributed Consensus Protocol :   

It can be described by the following two properties as follows.

• Safety Property –
  It ensures that you will never converge to an incorrect value or correct individuals in a network will never converge to an incorrect value.
• Liveness Property –
  It states that every correct value must be accepted eventually which means something good will eventually happen.

To make it easier to develop algorithms in the real world, we can relax the definition of asynchronous and allow some synchrony. Several types of asynchrony may exist in a system:

Consider 2 different type of message passing system, one type of message passing system we call as the synchronous message passing system and the second one is the asynchronous message passing system.

Synchronous message passing system: the message must be received within a predefined time interval. So, we have a kind of strong guarantee on the message passing delay and you know apriori that what can be the maximum delay of message passing for this particular network.

Each message is received within bounded time

– Drift of each process’ local clock has a known bound

– Each step in a process takes lb < time < ub

E.g., A collection of processors connected by a communication bus, e.g., a Cray supercomputer or a multicore machine

Asynchronous message passing system: There is no upper bound on the message transmission delay or the message reception time. No any such constraint message can be arbitrary delayed or the message delivery time can be arbitrarily long.

•Asynchronous Distributed System

• No bounds on process execution
• The drift rate of a clock is arbitrary
• No bounds on message transmission delays

E.g., The Internet is an asynchronous distributed system, so are ad-hoc and sensor networks.

This is a more general (and thus challenging) model than the synchronous system model. A protocol for an asynchronous system will also work for a synchronous system (but not vice-versa).

Consensus is solvable or not

In the synchronous system model

–Consensus is solvable

In the asynchronous system model

• Consensus is impossible to solve
• Whatever protocol/algorithm you suggest, there is always a worst
• case possible execution (with failures and message delays) that prevents the system from reaching consensus
• Powerful result (see the FLP proof in the Optional lecture of this series)
• Subsequently, safe or probabilistic solutions have become quite popular to consensus or related problems.