Multiple network resources are commonly assigned similar of identical tasks in large-scale networked systems. The replication of tasks may be desirable and explicitly performed, such as the copying of the same content to multiple network points to increase its availability and reduce expected retrieval latency. In other instances, the replication may occur out of necessity, such as when numerous independent 802.11 wireless gateways are assigned the same transmission channel because the number of gateways exceeds the number of available channels.

In many cases, the performance of the network depends on the mapping that is used to assign these replicated tasks to nodes. The first part of the talk explores how to perform this mapping in massively distributed environments. We abstract the task assignment problem in a network to a non-traditional graph coloring problem. In the context of this model, we present a novel, elegant, distributed algorithm that assigns tasks to nodes in a manner that is amenable to a large body of network tasking scenarios.

In the second part of the talk, we consider a specific task replication scenario, where competing content providers replicate one anothers' content and pool together their serving resources into collectives, enabling them to serve requests for one another's content. Using simple models, we show that there are instances where all providers benefit from participating in the collective, but that often, more sophisticated sharing agreements are needed to ensure "fair" utilization of the collective's pooled resources.

Speaker Bio:

Dan Rubenstein has been an Assistant Professor of Electrical Engineering and Computer Science at Columbia University since 2000. He received a B.S. degree in mathematics from M.I.T., an M.A. in math from UCLA, and a PhD in computer science from University of Massachusetts, Amherst. His research interests are in network technologies, applications, and performance analysis, with an emphasis on large-scale Internet design for continuous media transmission. He received a Best Student Paper Award for his ACM SIGMETRICS 2000 paper entitled "Detecting Shared Points of Congestion via End-to-end Measurement" and an NSF CAREER Award in 2002 to continue his investigation of peer-to-peer and overlay networking systems.