SpectralShard: Lightweight Partitioning Under Dynamic Interaction Patterns

Distributed computing continuum systems (DCCS) commonly partition application state to enable parallel execution and scale. To avoid costly cross-partition coordination, objects that interact frequently should be assigned to the same partition. Maintaining such efficient partitions under dynamic workloads while keeping updates cheap, however, remains a key challenge. We present SpectralShard, a lightweight partitioning technique based on the spectral structure of the interaction graph. SpectralShard assigns each object a scalar value, derived from a loworder spectral representation of the graph, such that frequently interacting objects receive similar values, and groups objects with nearby values. Because these values can be maintained incrementally as the graph evolves, SpectralShard adapts to workload changes with low overhead, avoiding costly criticalpath computations required by optimization-based approaches. We evaluate SpectralShard on large-scale Ethereum transaction traces as a representative dynamic workload for distributed execution. SpectralShard reduces cross-partition interactions by up to 49.9%, improves throughput by up to 83.5%, and lowers end-to-end latency by up to 38.4% compared to hash-based sharding. These improvements match or exceed those of greedy locality-aware partitioning, while incurring negligible computation on the critical path, comparable to hash-based sharding. Overall, this suggests that low-order spectral methods are a promising building block for adaptive partitioning in DCCS.