Mainstream mobile computing devices, such as, smart phones and tablets, currently rely on remote backups for data recovery upon failures. For example, an iPhone periodically stores a recent snapshot to iCloud, that can get restored if needed. Such a commonly used "off-device" backup mechanism, however, suffers from a fundamental limitation, namely, the backup in the remote server is not always synchronized with data stored in the local device.