diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsResponse.java b/service-t/src/com/android/server/connectivity/mdns/MdnsResponse.java
index 3a98b4d..e765d53 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsResponse.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsResponse.java
@@ -96,6 +96,14 @@
     }
 
     /**
+     * @return True if this response contains an identical (original TTL included) record.
+     */
+    public boolean hasIdenticalRecord(@NonNull MdnsRecord record) {
+        final int existing = records.indexOf(record);
+        return existing >= 0 && recordsAreSame(record, records.get(existing));
+    }
+
+    /**
      * Adds a pointer record.
      *
      * @return <code>true</code> if the record was added, or <code>false</code> if a matching
diff --git a/service-t/src/com/android/server/connectivity/mdns/MdnsResponseDecoder.java b/service-t/src/com/android/server/connectivity/mdns/MdnsResponseDecoder.java
index 21792e6..6648729 100644
--- a/service-t/src/com/android/server/connectivity/mdns/MdnsResponseDecoder.java
+++ b/service-t/src/com/android/server/connectivity/mdns/MdnsResponseDecoder.java
@@ -20,6 +20,7 @@
 import android.annotation.Nullable;
 import android.net.Network;
 import android.os.SystemClock;
+import android.util.ArrayMap;
 import android.util.ArraySet;
 import android.util.Pair;
 
@@ -139,8 +140,11 @@
 
         final ArraySet<MdnsResponse> modified = new ArraySet<>();
         final ArrayList<MdnsResponse> responses = new ArrayList<>(existingResponses.size());
+        final ArrayMap<MdnsResponse, MdnsResponse> augmentedToOriginal = new ArrayMap<>();
         for (MdnsResponse existing : existingResponses) {
-            responses.add(new MdnsResponse(existing));
+            final MdnsResponse copy = new MdnsResponse(existing);
+            responses.add(copy);
+            augmentedToOriginal.put(copy, existing);
         }
         // The response records are structured in a hierarchy, where some records reference
         // others, as follows:
@@ -166,7 +170,7 @@
         // A: host name -> IP address
 
         // Loop 1: find PTR records, which identify distinct service instances.
-        long now = SystemClock.elapsedRealtime();
+        long now = clock.elapsedRealtime();
         for (MdnsRecord record : records) {
             if (record instanceof MdnsPointerRecord) {
                 String[] name = record.getName();
@@ -262,7 +266,11 @@
                         findResponsesWithHostName(responses, inetRecord.getName());
                 for (MdnsResponse response : matchingResponses) {
                     if (assignInetRecord(response, inetRecord)) {
-                        modified.add(response);
+                        final MdnsResponse originalResponse = augmentedToOriginal.get(response);
+                        if (originalResponse == null
+                                || !originalResponse.hasIdenticalRecord(inetRecord)) {
+                            modified.add(response);
+                        }
                     }
                 }
             } else {
@@ -270,12 +278,26 @@
                         findResponseWithHostName(responses, inetRecord.getName());
                 if (response != null) {
                     if (assignInetRecord(response, inetRecord)) {
-                        modified.add(response);
+                        final MdnsResponse originalResponse = augmentedToOriginal.get(response);
+                        if (originalResponse == null
+                                || !originalResponse.hasIdenticalRecord(inetRecord)) {
+                            modified.add(response);
+                        }
                     }
                 }
             }
         }
 
+        // Only responses that have new or modified address records were added to the modified set.
+        // Make sure responses that have lost address records are added to the set too.
+        for (int i = 0; i < augmentedToOriginal.size(); i++) {
+            final MdnsResponse augmented = augmentedToOriginal.keyAt(i);
+            final MdnsResponse original = augmentedToOriginal.valueAt(i);
+            if (augmented.getRecords().size() != original.getRecords().size()) {
+                modified.add(augmented);
+            }
+        }
+
         return Pair.create(modified, responses);
     }
 
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsResponseDecoderTests.java b/tests/unit/java/com/android/server/connectivity/mdns/MdnsResponseDecoderTests.java
index 31383d1..0d479b1 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsResponseDecoderTests.java
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsResponseDecoderTests.java
@@ -28,6 +28,7 @@
 import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
+import static org.mockito.Mockito.doReturn;
 import static org.mockito.Mockito.mock;
 
 import android.net.Network;
@@ -407,6 +408,31 @@
     }
 
     @Test
+    public void testDecodeWithIpv4AddressRemove() throws IOException {
+        MdnsResponse response = makeMdnsResponse(0, DATAIN_SERVICE_NAME_1, List.of(
+                new PacketAndRecordClass(DATAIN_PTR_1,
+                        MdnsPointerRecord.class),
+                new PacketAndRecordClass(DATAIN_SERVICE_1,
+                        MdnsServiceRecord.class),
+                new PacketAndRecordClass(DATAIN_IPV4_1,
+                        MdnsInet4AddressRecord.class),
+                new PacketAndRecordClass(DATAIN_IPV4_2,
+                        MdnsInet4AddressRecord.class)));
+        // Now update the response removing the second v4 address
+        final MdnsResponseDecoder decoder = new MdnsResponseDecoder(mClock, null);
+
+        final byte[] removedAddrResponse = makeResponsePacket(
+                List.of(DATAIN_PTR_1, DATAIN_SERVICE_1, DATAIN_IPV4_1));
+        final ArraySet<MdnsResponse> changes = decode(
+                decoder, removedAddrResponse, List.of(response));
+
+        assertEquals(1, changes.size());
+        assertEquals(1, changes.valueAt(0).getInet4AddressRecords().size());
+        assertEquals(parseNumericAddress("10.1.2.3"),
+                changes.valueAt(0).getInet4AddressRecords().get(0).getInet4Address());
+    }
+
+    @Test
     public void testDecodeWithIpv6AddressChange() throws IOException {
         MdnsResponse response = makeMdnsResponse(0, DATAIN_SERVICE_NAME_1, List.of(
                 new PacketAndRecordClass(DATAIN_PTR_1,
@@ -427,6 +453,29 @@
     }
 
     @Test
+    public void testDecodeWithIpv6AddressRemoved() throws IOException {
+        MdnsResponse response = makeMdnsResponse(0, DATAIN_SERVICE_NAME_1, List.of(
+                new PacketAndRecordClass(DATAIN_PTR_1,
+                        MdnsPointerRecord.class),
+                new PacketAndRecordClass(DATAIN_SERVICE_1,
+                        MdnsServiceRecord.class),
+                new PacketAndRecordClass(DATAIN_IPV6_1,
+                        MdnsInet6AddressRecord.class),
+                new PacketAndRecordClass(DATAIN_IPV6_2,
+                        MdnsInet6AddressRecord.class)));
+        // Now update the response adding an address
+        final MdnsResponseDecoder decoder = new MdnsResponseDecoder(mClock, null);
+        final byte[] removedAddrResponse = makeResponsePacket(
+                List.of(DATAIN_PTR_1, DATAIN_SERVICE_1, DATAIN_IPV6_1));
+        final ArraySet<MdnsResponse> updatedResponses = decode(
+                decoder, removedAddrResponse, List.of(response));
+        assertEquals(1, updatedResponses.size());
+        assertEquals(1, updatedResponses.valueAt(0).getInet6AddressRecords().size());
+        assertEquals(parseNumericAddress("aabb:ccdd:1122:3344:a0b0:c0d0:1020:3040"),
+                updatedResponses.valueAt(0).getInet6AddressRecords().get(0).getInet6Address());
+    }
+
+    @Test
     public void testDecodeWithChangeOnText() throws IOException {
         MdnsResponse response = makeMdnsResponse(0, DATAIN_SERVICE_NAME_1, List.of(
                 new PacketAndRecordClass(DATAIN_PTR_1,
@@ -493,11 +542,12 @@
                         new PacketAndRecordClass(DATAIN_IPV4_1, MdnsInet4AddressRecord.class),
                         new PacketAndRecordClass(DATAIN_IPV6_1, MdnsInet6AddressRecord.class),
                         new PacketAndRecordClass(DATAIN_PTR_1, MdnsPointerRecord.class),
-                        new PacketAndRecordClass(DATAIN_SERVICE_2, MdnsServiceRecord.class),
+                        new PacketAndRecordClass(DATAIN_SERVICE_1, MdnsServiceRecord.class),
                         new PacketAndRecordClass(DATAIN_TEXT_1, MdnsTextRecord.class));
         // Create a two identical responses.
-        MdnsResponse response = makeMdnsResponse(0, DATAIN_SERVICE_NAME_1, recordList);
+        MdnsResponse response = makeMdnsResponse(12L /* time */, DATAIN_SERVICE_NAME_1, recordList);
 
