The cost of collaboration

K. Gardner and R. Righter, “The Cost of collaboration,” Queueing Systems, vol. 100, pp. 7-40, 2022, https://doi.org/10.1007/s11134-021-09721-y .

Abstract Multi-class multi-server systems, in which each job class can be served by a subset of servers, are common in a wide variety of applications. In such systems, a key question is whether to collaborate, allowing a job to be in service on multiple servers simultaneously, or not to collaborate. For systems with redundancy and exponential service times, this question is equivalent to the question of whether to cancel copies of a job once a copy starts service or once a copy completes service. While the collaborative and noncollaborative systems have been well studied in steady state, existing results have not allowed for a comprehensive comparison of performance in the two systems. In this paper, we use a combination of steady-state analysis and sample-path arguments to study the costs and benefits of collaboration. While intuition says that collaboration should yield substantial benefits when service times are not correlated, we find that, surprisingly, this is not the case. In systems that exhibit symmetry among servers or job classes, we can construct coupled sample paths so that collaboration indeed always outperforms noncollaboration. However, in all systems the benefit of collaboration is limited: we show that on sample paths with the same arrival and service processes, there is an upper bound on this benefit, in terms of the number of jobs in system. On the other hand, collaboration can be arbitrarily worse than noncollaboration on sample paths with the same input processes. Ultimately, both in steady state and sample-path wise, the two systems typically achieve similar response times, indicating that collaboration is never a big win and that, in many real-world systems, noncollaboration may be the better choice.