Shards That Learn to Move Accounts: Decentralized Migration with Exact Counterfactual Credit

A sharded blockchain splits its ledger across many sub-networks, called shards, so that they can process transactions in parallel. This only pays off when a transaction's sender and receiver live in the same shard. When they don't, the transaction becomes a cross-shard transaction that needs a slow multi-round commit, and much of the parallel gain disappears. Who transacts with whom keeps changing, so a placement of accounts that was good last month decays. Existing learned approaches either place each account once, using a single central agent (SPRING), or reassign nodes through a central coordinator (TBDD). We propose that each shard decide for itself, from what it can see locally, which of its accounts to hand off to another shard and when.

The learning method is centralized training with decentralized execution (CTDE): agents are trained with access to global information, and at deployment each one acts only on its own local history. The domain gives this method an unusual advantage. A blockchain's transaction stream is largely set by users, who neither see nor react to the sharding layout. Replaying a historical trace therefore lets the trainer compute exactly how many cross-shard transactions a single shard's migration decision caused or prevented, with every other shard's decisions held fixed. Methods like COMA have to learn this quantity with a critic. Here it can be computed instead of estimated. Our claim is that this exact per-shard credit is what lets fully local migration policies beat both simple local heuristics and naive multi-agent learning.

Core Claim

Dynamic account migration in a sharded ledger is a decentralized, partially observable control problem. Each shard sees only its own accounts' recent transactions, the cross-shard messages it sends and receives, and delayed load reports from other shards. The hard part is not deciding where a single account belongs. It is that many shards migrate at once without knowing what the others are doing. Two shards can swap a pair of tightly linked accounts in opposite directions so that the pair stays split, or several shards can flood the same lightly loaded shard. A shared team reward cannot tell a shard whether its own move helped or hurt. Because the workload is exogenous, the trainer can give each shard a difference signal computed exactly from the trace, and this should make decentralized policies learn coordinated, low-churn migration. The specific new element is replacing a learned centralized critic with exact counterfactual credit computed by trace replay.

Research Program

Agents. Each shard is one agent. Its policy runs replicated inside the shard, and its decisions are agreed through the shard's ordinary intra-shard consensus, the same way SPRING's agent shard agrees on its PPO outputs (SPRING).

Observation. At each epoch boundary, shard $i$ sees three things:

  • per-account counts of recent transactions to each destination shard, which it can read from relay messages;
  • its own transaction-pool size;
  • load figures gossiped by other shards, which may be stale or missing.

It never sees the global map from accounts to shards or other shards' pending migrations. A recurrent network carries this history forward, as in the recurrent policies used by QMIX and COMA.

Action. The action is a small set of migration proposals: move account $a$ to shard $j$. A receiving shard can reject a proposal if accepting it would push its projected load past a cap. This keeps state transfer bounded, which matters because the SoK on sharding identifies migration traffic as a main cost of reconfiguration.

Credit signal. Let $\mathbf{m}$ be the joint set of migrations executed in an epoch, and $\mathbf{m}^{-i}$ the same set with shard $i$'s migrations removed. Let $J(\mathbf{m})$ be the cost over the next $W$ blocks of the replayed trace, made of three parts: the number of cross-shard transactions, a penalty $\lambda$ times the variance of shard loads, and $\mu$ times the bytes of state migrated. Shard $i$ receives

$$D_i = J(\mathbf{m}^{-i}) - J(\mathbf{m}),$$

which is the cost its own decisions saved, given what everyone else did. Computing $D_i$ requires one re-evaluation of the window per shard. Because the trace is fixed, this is a counting operation, not a full emulation run. Throughput and latency are not exogenous, since they depend on queueing. For that reason $J$ uses only the countable quantities, and throughput is measured separately in the emulator.

Training and deployment. Training uses PPO with the decentralized actors and per-shard advantages built from $D_i$. A small learned value function for $D_i$ serves as a baseline to reduce variance. At deployment, the trace, the global map and the credit computation are all discarded. Each shard runs only its actor network.

Training on degraded gossip. During training we randomly drop and delay load gossip. This follows the communication-dropout training of MARO, which made policies hold up as execution-time sharing degraded. We use plain dropout, not MARO's learned imputation of missing observations. Imputation is tested only as an ablation, because a stale load number may be all a shard needs.

Baselines

Static hash placement with no migration (naive reference). Accounts are assigned to shards by address hash, the Monoxide-style scheme that SPRING compares against. It sets the floor for cross-shard ratio and throughput. SPRING reports reducing the cross-shard transaction ratio by up to 26.63% and raising throughput by up to 36.03% over this kind of hashing on historical Ethereum traces.

