Nowadays, rich information about the context of mobile users is directly captured on the users' mobile phones in real-time. Especially, discrete context (e.g., the user's activity) has become highly interesting for many applications since it provides an intuitive and human-understandable description of the user's current state. However, while sensing is executed locally on the mobile device, changes of user context need to be distributed from the device to a large number of interested consumers, e.g., the friends in an online social network. This produces a large overhead for the continuous transmission of context updates and represents a serious challenge for the limited energy budget of battery-equipped mobile devices. In this paper, we propose different strategies for energy-efficient context updates. We present a number of update protocols that are characterized by an inherent trade-off between quality of context and message overhead. To this end, we investigate update criteria that allow consumers of context information to express their tolerance towards the inaccurateness of received context, and we propose update protocols that exploit this tolerance to save updates and, thus, energy. In our evaluation we analyse our update protocols based on a real-world trace of user activities and show that applications can save more than 80% of the messages when tolerating a minor degradation of the context quality only.