diff --git a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
index 31bf8aa..8c25d3a 100644
--- a/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/EagerInvalidatorTest.java
@@ -15,6 +15,7 @@
 
 import static com.google.common.truth.Truth.assertThat;
 import static com.google.devtools.build.skyframe.GraphTester.CONCATENATE;
+import static com.google.devtools.build.skyframe.GraphTester.NODE_TYPE;
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNotNull;
@@ -159,12 +160,12 @@
 
   @Test
   public void receiverWorks() throws Exception {
-    final Set<String> invalidated = Sets.newConcurrentHashSet();
+    final Set<SkyKey> invalidated = Sets.newConcurrentHashSet();
     EvaluationProgressReceiver receiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
         Preconditions.checkState(state == expectedState());
-        invalidated.add(((StringValue) value).getValue());
+        invalidated.add(skyKey);
       }
 
       @Override
@@ -186,21 +187,21 @@
 
     set("a", "c");
     invalidateWithoutError(receiver, skyKey("a"));
-    assertThat(invalidated).containsExactly("a", "ab");
+    assertThat(invalidated).containsExactly(skyKey("a"), skyKey("ab"));
     assertValueValue("ab", "cb");
     set("b", "d");
     invalidateWithoutError(receiver, skyKey("b"));
-    assertThat(invalidated).containsExactly("a", "ab", "b", "cb");
+    assertThat(invalidated).containsExactly(skyKey("a"), skyKey("ab"), skyKey("b"));
   }
 
   @Test
-  public void receiverIsNotNotifiedAboutValuesInError() throws Exception {
-    final Set<String> invalidated = Sets.newConcurrentHashSet();
+  public void receiverIsNotifiedAboutNodesInError() throws Exception {
+    final Set<SkyKey> invalidated = Sets.newConcurrentHashSet();
     EvaluationProgressReceiver receiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
         Preconditions.checkState(state == expectedState());
-        invalidated.add(((StringValue) value).getValue());
+        invalidated.add(skyKey);
       }
 
       @Override
@@ -214,23 +215,31 @@
       }
     };
 
+    // Given a graph consisting of two nodes, "a" and "ab" such that "ab" depends on "a",
+    // And given "ab" is in error,
     graph = new InMemoryGraph();
     set("a", "a");
     tester.getOrCreate("ab").addDependency("a").setHasError(true);
     eval(false, skyKey("ab"));
 
+    // When "a" is invalidated,
     invalidateWithoutError(receiver, skyKey("a"));
-    assertThat(invalidated).containsExactly("a").inOrder();
+
+    // Then the invalidation receiver is notified of both "a" and "ab"'s invalidations.
+    assertThat(invalidated).containsExactly(skyKey("a"), skyKey("ab"));
+
+    // Note that this behavior isn't strictly required for correctness. This test is
+    // meant to document current behavior and protect against programming error.
   }
 
   @Test
   public void invalidateValuesNotInGraph() throws Exception {
-    final Set<String> invalidated = Sets.newConcurrentHashSet();
+    final Set<SkyKey> invalidated = Sets.newConcurrentHashSet();
     EvaluationProgressReceiver receiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
         Preconditions.checkState(state == InvalidationState.DIRTY);
-        invalidated.add(((StringValue) value).getValue());
+        invalidated.add(skyKey);
       }
 
       @Override
@@ -323,17 +332,17 @@
     tester.getOrCreate(parent).addDependency(family[numValues - 1]).setComputedValue(CONCATENATE);
     eval(/*keepGoing=*/false, parent);
     final Thread mainThread = Thread.currentThread();
-    final AtomicReference<SkyValue> badValue = new AtomicReference<>();
+    final AtomicReference<SkyKey> badKey = new AtomicReference<>();
     EvaluationProgressReceiver receiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
-        if (value == childValue) {
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
+        if (skyKey.equals(child)) {
           // Interrupt on the very first invalidate
           mainThread.interrupt();
-        } else if (!childValue.equals(value)) {
-          // All other invalidations should be of the same value.
+        } else if (skyKey.functionName() != NODE_TYPE) {
+          // All other invalidations should have the GraphTester's key type.
           // Exceptions thrown here may be silently dropped, so keep track of errors ourselves.
-          badValue.set(value);
+          badKey.set(skyKey);
         }
         try {
           assertTrue(visitor.get().awaitInterruptionForTestingOnly(2, TimeUnit.HOURS));
@@ -359,16 +368,16 @@
     } catch (InterruptedException e) {
       // Expected.
     }
-    assertNull(badValue.get());
+    assertNull(badKey.get());
     assertFalse(state.isEmpty());
-    final Set<SkyValue> invalidated = Sets.newConcurrentHashSet();
+    final Set<SkyKey> invalidated = Sets.newConcurrentHashSet();
     assertFalse(isInvalidated(parent));
     SkyValue parentValue = graph.getValue(parent);
     assertNotNull(parentValue);
     receiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
-        invalidated.add(value);
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
+        invalidated.add(skyKey);
       }
 
       @Override
