--- a/mobile/android/services/src/main/java/org/mozilla/gecko/sync/repositories/Server15RepositorySession.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/sync/repositories/Server15RepositorySession.java
@@ -21,16 +21,17 @@ public class Server15RepositorySession e
   protected final Server15Repository serverRepository;
   private BatchingUploader uploader;
   private final BatchingDownloader downloader;
 
   public Server15RepositorySession(Repository repository) {
     super(repository);
     this.serverRepository = (Server15Repository) repository;
     this.downloader = new BatchingDownloader(
+            this.delegateQueue,
             this.serverRepository.authHeaderProvider,
             Uri.parse(this.serverRepository.collectionURI().toString()),
             this.serverRepository.getSyncDeadline(),
             this.serverRepository.getAllowMultipleBatches(),
             this.serverRepository.getAllowHighWaterMark(),
             this.serverRepository.stateProvider,
             this);
   }

--- a/mobile/android/services/src/main/java/org/mozilla/gecko/sync/repositories/downloaders/BatchingDownloader.java
+++ b/mobile/android/services/src/main/java/org/mozilla/gecko/sync/repositories/downloaders/BatchingDownloader.java
@@ -68,26 +68,28 @@ public class BatchingDownloader {
 
     /* package-local */ final AuthHeaderProvider authHeaderProvider;
 
     // Used to track outstanding requests, so that we can abort them as needed.
     @VisibleForTesting
     protected final Set<SyncStorageCollectionRequest> pending = Collections.synchronizedSet(new HashSet<SyncStorageCollectionRequest>());
     /* @GuardedBy("this") */ private String lastModified;
 
-    private final ExecutorService taskQueue = Executors.newSingleThreadExecutor();
+    private final ExecutorService taskQueue;
 
     public BatchingDownloader(
+            ExecutorService taskQueue,
             AuthHeaderProvider authHeaderProvider,
             Uri baseCollectionUri,
             long fetchDeadline,
             boolean allowMultipleBatches,
             boolean keepTrackOfHighWaterMark,
             RepositoryStateProvider stateProvider,
             RepositorySession repositorySession) {
+        this.taskQueue = taskQueue;
         this.repositorySession = repositorySession;
         this.authHeaderProvider = authHeaderProvider;
         this.baseCollectionUri = baseCollectionUri;
         this.allowMultipleBatches = allowMultipleBatches;
         this.keepTrackOfHighWaterMark = keepTrackOfHighWaterMark;
         this.fetchDeadline = fetchDeadline;
         this.stateProvider = stateProvider;
     }
@@ -319,16 +321,20 @@ public class BatchingDownloader {
 
         runTaskOnQueue(new Runnable() {
             @Override
             public void run() {
                 Logger.debug(LOG_TAG, "Running onFetchFailed.");
                 fetchRecordsDelegate.onFetchFailed(ex);
             }
         });
+
+        // Side-effect of calling this is an orderly shutdown of our task queue. It will process the
+        // above runnable, but won't accept any more work.
+        this.repositorySession.abort();
     }
 
     public void onFetchedRecord(CryptoRecord record,
                                 RepositorySessionFetchRecordsDelegate fetchRecordsDelegate) {
         try {
             fetchRecordsDelegate.onFetchedRecord(record);
             // NB: changes to stateProvider are committed in either onFetchCompleted or handleFetchFailed.
             if (this.keepTrackOfHighWaterMark) {
@@ -344,17 +350,16 @@ public class BatchingDownloader {
         if (request == null) {
             return;
         }
         this.pending.remove(request);
     }
 
     @VisibleForTesting
     protected void abortRequests() {
-        this.repositorySession.abort();
         synchronized (this.pending) {
             for (SyncStorageCollectionRequest request : this.pending) {
                 request.abort();
             }
             this.pending.clear();
         }
     }
 

--- a/mobile/android/services/src/test/java/org/mozilla/gecko/sync/repositories/downloaders/BatchingDownloaderDelegateTest.java
+++ b/mobile/android/services/src/test/java/org/mozilla/gecko/sync/repositories/downloaders/BatchingDownloaderDelegateTest.java
@@ -23,16 +23,17 @@ import org.mozilla.gecko.sync.repositori
 import org.mozilla.gecko.sync.repositories.RepositorySession;
 import org.mozilla.gecko.sync.repositories.Server15RepositorySession;
 import org.mozilla.gecko.sync.repositories.Server15Repository;
 import org.mozilla.gecko.sync.repositories.delegates.RepositorySessionFetchRecordsDelegate;
 import org.mozilla.gecko.sync.repositories.domain.Record;
 
 import java.net.URI;
 import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
 import java.util.concurrent.TimeUnit;
 
 import ch.boye.httpclientandroidlib.ProtocolVersion;
 import ch.boye.httpclientandroidlib.client.ClientProtocolException;
 import ch.boye.httpclientandroidlib.message.BasicHttpResponse;
 import ch.boye.httpclientandroidlib.message.BasicStatusLine;
 
 import static org.junit.Assert.*;
@@ -47,16 +48,17 @@ public class BatchingDownloaderDelegateT
         public boolean isSuccess = false;
         public boolean isFetched = false;
         public boolean isFailure = false;
         public Exception ex;
 
         public MockDownloader(RepositorySession repositorySession) {
             super(
                     null,
+                    null,
                     Uri.EMPTY,
                     SystemClock.elapsedRealtime() + TimeUnit.MINUTES.toMillis(30),
                     true,
                     true,
                     new NonPersistentRepositoryStateProvider(),
                     repositorySession
             );
         }
@@ -123,16 +125,17 @@ public class BatchingDownloaderDelegateT
                 new NonPersistentRepositoryStateProvider())
         );
         mockDownloader = new MockDownloader(repositorySession);
     }
 
     @Test
     public void testIfUnmodifiedSince() throws Exception {
         BatchingDownloader downloader = new BatchingDownloader(
+                Executors.newSingleThreadExecutor(),
                 null,
                 Uri.EMPTY,
                 SystemClock.elapsedRealtime() + TimeUnit.MINUTES.toMillis(30),
                 true,
                 true,
                 new NonPersistentRepositoryStateProvider(),
                 repositorySession
         );

--- a/mobile/android/services/src/test/java/org/mozilla/gecko/sync/repositories/downloaders/BatchingDownloaderTest.java
+++ b/mobile/android/services/src/test/java/org/mozilla/gecko/sync/repositories/downloaders/BatchingDownloaderTest.java
@@ -33,16 +33,17 @@ import org.mozilla.gecko.sync.repositori
 
 import java.io.UnsupportedEncodingException;
 import java.net.URI;
 import java.net.URISyntaxException;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.Map;
 import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
 import java.util.concurrent.TimeUnit;
 import java.util.concurrent.atomic.AtomicInteger;
 
 import ch.boye.httpclientandroidlib.ProtocolVersion;
 import ch.boye.httpclientandroidlib.message.BasicHttpResponse;
 import ch.boye.httpclientandroidlib.message.BasicStatusLine;
 
 import static org.junit.Assert.*;
@@ -171,17 +172,17 @@ public class BatchingDownloaderTest {
         public long limit;
         public boolean full;
         public String sort;
         public String ids;
         public String offset;
         public boolean abort;
 
         MockDownloader(RepositorySession repositorySession, boolean allowMultipleBatches, boolean keepTrackOfHighWaterMark, RepositoryStateProvider repositoryStateProvider) {
-            super(null, Uri.EMPTY, SystemClock.elapsedRealtime() + TimeUnit.MINUTES.toMillis(30),
+            super(null, null, Uri.EMPTY, SystemClock.elapsedRealtime() + TimeUnit.MINUTES.toMillis(30),
                     allowMultipleBatches, keepTrackOfHighWaterMark, repositoryStateProvider, repositorySession);
         }
 
         @Override
         public void fetchWithParameters(long newer,
                                  long batchLimit,
                                  boolean full,
                                  String sort,
@@ -541,20 +542,20 @@ public class BatchingDownloaderTest {
         mockDownloader.onFetchedRecord(record, sessionFetchRecordsDelegate);
         assertNull(repositoryStateProvider.getShadowedLong(RepositoryStateProvider.KEY_HIGH_WATER_MARK));
     }
 
     @Test
     public void testAbortRequests() {
         MockRepositorySession mockRepositorySession = new MockRepositorySession(serverRepository);
         BatchingDownloader downloader = new BatchingDownloader(
-                null, Uri.EMPTY, SystemClock.elapsedRealtime() + TimeUnit.MINUTES.toMillis(30),
+                Executors.newSingleThreadExecutor(), null, Uri.EMPTY, SystemClock.elapsedRealtime() + TimeUnit.MINUTES.toMillis(30),
                 true, true, new NonPersistentRepositoryStateProvider(), mockRepositorySession);
         assertFalse(mockRepositorySession.abort);
-        downloader.abortRequests();
+        downloader.handleFetchFailed(sessionFetchRecordsDelegate, null, null);
         assertTrue(mockRepositorySession.abort);
     }
 
     @Test
     public void testBuildCollectionURI() {
         try {
             assertEquals("?full=1&newer=5000.000", BatchingDownloader.buildCollectionURI(Uri.EMPTY, true, 5000000L, -1, null, null, null).toString());
             assertEquals("?newer=1230.000", BatchingDownloader.buildCollectionURI(Uri.EMPTY, false, 1230000L, -1, null, null, null).toString());