Online social networks (OSNs) are immensely popular, but their centralized control of user data raises important privacy concerns. This paper presents Vis-à-Vis, a decentralized framework for OSNs based on the privacy-preserving notion of a Virtual Individual Server (VIS). A VIS is a personal virtual machine running in a paid compute utility. In Vis-à-Vis, a person stores her data on her own VIS, which arbitrates access to that data by others. VISs self-organize into overlay networks corresponding to social groups. This paper focuses on preserving the privacy of location information. Vis-à-Vis uses distributed location trees to provide efficient and scalable operations for sharing location information within social groups. We have evaluated our Vis-à-Vis prototype using hundreds of virtual machines running in the Amazon EC2 compute utility. Our results demonstrate that Vis-à-Vis represents an attractive complement to today's centralized OSNs.