@@ -382,7 +391,7 @@
       }
     };
     invalidateWithoutError(receiver);
-    assertTrue(invalidated.contains(parentValue));
+    assertTrue(invalidated.contains(parent));
     assertThat(state.getInvalidationsForTesting()).isEmpty();
 
     // Regression test coverage:
@@ -451,7 +460,7 @@
       final CountDownLatch countDownToInterrupt = new CountDownLatch(countDownStart);
       final EvaluationProgressReceiver receiver = new EvaluationProgressReceiver() {
         @Override
-        public void invalidated(SkyValue value, InvalidationState state) {
+        public void invalidated(SkyKey skyKey, InvalidationState state) {
           countDownToInterrupt.countDown();
           if (countDownToInterrupt.getCount() == 0) {
             mainThread.interrupt();
diff --git a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
index 3ee896e..99a8df6 100644
--- a/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/MemoizingEvaluatorTest.java
@@ -199,9 +199,9 @@
     tester.delete("d1");
     tester.eval(true, "d3");
 
-    assertThat(tester.getDirtyValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
     assertEquals(
-        ImmutableSet.of(new StringValue("1"), new StringValue("123")), tester.getDeletedValues());
+        ImmutableSet.of(skyKey("d1"), skyKey("top")), tester.getDeletedKeys());
     assertEquals(null, tester.getExistingValue("top"));
     assertEquals(null, tester.getExistingValue("d1"));
     assertEquals(d2, tester.getExistingValue("d2"));
@@ -1888,11 +1888,11 @@
       private final AtomicBoolean firstInvalidation = new AtomicBoolean(true);
 
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
         if (interruptInvalidation.get() && !firstInvalidation.getAndSet(false)) {
           thread.interrupt();
         }
-        super.invalidated(value, state);
+        super.invalidated(skyKey, state);
       }
     });
     SkyKey key = null;
@@ -1946,8 +1946,8 @@
     assertFalse(result.hasError());
     topValue = result.get(top);
     assertEquals("leafy", topValue.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
   }
 
   @Test
@@ -1973,15 +1973,14 @@
     tester.invalidate();
     value = (StringValue) tester.evalAndGet("leaf");
     assertEquals("leafy", value.getValue());
-    assertThat(tester.getDirtyValues()).containsExactly(new StringValue("leafysuffix"),
-        new StringValue("leafysuffixsuffix"));
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).containsExactly(mid, top);
+    assertThat(tester.getDeletedKeys()).isEmpty();
     EvaluationResult<StringValue> result = tester.eval(/*keepGoing=*/false, top);
     assertFalse(result.hasError());
     value = result.get(top);
     assertEquals("leafysuffixsuffix", value.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
   }
 
   @Test
@@ -2025,9 +2024,8 @@
     tester.invalidate();
     topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("joyce drank whiskey", topValue.getValue());
-    assertThat(tester.getDirtyValues()).containsExactly(new StringValue("hemingway"),
-        new StringValue("hemingway drank absinthe"));
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).containsExactly(buildFile, top);
+    assertThat(tester.getDeletedKeys()).isEmpty();
   }
 
   @Test
@@ -2042,21 +2040,21 @@
     tester.set(leaf, new StringValue("leafy"));
     StringValue topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("ignore", topValue.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
     // Change leaf.
     tester.set(leaf, new StringValue("crunchy"));
     tester.invalidate();
     topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("ignore", topValue.getValue());
-    assertThat(tester.getDirtyValues()).containsExactly(new StringValue("leafy"));
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).containsExactly(leaf);
+    assertThat(tester.getDeletedKeys()).isEmpty();
     tester.set(leaf, new StringValue("smushy"));
     tester.invalidate();
     topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("ignore", topValue.getValue());
