A smart contract is a special type of transaction designed for the execution of automated logic on blockchains. Alas, smart contracts transactions are one of the major hindrances to blockchain throughput. Hence, improving the execution time of smart contracts is a prime challenge for Blockchains at large. To that end, concurrent execution of smart contract is an appealing direction, which has been adopted by several contemporary Blockchains like Solana, Aptos, Sui, Sei, and Monad. Executing smart contracts in parallel requires applying deterministic concurrency controls based on ensuring consistent ordering of all conflicting transactions in all miners/validators. Existing implementations rely on the Block's total ordering to resolve this requirement. Recently, it has been suggested that relying on minimal coloring of the conflict graph corresponding to the Block's transactions can provide a better performance potential, yet without any evaluation. In this paper, we compare between approaches to smart contracts parallelization. Our study’ finds that in many situations, indeed the coloring-based ordering leads to significantly better performance than the Block order preserving approach. However, this gain has its limits, and it is not always guaranteed. In particular, the results are largely dependent on the conflict ratio in the conflict graph and the type of application.

ABSTRACT A parameter crucial for preserving the underlying shortest path information in spanning tree construction is called stretch. It is the ratio of the distance of a pair of nodes in the spanning tree to their shortest distance in the graph. In this paper, we present a distributed heuristic LSTree that constructs a Minimum Average Stretch Spanning Tree of an undirected and unweighted graph in rounds of the CONGEST model, assuming the nodes know the size of the network. We like to stress that the LSTree protocol is the first use of Betweenness Centrality in constructing low‐stretch trees. The heuristic outperforms the current benchmark algorithm of Alon et al. and other spanning tree construction techniques when tested against synthetic and real‐world graph inputs. This paper concludes after giving a distributed edge addition technique for building an overlay while reducing the maximum stretch in the spanning tree generated by LSTree. The overlay is a relaxation in the topological requirement, albeit equivalent in functionality to the network backbone. Hence, in this way, the paper considers a holistic view towards building low‐stretch spanning trees: reducing both average stretch and max stretch in a single approach.

Lock-free concurrent data structures offer throughput with scalability and guarantees for the completion of operations on multicore computers. Recently, queries using machine learning models trained to predict the data distribution have gained remarkable attention. Yet, to our knowledge, no existing lock-free data structure employs them. This paper introduces a lock-free search structure that supports concurrent updates, membership, and range queries accelerated by a shallow hierarchy of lightweight machine learning models. The proposed approach significantly outperforms the current state-of-the-art lock-free data structures in many workload and data distribution settings. Ours is the first provably linearizable learned lock-free concurrent range search index.

This paper introduces a lock-free linearizable search structure that supports concurrent updates, membership, and range queries accelerated by a shallow hierarchy of lightweight machine learning (ML) models. The proposed approach significantly outperforms the current state-of-the-art lock-free data structures in many workload and data distribution settings.

Replicated tree data structures are extensively used in collaborative applications and distributed file systems, where clients often perform move operations. Local move operations at different replicas may be safe. However, remote move operations may not be safe. When clients perform arbitrary move operations concurrently on different replicas, it could result in various bugs, making this operation challenging to implement. Previous work has revealed bugs such as data duplication and cycling in replicated trees. In this paper, we present an efficient algorithm to perform move operations on the distributed replicated tree while ensuring eventual consistency. The proposed technique is primarily concerned with resolving conflicts efficiently, requires no interaction between replicas, and works well with network partitions. We use the last write win semantics for conflict resolution based on globally unique timestamps of operations. The proposed solution requires only one compensation operation to avoid cycles being formed when move operations are applied. The proposed approach achieves an effective speedup of 14.6× to 68.19× over the state-of-the-art approach in a geo-replicated setting.

Replicated tree data structures are extensively used in collaborative applications and distributed file systems, where clients often perform move operations. Local move operations at different replicas may be safe. However, remote move operations may not be safe. We present an efficient algorithm to perform move operations on the distributed replicated tree while ensuring eventual consistency. The proposed technique is primarily concerned with resolving conflicts efficiently, requires no interaction between replicas, and works well with network partitions. We use the last write win semantics for conflict resolution based on globally unique operation timestamps. The proposed solution requires only one compensation operation to avoid cycles being formed when move operations are applied. The proposed approach achieves an effective speedup of 14.6-68.19× over the state-of-the-art approach in a geo-replicated setting,