SPRING-style central placement. This is the strongest existing learned method, though it solves a different subproblem: initial placement only. We run it in two forms: as published with no migration, and as a central agent that also issues migrations with full global visibility. The second form is an upper bound on what full observation can buy. Our goal is not to beat it on cross-shard ratio. The goal is to come within a stated margin of it, for example recovering at least 80% of its reduction relative to hashing, without holding a global directory.

Label-propagation repartitioning (CLPA). BlockEmulator ships CLPA, a label-propagation method for repartitioning accounts, and reports that pairing it with BrokerChain or Relay improves workload balance and pool size over static assignment (BlockEmulator). No reported numeric cross-shard ratio for CLPA was found on Lacuna. We run CLPA both as shipped and as a strictly local variant, in which each shard relabels its own accounts toward their most frequent partner shard. This baseline is the most dangerous competitor, discussed below.

Graph partitioning at epoch boundaries. A min-cut partitioner, METIS-style, re-runs at each epoch boundary. SPRING reports that such partitioning takes hundreds of seconds per run. We charge it that wall-clock time and the migration volume it implies.

Fair comparison. All learned methods get the same traces, the same emulator, the same number of environment steps and the same hyperparameter-search budget. Every method pays the same per-byte migration cost.

Ablations. Three ablations isolate the key ingredient. The first uses independent PPO with the shared team reward $-J(\mathbf{m})$. The second uses independent PPO with each shard's purely local cost. The third uses a learned centralized critic in the style of COMA, conditioned on the global state, in place of exact $D_i$. Beating all three on net cost, at matched compute, is what would show that exact counterfactual credit matters.

Why not just…?

Why not just let each shard greedily move accounts toward their most frequent partner? This is local label propagation, and it is a real threat. It is decentralized, needs no training, and is roughly what CLPA does. Its known weakness is that simultaneous greedy moves can oscillate, and nothing in it weighs migration cost against benefit that may disappear when the workload shifts. That argument is ours, not a result from the file. The experiment settles it by reporting net cost, meaning cross-shard transactions plus migrated bytes, on stable and on drifting eras of the trace. If local label propagation matches us on the drifting 2019 and 2023 eras, we will report that learning is unnecessary for this problem.

Why not just keep a central learned controller, as SPRING does? SPRING's own limitations section says an agent shard holding the global map becomes a storage and communication bottleneck as the ledger grows. RingBFT reaches 1.2 million transactions per second across 15 shards precisely by avoiding a central reference committee. We still run the central controller, as an upper bound. The question is how much of its benefit decentralized policies keep, and whether that fraction holds as the number of shards grows from 4 to 64.

Why not just train independent learners? Is Independent Learning All You Need in SMAC? shows that independent learners can be surprisingly strong. COMA's own results point the other way: COMA reached about 81% mean win rate on 5m, while independent actor-critic struggled to reach 70% (COMA). That evidence comes from games, not ledgers, so the shared-reward and local-reward independent ablations decide the question here. We predict their gap to our method widens as the shard count grows, because one shard's influence on a shared reward shrinks roughly as $1/K$ for $K$ shards.

Why not just learn a centralized critic, as COMA does? A learned critic must approximate a quantity the trace already defines exactly. The learned-critic ablation measures whether exact credit is faster or better at equal compute. If the two tie, the contribution narrows to a cheaper training method, and we will say so.

Proposed Experiments

Testbed and data. We use BlockEmulator with its roughly 1.6 million Ethereum transactions from blocks 2,000,000 to 2,999,999. BlockEmulator reports 99.9% agreement with theory for throughput at 64 shards. To cover the 2015, 2019 and 2023 eras used by SPRING, we add Ethereum transfer histories, reconstructed from public chain data if SPRING's six-million-transaction set is unavailable. Smart-contract calls are excluded because BlockEmulator does not support them, which is a stated limitation. Training uses earlier windows of each era, and evaluation uses later, unseen windows.

Metrics. We measure the cross-shard transaction ratio, throughput, confirmation latency, transaction-pool size and migrated bytes, and add wall-clock decision time per epoch.

Sweeps. We vary the shard count from 4 to 64, gossip drop rates from 0 to 0.9, and migration cost $\mu$.

Decisive checks. Four results decide the outcome:

  • On net cost over the drifting eras, our method beats the local label-propagation baseline.
  • It beats all three credit ablations, with the margin growing in $K$.
  • It keeps the stated fraction of the central controller's gain relative to hashing.
  • Performance degrades gracefully as gossip is dropped. With MARO-style imputation added as an ablation, we can also tell whether stale load reports alone are enough.

Adversarial stress test. Some shards propose random or self-serving migrations. We measure how much harm the receiving shards' acceptance caps contain. This is only a first probe of the Byzantine-cooperation tension that cooperative value methods leave unaddressed. It does not offer a full solution.