Challenges

A1. Create a blockchain network with an interface supporting transaction timing constraints and flexible block generation for accommodating more transactions within a single block time.

• There is no interface to express and utilize the deadline of each transaction.
  (gas is not an answer.) - Make nodes can send each transaction to put as input the expected deadline of the transaction
• Increasing the rate of generating blocks itself cannot guarantee timely execution and incurs space inefficiency. (idle blocks can be accumulated.)
  • Extend the target network to provide the flexibility of making zero to multiple blocks at a single block time.

A2. Develop novel scheduling principles specialized for the blockchain network so as to guarantee the timely execution of periodic/sporadic transactions without wasting the blockchain network resources.

• The timeline of the transaction request of a transaction-generating node is different from that of a block-generating node.
  • Translate a periodic/sporadic request of a transaction-generating node, into a periodic/sporadic arrival on a block-generating node.
  • Derive a condition of the modeled transaction load.
• Each transaction cannot be split to be included in more than one block.
  • Develop a lazy deadline-based scheduling policy and its condition

Contributions

• We raise and address two issues to achieve timing guarantees for blockchain transactions, which is the first attempt.
• We modify the existing blockchain network enabling deadline-based transaction selection and extend it to provide the flexibility of the number of generated blocks at a single block time.
• We develop novel scheduling principles that can guarantee the timely execution of periodic/sporadic transactions, which is the first achievement.
• We develop advanced scheduling methodologies that reduce the number of generated blocks without compromising timing guarantees of transactions.
• We implement the proposed network architecture and scheduling principles in a real blockchain, and evaluate their performance.

RT-Blockchain

• A single block is generated and connected to the main blockchain
  at regular intervals (slots)
• Each of whose duration is same and called block time ($BT$)
• All transactions entering the system are stored in the transaction pool, and they are ordered based on their respective deadlines, with the earliest deadline transactions given priority.

RT-Blockchain: Node's POV

Block Generation Time

• Select node to create the block.
• The selected block-generating node stops accepting additional
  transactions into its pool.
• Starts selecting transactions to be included and then including them in the block.
• Also calculates block hash for ensuring the integrity and sequential order of the blocks in the blockchain.

Block Validation Time

• Validators independently validate the transactions and verify the
  block hash.
• This process, starting from when the block is distributed to when
  it is added to the main chain, is defined as block validation time.

RT-Blockchain: User's POV

Block Generation Time

• The duration from the sender to the pool, representing the transaction's time within the network, is referred to as traffic time ($\le tft$)
• $t^s(SL_j)$ denote the time instant at which $SL_j$ starts.
• transaction schedule time: A block is filled with scheduled transactions ($\le tst$)
• Hash calculation time ($\le hct$)
• Block generation time $\le C^{gen} = tst + hct$

Block Validation Time

• The generated block is distributed throughout the network and reaches the local machines of each validator ($\le tft$)
• The validating nodes run hash calculations on the given block to
  check the validity($\le hct$)
• $C^{val} = tft + hct$
• User’s transaction request can finish its execution no later than $t^s(SL_j)+C^{gen}+C^{val}$

Timely Transactions on RT-Blockchain

Definition 1.
A periodic/sporadic user-level blockchain transaction task $\eta_i \in \eta$ > $\left(T_i,D_i,S_i\right)$, $T_i$: the inter-arrival time, $D_i$: the relative deadline, $S_i$: the maximum transaction size.

A user-level blockchain transaction task $\eta_i\left(T_i,D_i,S_i\right)$ generates a series of transaction jobs, the $x^{th}$ of which is denoted by $\eta_{i,x}$.

The release times of $\eta_{i}$’s two consecutive jobs $\eta_{i,x}$ and $\eta_{i,x+1}$ are separated by at least $T_i$

Once a job $\eta_{i,x}$ is released at $t$, its transaction whose size is at most $S_i$ should be completed no later than $t + D_i$

Definition 2.
A periodic/sporadic user-level blockchain transaction task set $\eta$ is said to be schedulable, if there is no single job deadline miss for every legal job series generated by $\eta$.

Now we can state our goal as follows.

Problem Statement:
We develop a deadline-based scheduling algorithm and a schedulability condition for $η$, which is scheduled by the scheduling algorithm on a RT-blockchain system, such that

G1. $η$ is schedulable if $η$ satisfies the schedulability condition (achieving timing guarantees).

Achieving G1 in the problem statement is totally different from the case for the traditional real-time periodic/sporadic task set $τ$ executed on a computing platform due to the following challenges:

