diff --git a/AndroidManifest.xml b/AndroidManifest.xml
index 1621f8e..3d424e4 100644
--- a/AndroidManifest.xml
+++ b/AndroidManifest.xml
@@ -50,6 +50,9 @@
         <!-- This is used to keep the provider alive long enough to send update
              intent broadcasts. -->
         <service android:name=".EmptyService" />
+        <!-- This is used to keep the provider alive long enough to clean up scheduled
+             alarms after boot. -->
+        <service android:name=".CalendarReceiver$RemoveScheduledAlarmsEmptyService" />
 
         <activity android:name="CalendarContentProviderTests" android:label="Calendar Content Provider"
                 android:exported="false">
diff --git a/src/com/android/providers/calendar/CalendarAlarmManager.java b/src/com/android/providers/calendar/CalendarAlarmManager.java
index 3f4b53c..d917020 100644
--- a/src/com/android/providers/calendar/CalendarAlarmManager.java
+++ b/src/com/android/providers/calendar/CalendarAlarmManager.java
@@ -112,12 +112,6 @@
     @VisibleForTesting
     protected AtomicBoolean mNextAlarmCheckScheduled;
     /**
-     * Used for tracking if current alarms should be removed when recalculating
-     * new ones.
-     */
-    @VisibleForTesting
-    protected AtomicBoolean mNeedRemoveAlarms;
-    /**
      * Used for synchronization
      */
     @VisibleForTesting
@@ -139,14 +133,10 @@
         mContext = context;
         mAlarmManager = (AlarmManager) context.getSystemService(Context.ALARM_SERVICE);
         mNextAlarmCheckScheduled = new AtomicBoolean(false);
-        mNeedRemoveAlarms = new AtomicBoolean(false);
         mAlarmLock = new Object();
     }
 
     void scheduleNextAlarm(boolean removeAlarms) {
-        // We aggregate first the "remove alarm flag". Whenever it is to true,
-        // it will be sticky
-        mNeedRemoveAlarms.set(mNeedRemoveAlarms.get() || removeAlarms);
         if (!mNextAlarmCheckScheduled.getAndSet(true)) {
             if (Log.isLoggable(CalendarProvider2.TAG, Log.DEBUG)) {
                 Log.d(CalendarProvider2.TAG, "Scheduling check of next Alarm");
diff --git a/src/com/android/providers/calendar/CalendarReceiver.java b/src/com/android/providers/calendar/CalendarReceiver.java
index 2cd834a..48760dd 100644
--- a/src/com/android/providers/calendar/CalendarReceiver.java
+++ b/src/com/android/providers/calendar/CalendarReceiver.java
@@ -16,10 +16,13 @@
 
 package com.android.providers.calendar;
 
+import android.app.Service;
 import android.content.BroadcastReceiver;
 import android.content.ContentResolver;
 import android.content.Context;
 import android.content.Intent;
+import android.os.IBinder;
+import android.util.Log;
 
 /**
  * This IntentReceiver executes when the boot completes and ensures that
@@ -29,6 +32,7 @@
  * yet.
  */
 public class CalendarReceiver extends BroadcastReceiver {
+    private static final String TAG = "CalendarReceiver";
 
     static final String SCHEDULE = "com.android.providers.calendar.SCHEDULE_ALARM";
 
@@ -40,14 +44,62 @@
             cr.update(CalendarAlarmManager.SCHEDULE_ALARM_URI, null /* values */, null /* where */,
                     null /* selectionArgs */);
         } else if (action.equals(Intent.ACTION_BOOT_COMPLETED)) {
-            // Remove alarms from the CalendarAlerts table that have been marked
-            // as "scheduled" but not fired yet.  We do this because the
-            // AlarmManagerService loses all information about alarms when the
-            // power turns off but we store the information in a database table
-            // that persists across reboots. See the documentation for
-            // scheduleNextAlarmLocked() for more information.
-            cr.update(CalendarAlarmManager.SCHEDULE_ALARM_REMOVE_URI, null /* values */,
+            removeScheduledAlarms(context, cr);
+        }
+    }
+
+    /*
+     * Remove alarms from the CalendarAlerts table that have been marked
+     * as "scheduled" but not fired yet.  We do this because the
+     * AlarmManagerService loses all information about alarms when the
+     * power turns off but we store the information in a database table
+     * that persists across reboots. See the documentation for
+     * scheduleNextAlarmLocked() for more information.
+     *
+     * Running this on the main thread has caused ANRs, so we run it on a background
+     * thread and start an "empty service" to encourage the system to keep us alive.
+     *
+     * We don't expect this to be called more than once.  If it were, we would have to
+     * worry about serializing the use of the service.
+     */
+    private void removeScheduledAlarms(Context context, ContentResolver resolver) {
+        context.startService(new Intent(context, RemoveScheduledAlarmsEmptyService.class));
+
+        RemoveScheduledAlarmsThread thread = new RemoveScheduledAlarmsThread(context, resolver);
+        thread.start();
+    }
+
+    /**
+     * Background thread that handles cleanup of scheduled alarms.
+     */
+    private static class RemoveScheduledAlarmsThread extends Thread {
+        private Context mContext;
+        private ContentResolver mResolver;
+
+        RemoveScheduledAlarmsThread(Context context, ContentResolver resolver) {
+            mContext = context;
+            mResolver = resolver;
+        }
+
+        @Override
+        public void run() {
+            if (Log.isLoggable(TAG, Log.DEBUG)) {
+                Log.d(TAG, "Removing scheduled alarms");
+            }
+            mResolver.update(CalendarAlarmManager.SCHEDULE_ALARM_REMOVE_URI, null /* values */,
                     null /* where */, null /* selectionArgs */);
+            mContext.stopService(new Intent(mContext, RemoveScheduledAlarmsEmptyService.class));
+        }
+    }
+
+    /**
+     * Background {@link Service} that is used to keep our process alive long enough
+     * for background threads to finish.  Used for cleanup of scheduled alarms.
+     */
+    public static class RemoveScheduledAlarmsEmptyService extends Service {
+        @Override
+        public IBinder onBind(Intent intent) {
+            return null;
         }
     }
 }
diff --git a/tests/src/com/android/providers/calendar/CalendarProvider2ForTesting.java b/tests/src/com/android/providers/calendar/CalendarProvider2ForTesting.java
index 9c52207..9aa02bf 100644
--- a/tests/src/com/android/providers/calendar/CalendarProvider2ForTesting.java
+++ b/tests/src/com/android/providers/calendar/CalendarProvider2ForTesting.java
@@ -49,7 +49,6 @@
         protected void initializeWithContext(Context context) {
             mContext = context;
             mNextAlarmCheckScheduled = new AtomicBoolean(false);
-            mNeedRemoveAlarms = new AtomicBoolean(false);
             mAlarmLock = new Object();
         }