Entanglement improves coordination in distributed systems

Coordination in distributed systems is often hampered by communication latency, which degrades performance. Quantum entanglement enables correlations stronger than classically possible without communication. Such correlations manifest instantaneously upon measurement, irrespective of the physical distance separating the systems. We investigate the application of shared entanglement to a dual-objective optimization problem in a distributed system comprising two servers. The servers process both a continuously available, preemptible baseline task and incoming paired customer requests, to maximize the baseline task throughput subject to a Quality of Service (QoS) constraint on average customer waiting time. We present a rigorous analytical model demonstrating that an entanglement-assisted routing strategy allows the system to achieve higher baseline throughput compared to communication-free classical strategies, provided the baseline task's output exhibits sufficiently increasing returns with processing time. This advantage stems from entanglement enabling better coordination, which allows the system to satisfy the customer QoS constraint with a lower overall probability of splitting customer requests, leading to more favorable conditions for baseline task processing and thus higher throughput. We further show that the magnitude of this throughput gain is particularly pronounced for tasks exhibiting increasing returns, where output grows super-linearly with processing time. Our results identify optimization of scheduling in distributed systems as a novel application domain for near-term quantum networks.