Distributed systems require strategies to detect and recover from failures. Many protocols for distributed systems employ a strategy based on leases, which grant a leaseholder access to data or services for a limited time (the lease period). Choosing an appropriate lease period involves tradeoffs among resource utilization, responsiveness, and system size. We explain these tradeoffs for Jini Network Technology. Then, we describe an adaptive algorithm that enables a Jini system, given a fixed allocation of resources, to vary lease periods with system size to achieve the best responsiveness. We anticipate that similar procedures could improve failure responsiveness in other distributed systems that rely on leases. We describe how we implemented our adaptive algorithm in "reggie", a publicly available implementation of the Jini lookup service. We can use our implementation to demonstrate how adaptive leasing provides the best available responsiveness as network size varies.