# Shard Scheduler

[paper](https://arxiv.org/pdf/2107.07297.pdf)

The goal is to have a system that allows for easy migration of accounts on sharded blockchains, resulting in optimization of resources and consequently, better throughput.

Cross-shard transactions are more expensive than intra-shard transactions. Sometimes it may more economical to move an account to the target shard and then conduct an intra-shard transation, if the migration results in higher throughput and lower latency.

Shard Scheduler (SS) provides a decidedly smart way to actually facilitate such migration, but not before it can to a certain extent analyse their feasibility.

Broadly, there are two steps to the operation:
1. Deciding the "main shard" and the placement of new accounts
2. Deciding on migration of accounts with pending transactions

The main shard, once decided upon, is the only possible migration destination.
## Data structures

Each SS miner possesses a vector $v_i$ associated with an account,

$$ v_i = [a_{i1}, a_{i2}, \dots ,a_{in}]$$

where $a_{ij}$ denotes the *alignment* of account $i$ towards shard $j$. When an account is created, this is the zero vector. For a transaction $t$ from $acc_i$ in shard $z_i$ to an account $acc_j$ in shard $z_j$, the vector updates as $$a_{ij}' = a_{ij} + c(t)\\ a_{ji}' = a_{ji} + c(t)$$
where $c(t)$ denotes the cost of transaction $t$ and the prime $'$ denotes the updated value of the variable.

Alignment vectors only account for a finite number of previous transactions. Zero vectors are dropped so that alignment vectors of inactive accounts do not take up storage space. As alignment vectors are stored locally, there is no additional storage required on the chain.

There is however, some storage needed on the beacon chain that documents the load of each shard, which is the total cost of transactions processed by a shard over the last 100 blocks. This is submitted to the beacon chain by the shards along with block-headers.

## Determining the main shard

The *transaction coordinator* is the shard that includes the transaction in its block. "The transaction coordinator obtains a list of accounts to be modified and coordinates other shards involved in the transaction."

This step takes input $[l_i, \phi, s_i]$ where $l_i$ is the list of new accounts modified by the transaction, $\phi$ is the shard assignment function and $s_i$ is the last state of the shard. The list includes all internal transactions caused by this external one and is known to the transaction coordinator. Allocation recommendations and main shard assignment are made based on this information.

If multiple shards are involved, SS reads the load on each shard from the beacon chain and the minimally loaded shard is designated the main shard (see Algorithm 2 in the paper). All new accounts are assigned to the main shard.

## Deciding migration of existing accounts

The second step takes input $[ acc_i,\phi,m]$ where $acc_i$ is an account involved in a cross-shard transaction. This procedure is performed by the shard $z_i$ where $acc_i$ resides, without relying on data from other shards.

From the alignment vector of the account $acc_i$, SS evaluates if

> $a_{i, current} \times c(t_{cross-shard}) < \underset{k \neq current}\sum a_{ik}$

If true, the account is migrated to the main shard.

## Incentives
Proposals by rational miners in a sharded environment tend to include transactions that have the highest fees. Hence, they are greatly incentivized to migrate accounts to their own shard, in order to have more transactions to choose from, thus working against the interests of the network.

To tackle this, the writers propose a shard-special deposit, which is collected in the next epoch, after miners have been assigned to different shards. Upon assignment, the miner collects the same percentage of transaction fees accrued by the previous miners. For example, if 10% of the fees of the last transaction in the last shard were allotted to miner $m_1$, then $m_1$ will collect 10% of the fees accrued in the current shard.

Such a system results in an increased expected reward for miners which is directly proportional to the total fees collected in the network during the previous epoch, thus incentivizing increasing the network's total capacity.