diff --git a/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationDaemon.java b/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationDaemon.java
index 0a89106..60600a9 100644
--- a/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationDaemon.java
+++ b/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationDaemon.java
@@ -28,7 +28,9 @@
 import java.nio.file.Path;
 import java.time.Duration;
 import java.util.Arrays;
+import java.util.Iterator;
 import java.util.List;
+import java.util.Map;
 import java.util.Optional;
 import org.eclipse.jgit.lib.Ref;
 import org.eclipse.jgit.lib.Repository;
@@ -145,6 +147,31 @@
     }
   }
 
+  protected boolean isPushCompleted(Map<Project.NameKey, String> refsByProject, Duration timeOut) {
+    try {
+      WaitUtil.waitUntil(
+          () -> {
+            Iterator<Map.Entry<Project.NameKey, String>> iterator =
+                refsByProject.entrySet().iterator();
+            while (iterator.hasNext()) {
+              Map.Entry<Project.NameKey, String> entry = iterator.next();
+              try (Repository repo = repoManager.openRepository(entry.getKey())) {
+                if (checkedGetRef(repo, entry.getValue()) != null) {
+                  iterator.remove();
+                }
+              } catch (IOException e) {
+                throw new RuntimeException("Cannot open repo for project" + entry.getKey(), e);
+              }
+            }
+            return refsByProject.isEmpty();
+          },
+          timeOut);
+    } catch (InterruptedException e) {
+      return false;
+    }
+    return true;
+  }
+
   protected Ref checkedGetRef(Repository repo, String branchName) {
     try {
       return repo.getRefDatabase().exactRef(branchName);
diff --git a/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationStorageIT.java b/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationStorageIT.java
index 3b7bb3e..f6f3bbe 100644
--- a/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationStorageIT.java
+++ b/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationStorageIT.java
@@ -24,7 +24,9 @@
 import com.google.gerrit.reviewdb.client.Project;
 import com.googlesource.gerrit.plugins.replication.ReplicationTasksStorage.ReplicateRefUpdate;
 import java.util.Arrays;
+import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
 import java.util.regex.Pattern;
 import java.util.stream.Stream;
 import org.junit.Test;
@@ -153,15 +155,20 @@
 
     String changeRef1 = createChange().getPatchSet().getRefName();
     String changeRef2 = createChange().getPatchSet().getRefName();
+    Map<Project.NameKey, String> refsByProject = new HashMap<>();
+    refsByProject.put(target1, changeRef1);
+    refsByProject.put(target2, changeRef1);
+    refsByProject.put(target1, changeRef2);
+    refsByProject.put(target2, changeRef2);
 
     setReplicationDestination(remote1, suffix1, ALL_PROJECTS);
     setReplicationDestination(remote2, suffix2, ALL_PROJECTS);
     reloadConfig();
 
-    assertThat(isPushCompleted(target1, changeRef1, TEST_PUSH_TIMEOUT)).isEqualTo(true);
-    assertThat(isPushCompleted(target2, changeRef1, TEST_PUSH_TIMEOUT)).isEqualTo(true);
-    assertThat(isPushCompleted(target1, changeRef2, TEST_PUSH_TIMEOUT)).isEqualTo(true);
-    assertThat(isPushCompleted(target2, changeRef2, TEST_PUSH_TIMEOUT)).isEqualTo(true);
+    // Wait for completion within the time 2 pushes should take because each remote only has 1
+    // thread and needs to push 2 events
+    assertThat(isPushCompleted(refsByProject, TEST_PUSH_TIMEOUT.plus(TEST_PUSH_TIMEOUT)))
+        .isEqualTo(true);
   }
 
   @Test
diff --git a/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationTasksStorageMPTest.java b/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationTasksStorageMPTest.java
new file mode 100644
index 0000000..cc0ae04
--- /dev/null
+++ b/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationTasksStorageMPTest.java
@@ -0,0 +1,76 @@
+// Copyright (C) 2020 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.googlesource.gerrit.plugins.replication;
+
+import static org.junit.Assert.assertTrue;
+
+import com.google.common.jimfs.Configuration;
+import com.google.common.jimfs.Jimfs;
+import java.nio.file.FileSystem;
+import java.nio.file.Path;
+import org.eclipse.jgit.transport.URIish;
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+public class ReplicationTasksStorageMPTest {
+  protected static final String PROJECT = "myProject";
+  protected static final String REF = "myRef";
+  protected static final String REMOTE = "myDest";
+  protected static final URIish URISH =
+      ReplicationTasksStorageTest.getUrish("http://example.com/" + PROJECT + ".git");
+  protected static final ReplicationTasksStorage.ReplicateRefUpdate REF_UPDATE =
+      new ReplicationTasksStorage.ReplicateRefUpdate(PROJECT, REF, URISH, REMOTE);
+
+  protected ReplicationTasksStorage nodeA;
+  protected ReplicationTasksStorage nodeB;
+  protected ReplicationTasksStorage persistedView;
+  protected FileSystem fileSystem;
+  protected Path storageSite;
+
+  @Before
+  public void setUp() throws Exception {
+    fileSystem = Jimfs.newFileSystem(Configuration.unix());
+    storageSite = fileSystem.getPath("replication_site");
+    nodeA = new ReplicationTasksStorage(storageSite);
+    nodeB = new ReplicationTasksStorage(storageSite);
+    persistedView = new ReplicationTasksStorage(storageSite);
+  }
+
+  @After
+  public void tearDown() throws Exception {
+    persistedView = null;
+    nodeB = null;
+    nodeA = null;
+    storageSite = null;
+    fileSystem.close();
+  }
+
+  @Test
+  public void sameRefPersistedByOtherNodeIsDeduped() {
+    nodeA.persist(REF_UPDATE);
+
+    nodeB.persist(REF_UPDATE);
+    ReplicationTasksStorageTest.assertContainsExactly(persistedView, REF_UPDATE);
+  }
+
+  @Test
+  public void persistedRefCanBeCompletedByOtherNode() {
+    nodeA.persist(REF_UPDATE);
+
+    nodeB.delete(REF_UPDATE);
+    assertTrue(persistedView.list().isEmpty());
+  }
+}
diff --git a/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationTasksStorageTest.java b/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationTasksStorageTest.java
index 3ee85d7..fd02cf8 100644
--- a/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationTasksStorageTest.java
+++ b/src/test/java/com/googlesource/gerrit/plugins/replication/ReplicationTasksStorageTest.java
@@ -202,12 +202,12 @@
     assertThat(storage.list()).isEmpty();
   }
 
-  private void assertContainsExactly(
+  public static void assertContainsExactly(
       ReplicationTasksStorage tasksStorage, ReplicateRefUpdate update) {
     assertTrue(equals(tasksStorage.list().get(0), update));
   }
 
-  private boolean equals(ReplicateRefUpdate one, ReplicateRefUpdate two) {
+  private static boolean equals(ReplicateRefUpdate one, ReplicateRefUpdate two) {
     return (one == null && two == null)
         || (one != null
             && two != null