1. The timeline of each user’s transaction request is different from that of block generation.
2. Each transaction cannot be split to be included in more than one block, which may yield an arbitrarily small utilization of each block under priority-based approaches.

To address C1 first, we need to interpret the release time and the absolute deadline of each user’s transaction job, from the block-generating node’s point of view.

User-level to Slot-level Translation

Definition 3.
A periodic/sporadic slot-level blockchain transaction task $\eta_i^S \in \eta^S$

$\eta_i^S\left(T_i^S,D_i^S,S_i^S,N_i^S\right)$

• $T_i^S$: the inter-arrival slots
• $D_i^S$: the slot-unit relative deadline
• $S_i^S$: the maximum transaction size
• $N_i^S$: the number of transactions of each job of $\eta_i^S$

The ready-to-be-scheduled time instant for $\eta_{i,x}^S$ is $t^s(SL_j)$.
Once a job $η^S_{i,x}$ is ready-to-be-scheduled at $t^s(SL_j)$, there are $N^S_i$ transactions whose size is at most $S^S_i$.

Each of them should be included in any block of $SL_j$ , $SL_{j+1}$, $...$, or $SL_{j+D^S_{i}−1}$,

Definition 4.
A periodic/sporadic slot-level blockchain transaction task set $η^S$ is said to 1be schedulable, if there is no single job deadline miss for every legal job series generated by $η^S$.

We can translate $η$ to $η^S$, without compromising timing constraints of every $η_i ∈ η$.

We should consider two cases:

1. $(T_i − tft) \ge BT$
2. $(T_i − tft) < BT$

Theorem 1
The schedulability of a periodic/sporadic user-level blockchain transaction task set $η$ is schedulable on a RT-blockchain system, if its corresponding periodic/sporadic slot-level blockchain transaction task set $η^S$ is schedulable, where parameters of each $η^S_i ∈ \eta^S$ is set as follows.

$\begin{aligned} D_i^S &= \left\lfloor \frac{D_i - tft - C^{gen} - C^{val}}{BT} \right\rfloor, &(1)\\ S_i^S &= S_i,&(2)\\ \text{If } T_i - tft \ge BT, \quad T_i^S &= \left\lfloor \frac{T_i - tft}{BT} \right\rfloor, \text{ and } N_i^S = 1,&(3)\\ \text{If } T_i - tft < BT, \quad T_i^S &= 1, \text{ and } N_i^S = \left\lceil \frac{BT + tft}{T_i} \right\rceil.&(4)\\ \end{aligned}$

Proof for $D_i^S$
The worst case is a job of $\eta_i$ in block-generating node right after $t^S(SL_j)$.
If its absolute deadline is no earlier than $t^s(SL_{j+1}) + C^{gen} + C^{val}$, it does not miss the deadline.
It's equivalent to $D_i - BT - tft - C^{gen} - C^{val} \ge 0$.
Therefore, $D^S_i$ is not smaller than $\left\lfloor\frac {D_i - BT - tft - C^{gen} - C^{val}}{BT}\right\rfloor + 1$. which is equivalant to Eq. $(1)$.

Timing Guarantees for RT-Blockchain

Now we can translate the G1 to G1$^S$

Problem Statement:
We develop a deadline-based scheduling algorithm and a schedulability condition for $η^S$, which is scheduled by the scheduling algorithm on a RT-blockchain system, such that

G1$^S$. $η^S$ is schedulable if $η^S$ satisfies the schedulability condition (achieving timing guarantees).

Apply $EDF^{WC}$ (Work-Conserving Earliest Deadline First) for a RT-blockchain system as follows:

Algorithm of $EDF^{WC}$ for $\eta^S$ with a single block

1. At every beginning of each slot, sort all transactions in the waiting queue by their absolute slot-unit deadlines.
2. Then, assign each sorted transaction to the block one by one, until the highest-priority unassigned transaction in the waiting queue cannot be assigned due to the remaining portion of the block is smaller than the size of the highest-priority unassigned transaction.

Definition 5.
Let $DBF(\eta_i^S,q)$ denote the demand bound function for a slot-level blockchain transition task $\eta_i^S \in \eta^S$ during $q$ consecutive slots (where $q=1,2,\dots,3$), defined by

$DBF(\eta_i^S,q) = \max\left(0,\left(\left\lfloor\frac{q-D^S_i}{T^S_i}\right\rfloor+1\right)\cdot\frac{S^S_i\cdot N^S_i}{BS}\right) \tag{5}$

Definition 6.
Let $LOAD(η^S)$ denote the maximum of the sum of all $DBF(η^S_i , q)$ for $η^S_i ∈ η_i$ divided by the number of consecutive slots $q$, which is defined by

