Avatar is a system that leverages cloud resources to support fast, scalable, reliable, and energy efficient distributed computing over mobile devices. An avatar is a per-user software entity in the cloud that runs apps on behalf of the user's mobile devices. The avatars are instantiated as virtual machines in the cloud that run the same operating system with the mobile devices. In this way, avatars provide resource isolation and execute unmodified app components, which simplifies technology adoption. Avatar apps execute over distributed and synchronized (mobile device, avatar) pairs to achieve a global goal. The three main challenges that must be overcome by the Avatar system are: creating a high-level programming model and a middleware that enable effective execution of distributed applications on a combination of mobile devices and avatars, re-designing the cloud architecture and protocols to support billions of mobile users and mobile apps with very different characteristics from the current cloud workloads, and explore new approaches that balance privacy guarantees with app efficiency/usability. We have built a basic Avatar prototype on Android devices and Android x86 virtual machines. An application that searches for a lost child by analyzing the photos taken by people at a crowded public event runs on top of this prototype.