EOS whitepaper walk-through: Deterministic Parallel Execution of Applications, overview.

in eos •  8 months ago


Read the Whitepaper here 

Last time we went over the Account construct of EOS in Four parts. Part One, Part Two, Part Three, Part Four.

Deterministic Parallel Execution of Applications

Blockchain consensus depends upon deterministic (reproducible) behavior. This means all parallel execution must be free from the use of mutexes or other locking primitives. Without locks there must be some way to guarantee that transactions that may be executed in parallel do not create non-deterministic results.

What a blockchain represents is a current state of affair based on a history of events that has happened. Anyone, by applying the same sequence of events can arrive at the same state. How can we parallelize the performance of actions that are meant to be applied sequentially?

The use of mutexes is a way to allow many different calculation to be done on a shared file but not at the same time. But it is not certain which calculation will take place first. This breaks the deterministic behavior of the blockchain, rendering it unfit to use for the purpose of a ledger.

The challenge here is how do we reproduce this deterministic behavior, while performing the actions in parallel? After all, if we apply the events in different order, does it not generate a different outcome?

The June 2018 release of EOS.IO software will run single threaded, yet it contains the data structures necessary for future multithreaded, parallel execution.

Just a clarification on the road map of EOS.IO software.

In an EOS.IO software-based blockchain, once parallel operation is enabled, it will be the job of the block producer to organize Action delivery into independent shards so that they can be evaluated in parallel. The schedule is the output of a block producer and will be deterministically executed, but the process for generating the schedule need not be deterministic. This means that block producers can utilize parallel algorithms to schedule transactions.

Shards is a way to achieve the same result as using mutexes. By dividing the database into not-overlapping sections, we can ensure that although the calculation is applied in parallel, they will not produce a different outcome when ran again.

The block-producer is responsible for dividing the incoming action/message and scheduling their order. Parallel algorithms can be applied to perform this scheduling task. Once a schedule is produced, other block-producer can follow this schedule to run parallel executing of actions and arrive at the same state.

Part of parallel execution means that when a script generates a new Action it does not get delivered immediately, instead it is scheduled to be delivered in the next cycle. The reason it cannot be delivered immediately is because the receiver may be actively modifying its own state in another shard. 

EOS blocks are further divided into regions, which are divided into shards. Each shard contains a transaction that is evaluated in parallel, but the results are not applied until the next cycle, to prevent another shard from applying a different calculation to the same data region.

In the next article we'll go more in-deepth in how blocks are structured hierarchically in EOS.


Useful links: 


If you would like to know more about me and what I'm doing you can read my introduction post here.

EOS whitepaper walk-through. Abstract

EOS whitepaper walk-through. Note and Disclaimer

EOS whitepaper walk-through. Overview

EOS whitepaper walk-through. Background

EOS whitepaper walk-through. Requirement.

EOS whitepaper walk-through. Consensus Algorithm. Part One, Part Two, Part Three.

EOS whitepaper walk-through. Account construct of EOS. Part One, Part Two, Part Three, Part Four.

And you can contact me in the following way:


@bluabaleno on Steem.chat


Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  

That's great! upvoted and good luck!

Nice explanation as always! Wasn't aware sharding is already prepared in EOS, so the day that Vitalik announces sharding is coming, hedgehog EOS is - once again - already there....


Sharding is not yet ready in EOS, just like it isn't ready in Ethereum. However, once it is ready, EOS will be able to implement it as soon Ethereum.