|Speaker: Mor Harchol-Balter (CMU)
Title: A Better Model for Task Assignment in Server Farms: How Replication can Help
Abstract: An age-old problem in the design of server farms is the choice of the task assignment policy. This is the algorithm that determines how to assign incoming jobs to servers. Popular policies include Round-Robin assignment, Join-the-Shortest-Queue, Join-Queue-with-Least-Work, and so on.
While much research has studied assignment policies, little has taken into account server-side variability – the fact that the server we choose might be temporarily and unpredictably slow. We show that when server-side variability dominates runtime, replication of jobs can be very beneficial. We introduce the Replication-d algorithm that replicates each arrival to d servers chosen at random, where the job is considered “done” as soon as the first replica completes. We provide an exact closed-form analysis of Replication-d.
We next introduce a much more general model, one which takes both the inherent job size distribution and the server-side variability into account. This is a departure from traditional queueing models which only allow for one “size” distribution. We propose and analyze a new task assignment policy, Replicate-Idle-Queue (RIQ), which is designed to perform well given these dual sources of variability.
Bio: Mor Harchol-Balter is a Professor of Computer Science at Carnegie Mellon. She received her Ph.D. from U.C. Berkeley in Computer Science, completed her postdoc at MIT, and joined CMU in 1999. From 2008-2011, she served as the Associate Department Head for Computer Science. Mor is a recipient of the McCandless Junior Chair, the NSF CAREER award, and several teaching awards, including the Herbert A. Simon Award.
Mor’s work focuses on designing new resource allocation policies, including load balancing policies, power man- agement policies, and scheduling policies, for distributed systems. She is known for both her new techniques in queueing-theoretic analysis and Markov chains, as well as her work in computer systems implementation. Mor has co-authored over 100 publications in top journals and conferences, including a textbook, Performance Analysis and Design of Computer Systems, published by Cambridge University Press, 2013.
Mor is heavily involved in the ACM SIGMETRICS / PERFORMANCE research community, where she has published over two dozen papers, and received multiple best paper awards, and where she served as Technical Program Chair in 2007 and as General Chair in 2013. She is best known for her enthusiastic talks and her many PhD students, most of whom are professors in top academic institutions.
|Speaker: Philippe Jacquet (Nokia)
Title: Breathing the thoughts of mankind
Abstract: Mankind has never been connected as it is now and as it will be tomorrow. Nowadays thanks to the rise of social networks such as Tweeter and Facebook, we can follow in real time the thought of millions of people. In fact we can almost feel the thoughts of a whole humanity and maybe project ourselves in a position where we could predict the major trends in the collective behavior of this humanity.
However such an ambitious aim would require considerable resources in processing and networking which may be far from affordable. Indeed trends and topics are carried in a multiple of small texts written in various language and vocabularies like an hologram carries information in a dispersed way. Their capture and classification pose serious problems of data mining and analytics. Processes based on pure semantic analysis would require too much processing power and memory. We will present alternative methods based on string complexity also inspired on geolocalization in wireless networks which saves processing power by several order of magnitude. The ultimate goal is to detect when people are thinking about the very same topics before they become aware. Beyond the problem of topic detection and classification one must also estimate the potential of an isolated topic to become a lasting trend. In other word one must probe the topic foundations, for example by challenging how trustworthy are its sources. Designing an efficient source finder algorithm is indissociable with building realistic models about topic propagation. If we suppose that topics propagate inside communities via the followers-followees links, the propagation is highly amplified by the unbalances in the graph topology. It is established that dominating and semi dominating nodes such as the CNN Tweeter site are the main accelerator of topic propagation. The difficulty is to find the actual source of a topic beyond those screening nodes and the search is prone to false positive and true negative effects. In fact we will show that finding a source of topic is similar to finding a common ancestor in a Darwin channel where spurious mutations complicate the task.
Bio: Philippe Jacquet graduated form Ecole Polytechnique, Paris, France in 1981, and from Ecole des Mines in 1984. He received his PhD degree from Paris Sud University in 1989. Since 1998, he has been a research director in Inria, a major public research lab in Computer Science in France. He has been a major contributor to the Internet OLSR protocol for mobile networks. His research interests involve information theory, probability theory, quantum telecommunication, protocol design, performance evaluation and optimization, and the analysis of algorithms. Since 2012 he is with Nokia (formerly Alcatel-Lucent) Bell Labs as head of the department of mathematics of dynamic networks and information.
Speaker: Yi Lu (UIUC)
Title: Cloud Computing and Big Data Analytics - What I learned over the last five years