+        doReturn(34L).when(mClock).elapsedRealtime();
         final MdnsResponseDecoder decoder = new MdnsResponseDecoder(mClock, null);
         final byte[] identicalResponse = makeResponsePacket(
                 recordList.stream().map(p -> p.packetData).collect(Collectors.toList()));
diff --git a/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java b/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java
index f9c0a19..a61e8b2 100644
--- a/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java
+++ b/tests/unit/java/com/android/server/connectivity/mdns/MdnsServiceTypeClientTests.java
@@ -1078,21 +1078,17 @@
                 0 /* flags */,
                 Collections.emptyList() /* questions */,
                 List.of(
-                        // TODO: cacheFlush will cause addresses to be cleared and re-added every
-                        //  time, which is considered a change and triggers extra
-                        //  onServiceChanged callbacks. Sets cacheFlush bit to false until the
-                        //  issue is fixed.
                         new MdnsServiceRecord(serviceName, updatedReceiptTime,
-                                false /* cacheFlush */, TEST_TTL, 0 /* servicePriority */,
+                                true /* cacheFlush */, TEST_TTL, 0 /* servicePriority */,
                                 0 /* serviceWeight */, 1234 /* servicePort */, hostname),
                         new MdnsTextRecord(serviceName, updatedReceiptTime,
-                                false /* cacheFlush */, TEST_TTL,
+                                true /* cacheFlush */, TEST_TTL,
                                 Collections.emptyList() /* entries */),
                         new MdnsInetAddressRecord(hostname, updatedReceiptTime,
-                                false /* cacheFlush */, TEST_TTL,
+                                true /* cacheFlush */, TEST_TTL,
                                 InetAddresses.parseNumericAddress(ipV4Address)),
                         new MdnsInetAddressRecord(hostname, updatedReceiptTime,
-                                false /* cacheFlush */, TEST_TTL,
+                                true /* cacheFlush */, TEST_TTL,
                                 InetAddresses.parseNumericAddress(ipV6Address))),
                 Collections.emptyList() /* authorityRecords */,
                 Collections.emptyList() /* additionalRecords */);