[논문 세미나] Batch-Schedule-Execute: On Optimizing Deterministic Concurrent Scheduling

Title:

Batch-Schedule-Execute: On Optimizing Deterministic Concurrent Scheduling

 

Authors:

Hay, Yaron and Friedman, Roy.

 

Journal/Conference:

SRDS '24

 

Source: https://ieeexplore.ieee.org/document/10806617, https://arxiv.org/abs/2402.05535

 

Abstract:

Executing smart contracts is a compute and storage-intensive task, which currently dominates modern blockchain's performance. Given that computers are becoming increasingly multicore, concurrency is an attractive approach to improve programs' execution runtime. A unique challenge of blockchains is that all replicas (miners or validators) must execute all smart contracts in the same logical order to maintain the semantics of State Machine Replication (SMR).
In this work, we study the maximal level of parallelism attainable when focusing on the conflict graph between transactions packaged in the same block. This exposes a performance vulnerability that block creators may exploit against existing blockchain concurrency solutions, which rely on a total ordering phase for maintaining consistency amongst all replicas. To facilitate the formal aspects of our study, we develop a novel generic framework for Active State Machine Replication (ASMR) that is strictly serializable. We introduce the concept of graph scheduling and the definition of the minimal latency scheduling problem, which we prove to be NP-hard. We show that the restricted version of this problem for homogeneous transactions is equivalent to the classic Graph Vertex Coloring Problem, yet show that the heterogeneous case is more complex. We discuss the practical implications of these results.

 

Presentation material:

2024-06-19 On Optimizing Deterministic Concurrent Scheduling.pdf

2.40MB

---

Introduction

 

 

 

Generic Framework

 

Graph Scheduling

Conclusion