A parameter crucial for preserving the underlying shortest path information in spanning tree construction is called stretch. It is the ratio of the distance of two nodes x and y in the spanning tree to the shortest distance between x and y in the graph. In this paper, we present a heuristic LSTree that constructs a Minimum Average Stretch Spanning Tree of an n− node undirected and unweighted graph in $\mathcal{O}$(n) rounds of the CONGEST model. We like to stress that LSTree protocol is the first use of Betweenness centrality in the construction of low stretch trees. The heuristic outperforms the current benchmark algorithm of Alon et. al. as well as other spanning tree construction techniques presently known, when tested against synthetic as well as real-world graph inputs.

Summary Contemporary blockchain such as Bitcoin and Ethereum execute transactions serially by miners and validators and determine the Proof‐of‐Work (PoW). Such serial execution is unable to exploit modern multi‐core resources efficiently, hence limiting the system throughput and increasing the transaction acceptance latency. The objective of this work is to increase the transaction throughput by introducing parallel transaction execution using a static analysis over the transaction dependencies. We propose the DiPETrans framework for distributed execution of transactions in a block. Here, peers in the blockchain network form a community of trusted nodes to execute the transactions and find the PoW in‐parallel, using a leader–follower approach. During mining, the leader statically analyzes the transactions, creates different groups (shards) of independent transactions, and distributes them to followers to execute concurrently. After execution, the community's compute power is utilized to solve the PoW concurrently. When a block is successfully created, the leader broadcasts the proposed block to other peers in the network for validation. On receiving a block, the validators re‐execute the block transactions and accept the block if they reach the same state as shared by the miner. Validation can also be done in parallel, following the same leader–follower approach as mining. We report experiments using over 5 million real transactions from the Ethereum blockchain and execute them using our DiPETrans framework to empirically validate the benefits of our techniques over a traditional sequential execution. We achieve a maximum speedup of 2.2 and 2.0 and an average speedup of 1.6 and 1.5 for the miner and the validator, respectively, with 100–500 transactions per block when using 6 machines in the community. Further, we achieve a peak of 5 end‐to‐end block creation speedup using a parallel miner over a serial miner.

PageRank algorithm is a benchmark for many graph analytics and is the underlying kernel for link predictions, recommendation systems. It is an iterative algorithm that updates ranks of pages until the value converges. Implementation of PageRank algorithm on a shared memory architecture while taking advantage of fine-grained parallelism using large-scale graphs is a challenging task. In this paper, We present parallel algorithms for computing the PageRank suitable to the shared memory systems. Initially, we present parallel implementations of page-rank algorithms using barrier and lock variants. Later, we propose new approaches which are lock-free and are barrier-less synchronization to overcome the issues of lock based methods. A detailed experimental analysis of our approach is carried out using real-world web graphs from SNAP and Synthetic Graphs from RMAT on an Intel(R) Xeon E5-2660 v4 processor architecture with 56 threads using the POSIX thread library.

This paper reports a new concurrent graph data structure that supports updates of both edges and vertices and queries: Breadth-first search, Single-source shortest-path, and Betweenness centrality. The operations are provably linearizable and non-blocking.

Spanning trees are widely used as a communication backbone over some given infrastructure and help network designers achieve a low-cost communication overhead. Spanning trees are generally designed, keeping in mind some optimizing metric (most general being sum of edge weights in a Minimum Spanning Tree) with respect to the underlying graph. For applications that require preserving shortest path distances between nodes of the weighted underlying graph in the abstracted spanning tree, we look to minimize a parameter known as stretch. Stretch is defined as the ratio of the distance between two nodes in the tree to its shortest path distance in the communication graph.To make spanning-tree constructions resilient to edge failures in an error-prone environment, we consider what is called the All Best Swap Edges (ABSE) problem. Since every edge in a tree is a bridge edge, a single edge failure disconnects the tree into two connected components. In the ABSE problem, for each edge e in the spanning tree, we compute a swap edge f corresponding to e, that is activated when e fails. f helps to restore the communication in the tree by connecting the disconnected components.In this paper, we give a novel distributed algorithm to efficiently construct a low average stretch spanning tree and make it robust against edge failures by finding a swap edge for every edge in the constructed tree. This is the first known deterministic distributed algorithm for constructing a low stretch tree that is also edge fault-tolerant. The distributed ABSE computation in our case equals the state-of-the-art running time of O(h) rounds, where h is the height of the tree.

