Title: Practical Models of Computation in Fault-Prone Clouds
Speaker: Dr. Greg Malewicz, Google
Time: 4:30pm, Oct 26 (Mon), 2009
Place: Room 101, CSIE building

Abstract:

(** The talk is targeting researchers, not students)

Many companies, including Google, operate datacenters consisting of networked commodity computers. Solving practical computational problems on such datacenters can be difficult because of several challenges. Input data can be significantly imbalanced, resulting in hotspots. Individual computers can fail. Even in the absence of failure computers can work at varying paces, introducing delays. Many models of computation have complicated semantics, making programming difficult, and some theoretical models do not have any scalable and efficient realization that is suitable for industrial use.

Google has introduced several models of computation that meet these challenges. The best known example is MapReduce where input records are transformed and intermediate records are grouped by key and passed to a reduce operation. Other example is Pregel, a graph computing system where vertices send messages to one another in a series of iterations separated by synchronization barriers. Despite the simplicity of these models, many useful algorithms can easily be expressed in them.

In this talk I will describe these models, the challenges in implementing them, and the techniques that led to the first successful sort of 1PB of data in 6h 2m.


Short Biography:

Greg Malewicz received the BA degrees in computer science and in applied mathematics in 1996 and 1998, respectively, and the MS degree in computer science in 1998, all from the University of Warsaw. He received the PhD degree in computer science from the University of Connecticut in 2003 with his last year at Massachusetts Institute of Technology. He is an engineer at Google designing simple and expressive models of computation and realizing them as scalable systems so as to make data processing in the cloud simple. He co-founded the Pregel project for graph processing and earlier worked on MapReduce, which lead to the first successful 1PB sort (both projects are team efforts). He has had internships at the AT&T Shannon Laboratory (summer 2001) and Microsoft Corp. (summer 2000 and fall 2001). He was a visiting scientist at the University of Massachusetts, Amherst (summer 2004) and Argonne National Laboratory (summer 2005), and an assistant professor at the University of Alabama, where he taught computer science (2003 until 2005). His research focuses on high-performance parallel and distributed computing, experimental and theoretical algorithmics, combinatorial optimization, and scheduling. His research appears in top journals and conferences and includes a singly authored SIAM Journal on Computing paper that solves a decade-old problem in distributed computing.

Greg is an avid traveler. His bicycle and friends toured the Himalayas, the Andes and the Alps, including Khardung La, which he cycled as the first Pole. Check out Greg's photos from bicycle and other trips( http://www.cs.ua.edu/~greg/personal.html ). Friendly comments are very welcome!