$LOAD(\eta^S) = \max_{q=1,2,3,\dots}\frac{\sum_{\eta^S_i\in\eta^S}DBF(\eta^S_i, q)}{q} \tag{6}$

One may think that $LOAD(\eta^S) \le 1.0$ could be schedulability condition for $\eta^S$.

However, this is wrong due to C2: Each transaction cannot be split to be included in more than one block.

Theorem 2
A set of periodic/sporadic slot-level blockchain transaction tasks $η^S$ is schedulable by $EDF^{WC}$ on a RT-blockchain system, if the following condition holds.

$LOAD(\eta^S) \le 1.0 - \max_{\eta_i \in \eta^S}\frac{S^S_i}{BS} \tag{7}$

Proof

• First, we prove the statement: if the sum of the size of transactions in the waiting queue is larger than $BS\cdot\left(1.0 - \max_{\eta_i \in \eta^S}\frac{S^S_i}{BS}\right)$, the block can include a set of transaction whose size summation is at least $BS\cdot\left(1.0 - \max_{\eta_i \in \eta^S}\frac{S^S_i}{BS}\right)$.

• Suppose that the statement is wrong, then there exists a job that cannot be included in the block.

• But the block has at least $BS\cdot\max_{\eta_i \in \eta^S}\frac{S^S_i}{BS}$ amount remaining space.

• This violates the Work-conserving

• Second, suppose that there exists a deadline miss of transaction of $\eta_{i,x}$ at the $n^{th}$ slot.
• Let $n_0$($\le n$) is the largest index of the slot, such that
  1. $BS\cdot\left(1.0 - \max_{\eta_i \in \eta^S}\frac{S^S_i}{BS}\right)$ is strictly larger than the sum of the size of transactions whose slot-unit absolute deadline is no later than that of the transaction $\eta_{i,x}$ in the block of $(n_0-1)^{th}$ slot.
  2. $BS\cdot\left(1.0 - \max_{\eta_i \in \eta^S}\frac{S^S_i}{BS}\right)$ is no larger than that in the block of $n_0^{th}$ slot.

The first property implies that there is no job whose release slot index is $n_0 - 1$ or smaller, but is not included in any block until the beginning of the $n_0^{th}$ slot.

Therefore, $BS \cdot \sum_{\eta_i \in \eta^S} DBF(\eta_i, n - n_0 + 1)$ is the largest possible sum of the size of transactions whose slot-unit absolute deadline is no later than that of $\eta_{i,x}$.
Also, by definition, $(n - n_0 + 1) \cdot BS \cdot (1.0 - \max_{\eta_i \in \eta^S} \frac{S_i^S}{BS})$ is a lower bound of the sum of the size of transactions whose slot-unit absolute deadline is no later than that of $\eta_{i,x}$.

This contradicts Eq. $(7)$.

Design of Multi-Block RT-Blockchain

We design an architecture that generates multiple blocks per block time to enhance the scalability of the blockchain system while preventing the generation of empty blocks.
: multi-block RT-blockchain

Unlike traditional blockchain systems, our architecture allows the block-generating node to determine the number of blocks to generate during each block time based on the transactions in the pool.

• $m$: a predefined threshold of the maximum number of generating blocks in each slot.

---

Design of Multi-Block RT-Blockchain

1. The node generating the block first calculates how many blocks will be needed to fit the transaction in the pool
2. the node stores transactions sequentially in each block while keeping the bound

We assume that $tst' \le m\cdot tst$, implying block generation time for a $m$-block RT-blockchain is upper-bounded by $tst' + m\cdot hst \le m\cdot(tst + hct) = m\cdot C^{gen}$.

Also, block validation time is upper-bounded by $m\cdot C^{val} = m\cdot (tft+hct)$.

Therefore, any transaction included in one of the m blocks at the jth slot is finished no later than $t_s(SLj) + m \cdot C_{gen} + m \cdot C_{val}$

Timing Guarantees for Multi-Block RT-Blockchain

Theorem 3
The schedulability of a periodic/sporadic user-level block-chain transaction task set $η^S$ is schedulable on a $m$-block blockchain system,
If its corresponding periodic/sporadic slot-level block-chain transaction task set $η^S$ is schedulable, where $D^S_i$ of each $η^S_i$ is set to Eq. $(8)$ and other parameters are set to Eqs. $(2)$, $(3)$ and $(4)$ in Theorem 1.

$D^S_i = \left\lfloor \frac{{D_i - tft} - m \cdot C^{gen} - m \cdot C^{val}}{BT} \right\rfloor \tag{8}$