Blockchain platforms such as Ethereum and several others execute complex transactions in blocks through user-defined scripts known as smart contracts. Normally, a block of the chain consists of multiple transactions of smart contracts which are added by a miner. To append a correct block into the blockchain, miners execute these transactions of smart contracts sequentially. Later the validators serially re-execute the smart contract transactions of the block. If the validators agree with the final state of the block as recorded by the miner, then the block is said to be validated. It is then added to the blockchain using a consensus protocol. In Ethereum and other blockchains that support cryptocurrencies, a miner gets an incentive every time such a valid block successfully added to the blockchain. In most of the current day blockchains the miners and validators execute the smart contract transactions serially. In the current era of multi-core processors, by employing the serial execution of the transactions, the miners and validators fail to utilize the cores properly and as a result, have poor throughput. By adding concurrency to smart contracts execution, we can achieve better efficiency and higher throughput. In this paper, we develop an efficient framework to execute the smart contract transactions concurrently using optimistic Software Transactional Memory systems (STMs). Miners execute smart contract transactions concurrently using multi-threading to generate the final state of blockchain. STM is used to take care of synchronization issues among the transactions and ensure atomicity. Now when the validators also execute the transactions (as a part of validation) concurrently using multi-threading, then the validators may get a different final state depending on the order of execution of conflicting transactions. To avoid this, the miners also generate a block graph of the transactions during the concurrent execution and store it in the block. This graph captures the conflict relations among the transactions and is generated concurrently as the transactions are executed by different threads. The miner proposes a block which consists of set of transactions, block graph, hash of the previous block, and final state of each shared data-objects. Later, the validators re-execute the same smart contract transactions concurrently and deterministically with the help of block graph given by the miner to verify the final state. If the validation is successful then proposed block appended into the blockchain and miner gets incentive otherwise discard the proposed block. We execute the smart contract transactions concurrently using Basic Time stamp Ordering (BTO) and Multi-Version Time stamp Ordering (MVTO) protocols as optimistic STMs. BTO and MVTO miner achieves 3.6x and 3.7x average speedups over serial miner respectively. Along with, BTO and MVTO validator outperform average 40.8x and 47.1x than serial validator respectively.

Summary In this paper, we propose an enhanced Automatic Checkpointing and Partial Rollback (CaPR++) algorithm to realize Software Transactional Memory (STM), that employs partial rollback mechanism for conflict resolution. We have comparatively evaluated the “Abort” and “Partial Rollback” mechanisms for STMs. For purposes of comparison, we have used the state‐of‐the‐art RSTM system and for the “Partial Rollback”, and we have used our earlier CaPR+ algorithm that has been enhanced for our requirements. Note that we have enriched the STAMP benchmarks with varied delayed transaction times. The results obtained demonstrate the effectiveness of the Partial Rollback mechanism over pure abort mechanisms for applications consisting of large transaction delays, with up to 1.6x performance gain for applications with large transactional delays. Our study makes the case for a hybrid system of pure aborts and partial rollbacks, which can extract the benefits of both mechanisms. Keeping in line with our study, we have proposed a hybrid implementation where some of the transactions of an application subscribe to abort mechanisms and the rest to partial rollback. Our initial implementation demonstrates various scenarios where the hybrid approach outperforms the pure abort and partial rollback approaches.

The group mutual exclusion problem extends the traditional mutual exclusion problem by associating a type (or a group) with each critical section. In this problem, processes requesting critical sections of the same type can execute their critical sections concurrently. However, processes requesting critical sections of different types must execute their critical sections in a mutually exclusive manner. We present a distributed algorithm for solving the group mutual exclusion problem based on the notion of surrogate-quorum. Intuitively, our algorithm uses the quorum that has been successfully locked by a request as a surrogate to service other compatible requests for the same type of critical section. Unlike the existing quorum-based algorithms for group mutual exclusion, our algorithm achieves a low message complexity of O(q) and a low (amortized) bit-message complexity of O(bqr), where q is the maximum size of a quorum, b is the maximum number of processes from which a node can receive critical section requests, and r is the maximum size of a request while maintaining both synchronization delay and waiting time at two message hops. As opposed to some existing quorum-based algorithms, our algorithm can adapt without performance penalties to dynamic changes in the set of groups. Our simulation results indicate that our algorithm outperforms the existing quorum-based algorithms for group mutual exclusion by as much as 45 percent in some cases. We also discuss how our algorithm can be extended to satisfy certain desirable properties such as concurrent entry and unnecessary blocking freedom.