Competitive distributed decision-making |
| |
Authors: | Xiaotie Deng C. H. Papadimitriou |
| |
Affiliation: | (1) Department of Computer Science, York University, M3J 1P3 North York, Ontario, Canada;(2) Department of Computer Science, University of California at San Diego, 92093 La Jolla, CA, USA |
| |
Abstract: | We study several natural problems in distributed decision-making from the standpoint of competitive analysis; in these problems incomplete information is a result of the distributed nature of the problem, as opposed to the on-line mode of decision making that was heretofore prevalent in this area. In several simple situations of distributed scheduling, the competitive ratio can be computed exactly, and the different ratios can be used as a measure of the value of information and communication between decision-makers. In a more general distributed scheduling situation, we give tight upper and lower bounds on the competitive ratio achievable in the deterministic case, and give an optimal randomized algorithm with a much better competitive ratio.The research of Xiaotie Deng was supported by an NSERC grant and that of C. H. Papadimitriou was supported by an NSF grant. |
| |
Keywords: | On-line algorithms Distributed computing Load balancing Distributed scheduling |
本文献已被 SpringerLink 等数据库收录! |
|