When it comes to the scheduling algorithm, we also apply $EDF^{WC}$, generalized for $m$ blocks (instead of a single block) to be supplied.

Algorithm of $EDF^{WC}$ for $\eta^S$ with $m$ blocks

1. At every beginning of each slot (i.e., $t^S(SL_j)$), sort all transactions in the waiting queue by their absolute slot-unit deadlines.
2. Then, assign each sorted transaction to one of the $m$ blocks one by one using the first-fit policy, until the highest-priority unassigned transaction in the waiting queue cannot be assigned to any of the m blocks

Theorem 4
A set of periodic/sporadic slot-level blockchain transaction tasks $η^S$ is schedulable by $EDF^{WC}$ on a $m$-block blockchain system, if the following condition holds

$LOAD(\eta^S) \leq LOAD^*(\eta^S) \tag{9}$

$\text{where} \quad LOAD^*(\eta^S)= m \cdot \left(1.0 - \max_{\eta_i \in \eta^S} \frac{S_i^S}{BS}\right)\tag{10}$

But if $(1.0 - \max_{\eta_i \in \eta^S} \frac{S_i^S}{BS})$ is small, Theorem 4 is pessimistic.

We can improve this as follows.

Theorem 5
A set of periodic/sporadic slot-level blockchain transaction tasks $η^S$ is schedulable by $EDF^{WC}$ on a $m$-block blockchain system, if the following condition holds

$LOAD(\eta^S) \leq LOAD^{**}(\eta^S) \tag{11}$

$\begin{aligned} \text{where} \quad LOAD^{**}(\eta^S)= &\max\left(\frac 1 2, 1.0 - \max_{\eta_i \in \eta^S} \frac{S_i^S}{BS}\right)\cdot(m-1) \\ \tag{12} &+\left(1.0 - \max_{\eta_i \in \eta^S} \frac{S_i^S}{BS}\right) \end{aligned}$

Proof
We only need to prove the case for $\left(1.0 - \max_{\eta_i \in \eta^S} \frac{S_i^S}{BS}\right) < 0.5$.
If the sum of the size of transactions in the waiting queue is larger than $BS · LOAD^{∗∗}(η^S)$, the block can include a set of transactions whose size summation is at least $BS · LOAD^{∗∗}(η^S)$ without violating the priority of transactions

Suppose that there are at least two blocks, each of which is occupied no larger than 50%,
Then, it immediately contradicts the first-fit policy in $EDF^{WC}$.
Therefore, there is at most one block that is occupied no larger than 50%.

Since no schedular can make $\eta^S$ schedulable if $LOAD(\eta^S) > m$, the resource augmentation bound(?) is

which converges to 2.

Resource Efficiency with Timing Guarantees.

G2$^S$. The number of generated blocks is minimized.

We develop a lazy algorithm called $EDF^{Lazy}(r)$ as follows, where $r$ is a positive rational number less than $m$.

Algorithm of $EDF^{Lazy}(r)$ for $\eta^S$ with $m$ blocks

1. At every beginning of each slot (i.e., $t^S(SL_j)$), sort all transactions in the waiting queue by their absolute slot-unit deadlines.
2. Then, assign each sorted transaction to one of the $m$ blocks one by one using the first-fit policy, until the sum of $\frac {S^S_i} {BS}$ for all assigned transactions is no smaller than $r$.
3. Let $m'$ denote the number of blocks occupied by at least one transaction so far.
4. We apply $EDF^{WC}$ for the remaining unassigned transactions as if we have only the $m'$ blocks instead of $m$

Theorem 6.
A set of periodic/sporadic slot-level blockchain transaction tasks $η^S$ is schedulable by $EDF^{Lazy}(LOAD(η^S))$ on a $m$-block blockchain system, if Eq. (1$3)$ holds.

$LOAD(\eta^S) \leq LOAD^{**}(\eta^S) \tag{13}$

Proof
If the sum of the size of transactions in the waiting queue is larger than $BS · LOAD(η^S)$, the block can include a set of transactions whose size summation is at least $BS · LOAD(η^S)$ without violating the priority of transactions.

The operation of $EDF^{Lazy}(LOAD(η^S))$ is exactly the same as that of $EDF^{WC}$ until the $m$ or smaller blocks include a set of earliest-deadline transactions whose size summation is barely no smaller than $BS · LOAD(η^S)$, the remaining proof is similar to that of Theorem 5.

---

Implementation

• Turtlecoin, a commercially available and highly extensible blockchain platform.
• PoS (Proof of Stake) Consensus Mechanism
• BT = 12s, BS = 100KB
• 66% of validators should include the block in their main chain.