[1] Some writers reserve the term "client" for cases in which users have exclusive rights to their assigned client machine, and they use the term "cooperative" or "distributed" computing otherwise [e.g. Francis (1990)]. However, we have no need to make such a distinction, and will hence use the term client for all user-interface processors.

[2] It is straightforward to modify our results for interruptable priority service, or a mixture of interruptable and non-interruptable priority services. We chose the non-interruptable case because it is quite common, and because we wanted to keep the notation at a minimum.

[3]While most machines may be deterministic, given idiosyncratic differences (such as different data), it may be more realistic to view the load as a random number, albeit with a known mean and small variance. Also some machines may route a job to successor machines based on the current queue of those machines, so the "path" through the system may be probabilistic. In the event that a user mistakenly attempted to start a program p at a machine incompatible with the program instructions, the machine would issue an unable-to-read message and terminate - thus imposing a negligible load on the NCS.

[4] This may appear to be a formidable task, especially in view of the "halting problem." However, we envision that almost all users will employ standardized commerical software in which case rule-of-thumb load estimation techniques could be developed and widely available. Moreover, the client software could update the rules-of-thumb based on accumulated experience. In the case of new user-specific programs, load estimation could be added to the compiler task in a new generation of compilers.

[5]What matters are the beliefs of the clients about the waiting times. We assume that the NCS provides reliable information to the user's client about w, which form the basis for common beliefs. We further assume that beliefs about w change at a much slower rate than programs move through the NCS, so a constant w for a given originating program p is justified.

[6] We have implicitly that the user selects one priority class for each distinct program. Different priorities at different machines could be modeled by specifying the priority choice as a vector , and replacing with . We opted for the constant priority class approach because it is notationally simpler and would be easier to implement.

[7] While this appears to be an infinite dimensional problem, under mild conditions it reduces to a finite dimensional problem. To see this, observe that by continuous differentiability of , the instantaneous marginal value of any output is bounded, while the completion time and/or cost of p is unbounded, so infinitely long programs will never be optimal. Hence, there will be a finite limit, L, for the length of programs such that if the length of p exceeds L, then p is never considered. Under these circumstances, P can be replaced by the finite set of programs of length L or less. Finally, for practical purposes, any single user-client is likely to be knowledgeable about a small subset of , so the cost minimization problem will finite and manageable.

[8] There will be a unique cost-minimize program and priority class for almost every (r,w), but for some (r,w) there may be several cost-minimizing programs. By standard arguments [see, for example, Debreu, 1959], is convex-valued and upper-hemi-continuous. Further, given (r,w), there will be a unique cost-minimizing program and priority class for almost every value of .

[9] In this expression, and others that follow, given user i and service s, the summation should be understood to range only over .

[10] Multiplicities in can arise only in the rare instances when there are multiple cost-minimizing programs and priority classes given (r,w).

[11] Since depends only on and is strictly concave, a standard argument from mathematical economics establishes that exists and is finite, single-valued and continuous for all non-negative (r,w).

[12] A similar process was studied by Sanders (1988a) and shown to be stable.

[13] CISM is a process based simulation programming environment developed by H. Schwetman, an expert in computer performance evaluation at Microelectronics and Computer Technology Corporation (MCC) at Austin, Texas. It provides functions in C/C++, which can be used to control the simulation flow and gather the statistics at each machine. CSIM also has the capability of simulating parallel processing.

¹⁶ An aggregate exogenous Poisson arrival rate represents the arrival rate of jobs regardless of their desired service type. A service type is identified only after the job arrives, according to the probability distribution specified in Table 3.

[14] In the case with no pricing, net benefits = private benefits.

[15] For example, the delay cost could be reported when a service request is submitted, and the priority could be determined by the NCS. For the single server case, it is well known that the optimal priority assignment would follow the rule. Dolan (1978) and Mendelson and Whang (1990) take this approach. However, in a network setting, the optimal machine-by-machine priority assignment rule is an open question.

[16] While is single-valued. With a continuum of agents, multi-valued demands have no consequence for the stochastic equilibrium or the welfare maximum. With a finite number of agents, this "decentralization" problem can be overcome with an -optimal approach [Stahl, 1986].