This paper describes two techniques that are only loosely related. The first is a method for constructing a highly available service for use in a distributed system. The service presents its clients with a consistent view of its state, but the view may contain old information. Clients can indicate how recent the information must be. The method can be used in any application in which the property of interest is stable: once the property becomes true, it remains true forever. The paper also describes a fault-tolerant garbage collection method for a distributed heap. The method is practical and efficient. Each computer that contains part of the heap does local garbage collection independently, using whatever algorithm it chooses, and without needing to communicate with the other computers that contain parts of the heap. The highly available central service is used to store information about inter-computer references. (kr)