COMPETITIVE DISTRIBUTED DECISION-MAKING

We study several natural problems in distributed decision-making from the standpoint of competitive analysis; in these problems incomplete i nformation is a result of the distributed nature of the problem, as op posed to the on-line mode of decision making that was heretofore preva lent in this area In several simple situations of distributed scheduli ng, the competitive ratio can be computed exactly, and the different r atios can be used as a measure of the value of information and communi cation between decision-makers. In a more general distributed scheduli ng situation, we give tight upper and lower bounds on the competitive ratio achievable in the deterministic case, and give an optimal random ized algorithm with a much better competitive ratio.