By allowing arbitrary collections of users to share various computational resources, the internet has enabled a wide range of interesting new applications. Unfortunately, current internet protocols are not well-designed for supporting certain applications (e.g., Web TV). Thus it is desirable to design scalable resource sharing protocols that support as wide a range of applications as possible given the available hardware.

In order to guide the design of newer and more efficient resource sharing protocols, it is useful to study the theoretical complexity of such protocols with respect to first-order abstract models of the internet. In this mini-course we will study a number of recent research results in this direction. Apart from a brief overview lecture on the first evening, and a summary lecture on the last day, the course material is divided into five modules (one per day, Monday to Friday) as outlined below.

In the first module we introduce the concepts of on-line computation and competitive analysis, and consider problems related to the design of efficient caching protocols in wide-area networks.

In the second module we introduce the metric space model of internet computation, and review a number of important theoretical results concerning metric spaces, including the probabilistic approximation of metric spaces and its algorithmic applications.

In the third module we present various popular interconnection schemes for parallel computers, and demonstrate that dynamic versions of these schemes provide a plausible foundation for coordinating a dynamic collection of machines in the internet.

In the fourth module we discuss algorithms for clustering large data sets. We present recent algorithms for clustering metric data sets and for clustering the (non-metric) Web graph.

In the fifth module we introduce basic notions from the field of mechanism design, and apply these notions to develop cost sharing protocols that behave well even in the presence of "selfish" participants, that is, participants who wish to maximize their own benefit rather than the common good.

Note: If you wish, you can look at the references appearing on the online lecture schedule for Greg Plaxton's Fall internet algorithms course at UT Austin, which is linked from his web page http://www.cs.utexas.edu/users/plaxton/c/395t/index.html. In particular, he expects to touch on some of the material covered in the following lectures of the course (in addition to a bit of other more recent material): Sep 4, Sep 9, Sep 18 through Oct 9, Oct 21, Oct 23, Nov 13 through Nov 25.