https://hal.inria.fr/hal-00788771Anselmi, JonathaJonathaAnselmiBCAM - Basque Center for Applied Mathematics - Basque Center for Applied MathematicsGaujal, BrunoBrunoGaujalMESCAL - Middleware efficiently scalable - Inria Grenoble - Rhône-Alpes - Inria - Institut National de Recherche en Informatique et en Automatique - LIG - Laboratoire d'Informatique de Grenoble - UPMF - Université Pierre Mendès France - Grenoble 2 - UJF - Université Joseph Fourier - Grenoble 1 - Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology - INPG - Institut National Polytechnique de Grenoble - CNRS - Centre National de la Recherche ScientifiqueThe Price of Forgetting in Parallel and Non-Observable QueuesHAL CCSD2011[INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation[INFO.INFO-PF] Computer Science [cs]/Performance [cs.PF][INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT][INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]Legrand, Arnaud2013-02-15 11:10:352023-03-15 08:53:372013-02-15 11:10:48enJournal articles10.1016/j.peva.2011.07.0231We consider a broker-based network of non-observable parallel queues and analyze the minimum expected response time and the optimal routing policy when the broker has the memory of its previous routing decisions. We provide lower bounds on the minimum response time by means of convex programming that are tight, as follows by a numerical comparison with a proposed routing scheme. The "Price of Forgetting" (PoF), the ratio between the minimum response times achieved by a probabilistic broker and a broker with memory, is shown to be unbounded or arbitrarily close to one depending on the coefficient of variation of the service time distributions. In the case of exponential service times, the PoF is bounded from above by two, which is tight in heavy-traffic, and independent of the network size and heterogeneity. These properties yield a simple engineering product-form approximating tightly the minimum response time. Finally, we put our results in the context of game theory revisiting the "Price of Anarchy" (PoA) of parallel queues: it can be decomposed into the product of the PoA achieved by a probabilistic broker (already well understood) and the PoF.