Dağıtık anahtar-değer depolarında silme işlemi, yazma işlemine kıyasla çok daha karmaşık bir tutarlılık problemi doğurur. Gerçek anlamda silme, yani fiziksel olarak verinin kaldırılması, replikasyon ortamında bir anti-pattern haline gelir; çünkü silme bilgisinin kendisi de bir mutasyon olup tüm node'lara iletilmesi gerekir. İşte bu noktada tombstone mekanizması devreye girer. Tombstone dağıtık depolama sistemlerinde, silinen bir anahtarın yerine özel bir işaretçi, tombstone kaydı, yazılır. Bu kayıt, ilgili anahtarın artık geçersiz olduğunu cluster genelinde propagate eder. Cassandra gibi LSM-tree tabanlı motorlarda tombstone'lar, arka planda çalışan compaction süreçleri tamamlanana kadar disk üzerinde yaşamaya devam eder. Buradaki kritik nokta şudur: compaction öncesinde bir tombstone'un süresi dolmamışsa, veri teorik olarak "silinmiş" olmasına karşın depolama alanını işgal etmeye devam eder. Kademeli silme (soft delete) ile tombstone yaklaşımı arasındaki temel ayrım, işlemin semantiğinde yatar. Kademeli silmede uygulama katmanı "deleted" bayrağıyla mantıksal bir silme gerçekleştirirken, tombstone dağıtık depolama motorunun kendi protokolüne entegre edilmiş bir mekanizmadır. Motor, okuma sırasında tombstone varlığını tespit edince ilgili anahtarı sonuç kümesinden eleme kararını alır; bu karar hem koordinatör node hem de replika node'lar arasındaki uzlaşma sürecini etkiler. Tutarlılık açısından en kritik senaryo, "zombie read" durumudur. Eğer bir replika tombstone kaydını almadan önce okuma isteğiyle karşılaşırsa, çoktan silinmiş bir veriyi döndürebilir. Bu durum özellikle eventual consistency modelinde çalışan sistemlerde sorun çıkarır. Çözüm olarak, tombstone dağıtık depolama protokollerinde hinted handoff ve read repair mekanizmaları birlikte çalışarak tombstone'ların geç gelen replikalar tarafından da uygulanmasını sağlar. Tombstone birikimi, tombstone accumulation, ayrı bir performans boyutu taşır. Yüksek silme oranlı iş yüklerinde, compaction tetiklenmeden önce binlerce tombstone birikimlenmişse okuma gecikmesi belirgin biçimde artar; çünkü her okuma isteği tombstone'ları atlayarak gerçek veriye ulaşmaya çalışır. Bu nedenle gc_grace_seconds parametresi, tutarlılık ile depolama verimliliği arasındaki dengeyi belirleyen kritik bir yapılandırma değişkenidir: çok kısa tutulursa zombie read riski artar, çok uzun tutulursa disk baskısı yoğunlaşır. Praktik olarak, tombstone dağıtık depolama tasarımında dikkat edilmesi gereken bir diğer boyut, silme yoğunluğu ile okuma amplification arasındaki ters korelasyondur. Wide-row tasarımı benimseyen tablolarda tek bir partition içinde çok sayıda tombstone birikimlenmesi, koordinatör node'un tombstone uyarısı fırlatmasına, tombstone warning, yol açar. Bu uyarıyı görmezden gelen sistemlerde zamanla partition'ın okunması timeout'a düşer.