Random Graphs and Large Networks

Dimitris Achlioptas, UC Santa Cruz & RACTI Abstract: The best-known model of random graphs was introduced 50 years ago, by Erdos and Renyi (ER): take n vertices and connect each pair of them, independently, with probability p(n). By now, and thousands of research papers later, we know that ER random graphs have a number of amazing properties, many of which we understand very well. A bit more slowly we have also come to understand that ER random graphs can be poor models of "network realities": it is impossible to place the vertices of a (typical) ER random graph in a low-dimensional space, so that for each pair of vertices, their geometric distance is a good approximation of their graphical (shortest-path) distance. In other words, ER random graphs are inherently high-dimensional objects, in contrast to many real networks. In this tutorial talk we will survey some of the fundamental results for ER random graphs and use them as springboards to introduce (and compare with) alternative random graph models.

Scheduling in server farms: approaches and open problems

Mor Harchol-Balter, Carnegie Mellon University Abstract: Server farms are ubiquitous in applications ranging from Web server farms to high-performance supercomputing systems to call centers. The popularity of the server farm architecture is understandable, as it allows for increased performance, while being cost-effective and easily scalable, allowing applications to meet response time goals and power goals. Given the prevalence of server farms, it is surprising that even at this late date so little is understood with respect to designing policies for resource management in multi-server systems. In this talk we address the following design questions: What are good policies for routing/dispatching jobs to hosts in a server farm? How should jobs be scheduled at the individual hosts? How can we choose policies to combat job size variability? What are the tradeoffs between response time and fairness goals? How can policies simultaneously meet response time goals and energy goals for a server farm? There are at least three distinct communities studying scheduling in server farms from an analytical perspective. These include the SIGMETRICS community, the INFORMS community, and the SPAA/STOC/FOCS community, all of which have different approaches and goals. One of our goals in this tutorial is to make researchers aware of results in these different communities. The emphasis will be on intuition, so that the talk is accessible to newcomers as well as old-timers. In surveying the newest results, we will also present some practical open problems.

Fundamentals of Continuum Percolation

Mathew Penrose, University of Bath Abstract: We consider graphs created on a randomly scattered set of vertices in Euclidean d-space, by placing an edge between any two vertices at most unit distance apart. When the underlying set of vertices is an infinite homogeneous Poisson process, this graph is called the Gilbert graph; when it is a finite set of points in a cube, it is called the random geometric graph. We discuss basic notions notions for the Gilbert graph such as cluster size distribution, and phase transition for infinite components. We also relate these notions to asymptotic properties of the random geometric graph.

Multisource Network Coding

Raymond W. Yeung, Chinese University of Hong Kong Abstract: The capacity of network coding for a single source has the nice and sweet max-flow min-cut characterization. Once we move beyond single-source, the problem becomes much more difficult. The capacity region for multisource network coding on acyclic networks was completely characterized by Yan, Yeung, and Zhang (2007) in terms of $\Gamma^*$, the region of all entropy functions. This characterization is strongly tied to the study of non-Shannon-type inequalities. In this tutorial, we will first explain this characterization on an intuitive basis. This characterization, however, works only for block network codes with arbitrarily small probability of decoding error but does not work with variable-rate network codes that can possibly achieve zero error. In the rest of the tutorial, we will explain the hurdles involved and report some of our latest efforts toward overcoming these hurdles.