Algorithmic issues for resource management in Internet-centric computing.

摘要

One of the unique abilities of the Internet is that it has enabled the creation of virtual communities of users who can share information and resources. In the last few years, a number of important applications have been built around this functionality. For instance, electronic markets have enabled communities of buyers and sellers to trade without barriers of distance; and peer-to-peer networks have created communities of file-sharing users. These nascent applications point to the Internet's potential as a large-scale, distributed resource-sharing platform. The scale and the decentralized nature of this platform, however, pose significant and novel research challenges for designing algorithms for the allocation and discovery of resources.; In this thesis, we study four algorithmic problems that arise in connection with exchanging and sharing resources in Internet-centric applications. The first problem deals with the computational complexity of multi-unit auctions; the second problem deals with joint allocation of computing cycles and bandwidth in resource sharing systems like Grid computing and Utility computing; the third problem deals with indexing of spatial data for range queries in P2P systems; finally, the last problem addresses the anarchic aspect of the Internet: the users may be selfish and act to maximize their own private benefit, rather than act selflessly towards the common good of the system.