-    assertThat(tester.getDirtyValues()).containsExactly(new StringValue("crunchy"));
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).containsExactly(leaf);
+    assertThat(tester.getDeletedKeys()).isEmpty();
   }
 
   private static final SkyFunction INTERRUPT_BUILDER = new SkyFunction() {
@@ -2104,8 +2102,8 @@
     tester.set(leaf, new StringValue("leafy"));
     StringValue topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("leafy", topValue.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
     failBuildAndRemoveValue(leaf);
     // Leaf should no longer exist in the graph. Check that this doesn't cause problems.
     tester.set(leaf, null);
@@ -2129,8 +2127,8 @@
     tester.set(leaf, new StringValue("leafy"));
     StringValue topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("leafy", topValue.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
     failBuildAndRemoveValue(leaf);
     tester.set(leaf, new StringValue("crunchy"));
     tester.invalidate();
@@ -2199,8 +2197,8 @@
     tester.set(leaf, new StringValue("leafy"));
     StringValue topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("leafy", topValue.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
     // Change leaf.
     tester.getOrCreate(leaf, /*markAsModified=*/true).setHasError(true);
     tester.getOrCreate(top, /*markAsModified=*/false).setHasError(true);
@@ -2224,8 +2222,8 @@
     tester.set(leaf, new StringValue("leafy"));
     StringValue topValue = (StringValue) tester.evalAndGet("top");
     assertEquals("leafysecondError", topValue.getValue());
-    assertThat(tester.getDirtyValues()).isEmpty();
-    assertThat(tester.getDeletedValues()).isEmpty();
+    assertThat(tester.getDirtyKeys()).isEmpty();
+    assertThat(tester.getDeletedKeys()).isEmpty();
     // Invalidate leaf.
     tester.getOrCreate(leaf, /*markAsModified=*/true);
     tester.set(leaf, new StringValue("crunchy"));
@@ -3060,11 +3058,11 @@
       emittedEventState.clear();
     }
 
-    public Set<SkyValue> getDirtyValues() {
+    public Set<SkyKey> getDirtyKeys() {
       return invalidationReceiver.dirty;
     }
 
-    public Set<SkyValue> getDeletedValues() {
+    public Set<SkyKey> getDeletedKeys() {
       return invalidationReceiver.deleted;
     }
 
diff --git a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
index af2c4e0..d414fea 100644
--- a/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
+++ b/src/test/java/com/google/devtools/build/skyframe/ParallelEvaluatorTest.java
@@ -249,7 +249,7 @@
     final Set<SkyKey> receivedValues = Sets.newConcurrentHashSet();
     revalidationReceiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {}
+      public void invalidated(SkyKey skyKey, InvalidationState state) {}
 
       @Override
       public void enqueueing(SkyKey key) {}
@@ -1886,7 +1886,7 @@
     final Set<SkyKey> evaluatedValues = Sets.newConcurrentHashSet();
     EvaluationProgressReceiver progressReceiver = new EvaluationProgressReceiver() {
       @Override
-      public void invalidated(SkyValue value, InvalidationState state) {
+      public void invalidated(SkyKey skyKey, InvalidationState state) {
         throw new IllegalStateException();
       }
 
diff --git a/src/test/java/com/google/devtools/build/skyframe/TrackingInvalidationReceiver.java b/src/test/java/com/google/devtools/build/skyframe/TrackingInvalidationReceiver.java
index 465f32c..a9a7af3 100644
--- a/src/test/java/com/google/devtools/build/skyframe/TrackingInvalidationReceiver.java
+++ b/src/test/java/com/google/devtools/build/skyframe/TrackingInvalidationReceiver.java
@@ -22,21 +22,21 @@
  * A testing utility to keep track of evaluation.
  */
 public class TrackingInvalidationReceiver implements EvaluationProgressReceiver {
-  public final Set<SkyValue> dirty = Sets.newConcurrentHashSet();
-  public final Set<SkyValue> deleted = Sets.newConcurrentHashSet();
+  public final Set<SkyKey> dirty = Sets.newConcurrentHashSet();
+  public final Set<SkyKey> deleted = Sets.newConcurrentHashSet();
   public final Set<SkyKey> enqueued = Sets.newConcurrentHashSet();
   public final Set<SkyKey> evaluated = Sets.newConcurrentHashSet();
 
   @Override
-  public void invalidated(SkyValue value, InvalidationState state) {
+  public void invalidated(SkyKey skyKey, InvalidationState state) {
     switch (state) {
       case DELETED:
-        dirty.remove(value);
-        deleted.add(value);
+        dirty.remove(skyKey);
+        deleted.add(skyKey);
         break;
       case DIRTY:
-        dirty.add(value);
-        Preconditions.checkState(!deleted.contains(value));
+        dirty.add(skyKey);
+        Preconditions.checkState(!deleted.contains(skyKey));
         break;
       default:
         throw new IllegalStateException();
@@ -52,8 +52,10 @@
   public void evaluated(SkyKey skyKey, SkyValue value, EvaluationState state) {
     evaluated.add(skyKey);
     if (value != null) {
-      dirty.remove(value);
-      deleted.remove(value);
+      deleted.remove(skyKey);
+      if (state.equals(EvaluationState.CLEAN)) {
+        dirty.remove(skyKey);
+      }
     }
   }