diff --git a/java/com/android/dialer/common/concurrent/DialerFutures.java b/java/com/android/dialer/common/concurrent/DialerFutures.java
new file mode 100644
index 0000000..9829982
--- /dev/null
+++ b/java/com/android/dialer/common/concurrent/DialerFutures.java
@@ -0,0 +1,138 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License
+ */
+
+package com.android.dialer.common.concurrent;
+
+import com.google.common.base.Predicate;
+import com.google.common.collect.ImmutableList;
+import com.google.common.util.concurrent.AbstractFuture;
+import com.google.common.util.concurrent.Atomics;
+import com.google.common.util.concurrent.Futures;
+import com.google.common.util.concurrent.ListenableFuture;
+import com.google.common.util.concurrent.MoreExecutors;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.atomic.AtomicReference;
+
+/** Static utility methods related to futures. */
+public class DialerFutures {
+
+  /**
+   * Returns a future that will complete with the same value as the first matching the supplied
+   * predicate, cancelling all inputs upon completion. If none match, {@code defaultValue} is
+   * returned.
+   *
+   * <p>If an input fails, it is treated as if the predicate did not match.
+   *
+   * <p>Cancellation of the output future will cause cancellation of all input futures.
+   *
+   * @throws IllegalArgumentException if {@code futures} is empty.
+   */
+  public static <T> ListenableFuture<T> firstMatching(
+      Iterable<? extends ListenableFuture<? extends T>> futures,
+      Predicate<T> predicate,
+      T defaultValue) {
+    return firstMatchingImpl(futures, predicate, defaultValue);
+  }
+
+  private static <T> ListenableFuture<T> firstMatchingImpl(
+      Iterable<? extends ListenableFuture<? extends T>> futures,
+      Predicate<T> predicate,
+      T defaultValue) {
+    AggregateFuture<T> output = new AnyOfFuture<>(futures);
+    // Use an atomic reference to ensure that late listeners don't pin the FirstOfFuture in memory.
+    final AtomicReference<AggregateFuture<T>> ref = Atomics.newReference(output);
+    final AtomicInteger pending = new AtomicInteger(output.futures.size());
+    for (final ListenableFuture<? extends T> future : output.futures) {
+      future.addListener(
+          new Runnable() {
+            @Override
+            public void run() {
+              // Call get() and then set() instead of getAndSet() because a volatile read/write is
+              // cheaper than a CAS and atomicity is guaranteed by setFuture.
+              AggregateFuture<T> output = ref.get();
+              if (output != null) {
+                boolean threw = false;
+                T value = null;
+                try {
+                  value = Futures.getDone(future);
+                } catch (ExecutionException e) {
+                  threw = true;
+                }
+                if (threw || !predicate.apply(value)) {
+                  if (pending.decrementAndGet() == 0) {
+                    // we are the last future (and every other future hasn't matched or failed).
+                    output.set(defaultValue);
+                    // no point in clearing the ref, every other listener has already run
+                  }
+                } else {
+                  ref.set(null); // unpin
+                  output.set(value);
+                }
+              }
+            }
+          },
+          MoreExecutors.directExecutor());
+    }
+    return output;
+  }
+
+  private static class AggregateFuture<T> extends AbstractFuture<T> {
+    ImmutableList<ListenableFuture<? extends T>> futures;
+
+    AggregateFuture(Iterable<? extends ListenableFuture<? extends T>> futures) {
+      ImmutableList<ListenableFuture<? extends T>> futuresCopy = ImmutableList.copyOf(futures);
+      if (futuresCopy.isEmpty()) {
+        throw new IllegalArgumentException("Expected at least one future, got 0.");
+      }
+      this.futures = futuresCopy;
+    }
+
+    // increase visibility
+    @Override
+    protected boolean set(T t) {
+      return super.set(t);
+    }
+
+    @Override
+    protected boolean setFuture(ListenableFuture<? extends T> t) {
+      return super.setFuture(t);
+    }
+  }
+
+  // Propagates cancellation to all inputs cancels all inputs upon completion
+  private static final class AnyOfFuture<T> extends AggregateFuture<T> {
+    AnyOfFuture(Iterable<? extends ListenableFuture<? extends T>> futures) {
+      super(futures);
+    }
+
+    @SuppressWarnings("ShortCircuitBoolean")
+    @Override
+    protected void afterDone() {
+      ImmutableList<ListenableFuture<? extends T>> localFutures = futures;
+      futures = null; // unpin
+      // even though afterDone is only called once, it is possible that the 'futures' field is null
+      // because it isn't final and thus the write might not be visible if the future instance was
+      // unsafely published.  See the comment at the top of Futures.java on memory visibility.
+      if (localFutures != null) {
+        boolean interrupt = !isCancelled() | wasInterrupted();
+        for (ListenableFuture<? extends T> future : localFutures) {
+          future.cancel(interrupt);
+        }
+      }
+    }
+  }
+}
diff --git a/java/com/android/dialer/phonelookup/composite/CompositePhoneLookup.java b/java/com/android/dialer/phonelookup/composite/CompositePhoneLookup.java
index 10b0e24..ba08fe9 100644
--- a/java/com/android/dialer/phonelookup/composite/CompositePhoneLookup.java
+++ b/java/com/android/dialer/phonelookup/composite/CompositePhoneLookup.java
@@ -19,9 +19,11 @@
 import android.support.annotation.NonNull;
 import android.telecom.Call;
 import com.android.dialer.DialerPhoneNumber;
+import com.android.dialer.common.concurrent.DialerFutures;
 import com.android.dialer.phonelookup.PhoneLookup;
 import com.android.dialer.phonelookup.PhoneLookupInfo;
 import com.google.common.base.Function;
+import com.google.common.base.Preconditions;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.ImmutableSet;
@@ -73,7 +75,14 @@
   @Override
   public ListenableFuture<Boolean> isDirty(
       ImmutableSet<DialerPhoneNumber> phoneNumbers, long lastModified) {
-    return null;
+    List<ListenableFuture<Boolean>> futures = new ArrayList<>();
+    for (PhoneLookup phoneLookup : phoneLookups) {
+      futures.add(phoneLookup.isDirty(phoneNumbers, lastModified));
+    }
+    // Executes all child lookups (possibly in parallel), completing when the first composite lookup
+    // which returns "true" completes, and cancels the others.
+    return DialerFutures.firstMatching(
+        futures, Preconditions::checkNotNull, false /* defaultValue */);
   }
 
   @Override