skip to content
 

Topics in Computer Communication and Networks

15th December 2002 to 21st December 2002

Organisers: Martin Dyer (Leeds), Leslie Goldberg (Warwick), Mark Jerrum (Edinburgh), Frank Kelly (Cambridge) and Peter Winkler (Bell Labs)

Conference Theme

The Internet raises all sorts of completely new algorithmic questions, and it is these that form the focus for this workshop. An important aspect of communication on the Internet (and in other modern networks) is absence of centralised control: users communicate with each other by sending messages over the net, and use local protocols to control transmissions and to handle collisions.

One would like to study protocols, for example TCP/IP, with the aim of providing a rigorous analysis of the performance of the network. This study combines traditional probabilistic analysis (characterising the long-term behaviour of Markov chains and other stochastic processes, which are used to model protocols) with economic analysis (issues of fairness/utility) and with more traditional network algorithmics (routing methods).

Evaluating the quality of the long-term equilibrium is related to game-theory. One would like to know, for example, how close the Nash equilibrium (which arises from local control) is to the overall optimum. However, the new twist is that issues of computational tractability must be taken into account.

A further category of problems, more combinatorial in nature, arises in the modelling of the web graph and its evolution. For this purpose, standard random-graph models are unsuitable. New models are required which are consistent with empirical observations, for example that the degree-sequence of the web graph apparently obeys a power law.

University of Cambridge Research Councils UK
    Clay Mathematics Institute The Leverhulme Trust London Mathematical Society Microsoft Research NM Rothschild and Sons