Effects of Symmetry on Paradoxes in Non-Cooperative Distributed Computing

Summary Distributed computer systems consist of nodes (hosts, computers), un­der which a communication follows from connected nodes. Jobs (or transactions) arrive at each node. Jobs can be forwarded through the communication means to other nodes for remote processing. We assume that there is a decision maker at each node who strives to optimize non-cooperatively the mean response time (the cost) for a job arriving at the node, by choosing the job-processing rate at the node and job forwarding rates. This is regards in a non-cooperative game. Numerical ex­amples of a Braess-like paradox in which the performance for all decision makers in the system in a Nash equilibrium is worse with a communication means than without it, have been reported. Unlike the original Braess paradox, this behavior occurs in the models examined only in the case of finitely many users (decision makers) and not in the case of infinitesimal users, and the degree of performance degradation can increase without bound. Examples are presented which show that against our previous intuition the Braess-like paradox is strongest, i. e. the degree of performance degradation of all users in the Brass-like paradox is highest, in the completely symmetrical system wherein the parameter values describing each user are identical.