March 06, 2017

Resource Allocation for Coded Distributed Computing

  • Avestimehr S.
  • Liz S.
  • Maddahali M.
  • Yu Q.

A data center has an abundance of processing power (e.g., it hosts tens of thousands of servers). To execute a distributed computing job, it is natural to have multiple servers working on different parts of the job in parallel to reduce the computation time. On the other hand, in most cases the intermediate results computed by these servers needs to be collected by a server in order to execute a second stage computation. Thus, spreading the computation jobs onto too many servers may also increase the communication time. It is valuable to find the optimal way of assigning the computation resources to a problem, in order to solve it as soon as possible. We consider a simple distributed computing framework, where the goal is to compute Q arbitrary functions from N files, by decomposing the overall computation into a set of "Map" and "Reduce" functions. We study the minimum possible total execution time for completing an arbitrary distributed computing jobs, when one have access to arbitrary number of servers. We give the exact minimum possible execution time for all possible values of problem parameters, and we provide the corresponding optimal computing schemes. In most cases, the proposed optimal scheme can exactly achieve the minimum execution time using only a finite number of servers. We prove a matching information theoretic converse showing that our proposed scheme exactly achieve the minimum execution time. Besides, we also prove that among all possible computing schemes that achieves the minimum execution time, our proposed scheme also uses the exact minimum possible number of servers.

View Original Article

Recent Publications

August 09, 2017

A Cloud Native Approach to 5G Network Slicing

  • Francini A.
  • Miller R.
  • Sharma S.

5G networks will have to support a set of very diverse and often extreme requirements. Network slicing offers an effective way to unlock the full potential of 5G networks and meet those requirements on a shared network infrastructure. This paper presents a cloud native approach to network slicing. The cloud ...

August 01, 2017

Modeling and simulation of RSOA with a dual-electrode configuration

  • De Valicourt G.
  • Liu Z.
  • Violas M.
  • Wang H.
  • Wu Q.

Based on the physical model of a bulk reflective semiconductor optical amplifier (RSOA) used as a modulator in radio over fiber (RoF) links, the distributions of carrier density, signal photon density, and amplified spontaneous emission photon density are demonstrated. One of limits in the use of RSOA is the lower ...

July 12, 2017

PrivApprox: Privacy-Preserving Stream Analytics

  • Chen R.
  • Christof Fetzer
  • Le D.
  • Martin Beck
  • Pramod Bhatotia
  • Thorsten Strufe

How to preserve users' privacy while supporting high-utility analytics for low-latency stream processing? To answer this question: we describe the design, implementation and evaluation of PRIVAPPROX, a data analytics system for privacy-preserving stream processing. PRIVAPPROX provides three properties: (i) Privacy: zero-knowledge privacy (ezk) guarantees for users, a privacy bound tighter ...