  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 (minors or validators) must execute all smart contracts in the
same logical order to maintain the semantics of State Machine Replication
(SMR). While non-conflicting transactions can be executed in any actual order,
replicas need to enforce a unique logical order among all pairs of conflicting
transactions.
  In this work, we formally study the maximal level of parallelism obtainable
when focusing on the conflict graphs between transactions packaged in the same
block, rather than relying on the total ordering order. To that end, we
describe a generic framework for Active State Machine Replication (ASMR) that
is strictly serializable. The generic framework allows for shifting our focus
to developing efficient execution engines for transactions without introducing
non-deterministic results.
  Then, we suggest the concept of graph scheduling, and the minimal latency
scheduling problem, which we prove to be NP-Hard. We show that the restricted
version of the problem for homogeneous transactions is equivalent to the
classic Graph Vertex Coloring Problem, yet the heterogenous case is more
complex. We discuss practical implications of these results.
