BLISS Seminar: Queues, Balls and Bins, and Association

Seminar | March 19 | 3-4 p.m. | 540 Cory Hall

 R Srikant, UIUC

 Electrical Engineering and Computer Sciences (EECS)

We consider a problem motivated by file retrieval in cloud computing systems where storage coding is used. In such problems, each file-retrieval job consists of multiple tasks (each corresponding to the retrieval of a coded chunk of a file), and the job is completed only when all of its tasks are completed. The goal is to compute the tail probability of the job completion time. However, this is a difficult problem whereas the problem of computing tail probabilities of task completion times is relatively easy. We will show that, by assuming that the task completion times are independent, one can compute an upper bound on the tail probability of the job completion time. The result is obtained by proving that the task completions times at the various servers in the cloud system are associated. The key step in the proof can be easily understood by considering a corresponding balls-and-bins problem as we will illustrate in the talk. Joint work with Weina Wang, Mor Harchol-Balter, Haotian Jiang, and Alan Scheller-Wolf.