Academic research
In our research we have found the same concurrency problems in the context of high-performance computing and blockchain networks.
Concurrency Problem
High-Performance Concurrent Programming Solution
Ethereum Blockchain Solution
Data organization
Concurrent data structures (hashmap, vector, skiplist)
Blockchain, comprising blocks of transactions
Consensus problem (i.e. how is the view of shared memory decided)
Atomic variables combined with semantics defined by memory model (relaxed, sequentially consistent)
Proof-of-stake, active validators stake 32 ETH and are pseudo-randomly selected as block proposer for a slot
Race conditions
Mutexes, semaphores, compare-and-swap
A single beacon block is proposed per slot, and the beacon block is executed sequentially
Correctness
Correctness conditions (linearizability, sequential consistency)
Beacon block re-executed by validators assigned to attest to the beacon block
Unresponsive threads
Lock-free, wait-free progress algorithmic guarantee
Requirement of 2/3 attestation for proposed block, penalty when validator misses attestation
Malicious threads
Concurrency bug finding tools
Requirement of 32 staked ETH, slashing
Resource allocation
I/O, CPU resources, cache lines, database
Communication overhead, gas fees, blockspace
Zachary Painter and Damian Dechev, Lock-Free Concurrent Smart Contracts, In Proceedings of the 6th IEEE International Conference on Blockchain and Cryptocurrency (ICBC 2024), Dublin, Ireland, May 27-31, 2024.
Victor Cook, Christina Peterson, Zachary Painter, Damian Dechev, Quantifiability: a concurrent correctness condition modeled in vector space, Computing 105: 955–978, 2023. Funding: NSF grants OAC 1740095 and CCF 1717515. https://link.springer.com/article/10.1007/s00607-022-01092-3
Victor Cook, Christina Peterson, Zachary Painter, and Damian Dechev, Design and Implementation of Highly Scalable Quantifiable Data Structures, In Proceedings of the 16th International Conference on Parallel Computing Technologies (PaCT 2021), Kaliningrad, Russia, September 13-18, 2021. https://link.springer.com/chapter/10.1007/978-3-030-86359-3_28
Zachary Painter, Victor Cook, Christina Peterson, and Damian Dechev, Descriptor Based Consensus for Blockchain Transactions, In Proceedings of the 15th ACM International Conference On Distributed And Event-Based Systems (DEBS 2021), Online, June 28 – July 2, 2021. https://dl.acm.org/doi/10.1145/3465480.3466927
Victor Cook, Christina Peterson, Zachary Painter, Damian Dechev, Quantifiability: Correctness of Concurrent Programs in Vector Space, In Proceedings of the 29th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP 2021), Online, March 10-12, 2021. Funding: NSF grants OAC 1740095 and CCF 1717515. https://ieeexplore.ieee.org/document/9407133
Zachary Painter, Pradeep Kumar Gayam, Victor Cook, Damian Dechev, Parallel Hash-Mark-Set on the Ethereum Blockchain, In the 2nd IEEE International Conference on Blockchain and Cryptocurrency (ICBC 2020), Toronto, Canada, May, 2020. Funding: NSF grants OAC 1740095 and CCF 1717515. https://ieeexplore.ieee.org/abstract/document/9169415
Victor Cook, Christina Peterson, Zachary Painter, Damian Dechev, Quantifiability: a concurrent correctness condition modeled in vector space, Computing 105: 955–978, 2023. Funding: NSF grants OAC 1740095 and CCF 1717515. https://link.springer.com/article/10.1007/s00607-022-01092-3
Victor Cook, Christina Peterson, Zachary Painter, and Damian Dechev, Design and Implementation of Highly Scalable Quantifiable Data Structures, In Proceedings of the 16th International Conference on Parallel Computing Technologies (PaCT 2021), Kaliningrad, Russia, September 13-18, 2021. https://link.springer.com/chapter/10.1007/978-3-030-86359-3_28
Zachary Painter, Victor Cook, Christina Peterson, and Damian Dechev, Descriptor Based Consensus for Blockchain Transactions, In Proceedings of the 15th ACM International Conference On Distributed And Event-Based Systems (DEBS 2021), Online, June 28 – July 2, 2021. https://dl.acm.org/doi/10.1145/3465480.3466927
Victor Cook, Christina Peterson, Zachary Painter, Damian Dechev, Quantifiability: Correctness of Concurrent Programs in Vector Space, In Proceedings of the 29th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP 2021), Online, March 10-12, 2021. Funding: NSF grants OAC 1740095 and CCF 1717515. https://ieeexplore.ieee.org/document/9407133
Zachary Painter, Pradeep Kumar Gayam, Victor Cook, Damian Dechev, Parallel Hash-Mark-Set on the Ethereum Blockchain, In the 2nd IEEE International Conference on Blockchain and Cryptocurrency (ICBC 2020), Toronto, Canada, May, 2020. Funding: NSF grants OAC 1740095 and CCF 1717515. https://ieeexplore.ieee.org/abstract/document/9169415
Christina Peterson, Victor Cook, Damian Dechev, Practical Progress Verification of Descriptor-Based Non-Blocking Data Structures, In Proceedings of the 27th IEEE International Symposium on the Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS 2019), Rennes, France, October 22-25, 2019. Funding: NSF grants OAC 1740095 and CCF 1717515. https://ieeexplore.ieee.org/document/8842986
Victor Cook, Zachary Painter, Christina Peterson, Damian Dechev, Read-Uncommitted Transactions for Smart Contract Performance, In Proceedings of the 39th IEEE International Conference on Distributed Computing Systems (ICDCS 2019), Dallas, TX, July 7-10, 2019. Funding: NSF grants OAC 1740095 and CCF 1717515. https://ieeexplore.ieee.org/document/8884987
Christina Peterson, Damian Dechev, A Transactional Correctness Tool for Abstract Data Types, ACM Transactions on Architecture and Code Optimization, Vol. 14, No. 4, Article 37, December 2017. https://dl.acm.org/doi/10.1145/3148964
Fraser, Keir. Practical lock-freedom. No. UCAM-CL-TR-579. University of Cambridge, Computer Laboratory, 2004. https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.html
Deli Zhang, Damian Dechev, Lock-free Transactions Without Rollbacks for Linked Data Structures, In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), Pacific Grove, CA, July 2016. Funding: NSF ACI 1440530. https://dl.acm.org/doi/10.1145/2935764.2935780
Victor Cook, Zachary Painter, Christina Peterson, Damian Dechev, Read-Uncommitted Transactions for Smart Contract Performance, In Proceedings of the 39th IEEE International Conference on Distributed Computing Systems (ICDCS 2019), Dallas, TX, July 7-10, 2019. Funding: NSF grants OAC 1740095 and CCF 1717515. https://ieeexplore.ieee.org/document/8884987
Christina Peterson, Damian Dechev, A Transactional Correctness Tool for Abstract Data Types, ACM Transactions on Architecture and Code Optimization, Vol. 14, No. 4, Article 37, December 2017. https://dl.acm.org/doi/10.1145/3148964
Fraser, Keir. Practical lock-freedom. No. UCAM-CL-TR-579. University of Cambridge, Computer Laboratory, 2004. https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.html
Deli Zhang, Damian Dechev, Lock-free Transactions Without Rollbacks for Linked Data Structures, In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), Pacific Grove, CA, July 2016. Funding: NSF ACI 1440530. https://dl.acm.org/doi/10.1145/2935764.2935780
Join the network
We are here to help Ethereum.
We welcome collaborators.
© 2024 ETHPAR, All Rights Reserved.
