A fundamental capability of cloud computing is elasticity, i.e., the ability to dynamically change the amount of allocated resources. This is typically done by adjusting the number of VMs running a service based on the current demand for that service. For large services, centralized management is impractical and distributed methods should be employed. In such settings, no single component has full information on demand and service quality, thus elasticity becomes a real challenge. The presented method addresses this challenge by proposing a novel elasticity scheme that enables fully distributed management of large cloud services. Our fully distributed scheme can easily adapt to varying loads, effectively minimizing the number of VMs leased from the cloud, and, consequently, the operation cost, while meeting SLA requirements.