diff --git a/services_state/services_state.go b/services_state/services_state.go
index <HASH>..<HASH> 100644
--- a/services_state/services_state.go
+++ b/services_state/services_state.go
@@ -148,7 +148,17 @@ func (state *ServicesState) TombstoneServices(containerList []service.Service) [
 		mapping[container.ID] = &container
 	}
 
-	for id, svc := range state.Servers[hostname].Services {
+	// Copy this so we can change the real list in the loop
+	services := state.Servers[hostname].Services
+
+	for id, svc := range services {
+		// Manage tombstone life so we don't keep them forever
+		if svc.Status == service.TOMBSTONE &&
+				svc.Updated.Before(time.Now().UTC().Add(0 - TOMBSTONE_LIFESPAN)) {
+			delete(state.Servers[hostname].Services, id)
+			continue
+		}
+
 		if mapping[id] == nil && svc.Status == service.ALIVE {
 			log.Printf("Tombstoning %s\n", svc.ID)
 			svc.Tombstone()
Manage tombstone lifespan.

We don't want to keep them forever or we build up state
forever. This will remove them after a timeout window.
The result is that anyone partitioned from the cluster
for more than TOMBSTONE_LIFESPAN and believing that a
service is alive will re-add it to the cluster.

Need to add functionality to flush state when hosts
leave the cluster.