Jonathan Ellis (@spyced) explains the complexity of performing a delete operation in a distributed, eventually consistent system and how Cassandra deals with this operation.
Thus, a delete operation can’t just wipe out all traces of the data being removed immediately […] So, instead of wiping out data on delete, Cassandra replaces it with a special value called a tombstone. The tombstone can then be propagated to replicas that missed the initial remove request.
Cassandra does what distributed systems designers frequently do when confronted with a problem we don’t know how to solve: define some additional constraints that turn it into one that we do. Here, we defined a constant,
GCGraceSeconds, and had each node track tombstone age locally.
The post also includes some details about how Cassandra is dealing with eventual consistency by supporting hinted handoff ☞, read repair ☞ and anti entropy ☞ for reducing the inconsistency window.