As the Online Social Networks (OSNs) amass unprecedented amounts of personal information, the privacy concerns gain considerable attention from the community. Apart from privacy-enabling approaches for existing OSNs, a number of initiatives towards building decentralized OSN infrastructures have emerged. However, before this paradigm becomes a serious alternative to current centralized infrastructures, some key design challenges, often conflicting with each other, have to be addressed. In this paper, we explore such design objectives concerning various system properties, namely availability, replication degree, user online times, privacy, and experimentally study the tradeoffs among them based on real data sets from Facebook and Twitter. We introduce different mechanisms to model user online times in the OSN from their activity times. We demonstrate how different profile replica selection approaches significantly affect the system performance.