diff --git a/services/core/java/com/android/server/am/ActivityManagerService.java b/services/core/java/com/android/server/am/ActivityManagerService.java
index a2f5c15..fe25a17 100644
--- a/services/core/java/com/android/server/am/ActivityManagerService.java
+++ b/services/core/java/com/android/server/am/ActivityManagerService.java
@@ -15464,6 +15464,9 @@
                                         removeUriPermissionsForPackageLocked(ssp, userId, true);
 
                                         removeTasksByPackageNameLocked(ssp, userId);
+                                        if (userId == UserHandle.USER_OWNER) {
+                                            mTaskPersister.removeFromPackageCache(ssp);
+                                        }
                                     }
                                 } else {
                                     removeTasksByRemovedPackageComponentsLocked(ssp, userId);
diff --git a/services/core/java/com/android/server/am/ActivityRecord.java b/services/core/java/com/android/server/am/ActivityRecord.java
index cb693dd..af6a314 100755
--- a/services/core/java/com/android/server/am/ActivityRecord.java
+++ b/services/core/java/com/android/server/am/ActivityRecord.java
@@ -81,7 +81,7 @@
     private static final String ATTR_USERID = "user_id";
     private static final String TAG_PERSISTABLEBUNDLE = "persistable_bundle";
     private static final String ATTR_LAUNCHEDFROMUID = "launched_from_uid";
-    private static final String ATTR_LAUNCHEDFROMPACKAGE = "launched_from_package";
+    static final String ATTR_LAUNCHEDFROMPACKAGE = "launched_from_package";
     private static final String ATTR_RESOLVEDTYPE = "resolved_type";
     private static final String ATTR_COMPONENTSPECIFIED = "component_specified";
     static final String ACTIVITY_ICON_SUFFIX = "_activity_icon_";
@@ -90,7 +90,7 @@
     final IApplicationToken.Stub appToken; // window manager token
     final ActivityInfo info; // all about me
     final ApplicationInfo appInfo; // information about activity's app
-    final int launchedFromUid; // always the uid who started the activity.
+    int launchedFromUid; // always the uid who started the activity.
     final String launchedFromPackage; // always the package who started the activity.
     final int userId;          // Which user is this running for?
     final Intent intent;    // the original intent that generated us
@@ -1141,8 +1141,8 @@
         }
     }
 
-    static ActivityRecord restoreFromXml(XmlPullParser in,
-            ActivityStackSupervisor stackSupervisor) throws IOException, XmlPullParserException {
+    static ActivityRecord restoreFromXml(XmlPullParser in, ActivityStackSupervisor stackSupervisor)
+            throws IOException, XmlPullParserException {
         Intent intent = null;
         PersistableBundle persistentState = null;
         int launchedFromUid = 0;
diff --git a/services/core/java/com/android/server/am/TaskPersister.java b/services/core/java/com/android/server/am/TaskPersister.java
index 9ac1a24..318cd45 100644
--- a/services/core/java/com/android/server/am/TaskPersister.java
+++ b/services/core/java/com/android/server/am/TaskPersister.java
@@ -133,6 +133,8 @@
     // Data organization: <packageNameOfAffiliateTask, listOfAffiliatedTasksChains>
     private ArrayMap<String, List<List<OtherDeviceTask>>> mOtherDeviceTasksMap =
                 new ArrayMap<>(10);
+    // Local cache of package names to uid used when restoring a task from another device.
+    private ArrayMap<String, Integer> mPackageUidMap;
 
     // The next time in milliseconds we will remove expired task from
     // {@link #mOtherDeviceTasksMap} and disk. Set to {@link Long.MAX_VALUE} to never clean-up
@@ -583,7 +585,12 @@
     private void removeExpiredTasksIfNeeded() {
         synchronized (mOtherDeviceTasksMap) {
             final long now = System.currentTimeMillis();
-            if (mOtherDeviceTasksMap.isEmpty() || now < mExpiredTasksCleanupTime) {
+            final boolean noMoreTasks = mOtherDeviceTasksMap.isEmpty();
+            if (noMoreTasks || now < mExpiredTasksCleanupTime) {
+                if (noMoreTasks && mPackageUidMap != null) {
+                    // All done! package->uid map no longer needed.
+                    mPackageUidMap = null;
+                }
                 return;
             }
 
@@ -636,6 +643,20 @@
                 if (DEBUG_RESTORER) Slog.d(TAG, "Reset expiration time to "
                             + DateUtils.formatDateTime(mService.mContext, mExpiredTasksCleanupTime,
                             DateUtils.FORMAT_SHOW_DATE | DateUtils.FORMAT_SHOW_TIME));
+            } else {
+                // All done! package->uid map no longer needed.
+                mPackageUidMap = null;
+            }
+        }
+    }
+
+    /**
+     * Removes the input package name from the local package->uid map.
+     */
+    void removeFromPackageCache(String packageName) {
+        synchronized (mOtherDeviceTasksMap) {
+            if (mPackageUidMap != null) {
+                mPackageUidMap.remove(packageName);
             }
         }
     }
@@ -781,6 +802,27 @@
                             task.mAffiliatedTaskId = INVALID_TASK_ID;
                             task.mPrevAffiliateTaskId = INVALID_TASK_ID;
                             task.mNextAffiliateTaskId = INVALID_TASK_ID;
+                            // Set up uids valid for this device.
+                            Integer uid = mPackageUidMap.get(task.realActivity.getPackageName());
+                            if (uid == null) {
+                                // How did this happen???
+                                Slog.wtf(TAG, "Can't find uid for task=" + task
+                                        + " in mPackageUidMap=" + mPackageUidMap);
+                                return null;
+                            }
+                            task.effectiveUid = task.mCallingUid = uid;
+                            for (int i = task.mActivities.size() - 1; i >= 0; --i) {
+                                final ActivityRecord activity = task.mActivities.get(i);
+                                uid = mPackageUidMap.get(activity.launchedFromPackage);
+                                if (uid == null) {
+                                    // How did this happen??
+                                    Slog.wtf(TAG, "Can't find uid for activity=" + activity
+                                            + " in mPackageUidMap=" + mPackageUidMap);
+                                    return null;
+                                }
+                                activity.launchedFromUid = uid;
+                            }
+
                         } else {
                             Slog.e(TAG, "Unable to create task for backed-up file=" + file + ": "
                                         + fileToString(file));
@@ -804,42 +846,81 @@
 
     /**
      * Returns true if the input task chain backed-up from another device can be restored on this
-     * device.
+     * device. Also, sets the {@link OtherDeviceTask#mUid} on the input tasks if they can be
+     * restored.
      */
     private boolean canAddOtherDeviceTaskChain(List<OtherDeviceTask> chain) {
 
-        // Get component names of all the tasks in the chain.
-        // Mainly doing this to reduce checking for a component twice if two or more
-        // affiliations belong to the same component which is highly likely.
-        ArraySet<ComponentName> componentsToCheck = new ArraySet<>();
+        final ArraySet<ComponentName> validComponents = new ArraySet<>();
+        final IPackageManager pm = AppGlobals.getPackageManager();
         for (int i = 0; i < chain.size(); i++) {
 
             OtherDeviceTask task = chain.get(i);
             // Quick check, we can't add the task chain if any of its task files don't exist.
             if (!task.mFile.exists()) {
-                if (DEBUG_RESTORER)
-                        Slog.d(TAG, "Can't add chain due to missing file=" + task.mFile);
+                if (DEBUG_RESTORER) Slog.d(TAG,
+                        "Can't add chain due to missing file=" + task.mFile);
                 return false;
             }
-            componentsToCheck.add(task.mComponentName);
+
+            // Verify task package is installed.
+            if (!isPackageInstalled(task.mComponentName.getPackageName())) {
+                return false;
+            }
+            // Verify that all the launch packages are installed.
+            if (task.mLaunchPackages != null) {
+                for (int j = task.mLaunchPackages.size() - 1; j >= 0; --j) {
+                    if (!isPackageInstalled(task.mLaunchPackages.valueAt(j))) {
+                        return false;
+                    }
+                }
+            }
+
+            if (validComponents.contains(task.mComponentName)) {
+                // Existance of component has already been verified.
+                continue;
+            }
+
+            // Check to see if the specific component is installed.
+            try {
+                if (pm.getActivityInfo(task.mComponentName, 0, UserHandle.USER_OWNER) == null) {
+                    // Component isn't installed...
+                    return false;
+                }
+                validComponents.add(task.mComponentName);
+            } catch (RemoteException e) {
+                // Should not happen???
+                return false;
+            }
         }
 
-        boolean canAdd = true;
+        return true;
+    }
+
+    /**
+     * Returns true if the input package name is installed. If the package is installed, an entry
+     * for the package is added to {@link #mPackageUidMap}.
+     */
+    private boolean isPackageInstalled(final String packageName) {
+        if (mPackageUidMap != null && mPackageUidMap.containsKey(packageName)) {
+            return true;
+        }
         try {
-            // Check to see if all the components for this task chain are installed.
-            final IPackageManager pm = AppGlobals.getPackageManager();
-            for (int i = 0; canAdd && i < componentsToCheck.size(); i++) {
-                ComponentName cn = componentsToCheck.valueAt(i);
-                canAdd &= pm.getActivityInfo(cn, 0, UserHandle.USER_OWNER) != null;
-                if (DEBUG_RESTORER) Slog.d(TAG, "ComponentName=" + cn + " installed=" + canAdd);
+            int uid = AppGlobals.getPackageManager().getPackageUid(
+                    packageName, UserHandle.USER_OWNER);
+            if (uid == -1) {
+                // package doesn't exist...
+                return false;
             }
+            if (mPackageUidMap == null) {
+                mPackageUidMap = new ArrayMap<>();
+            }
+            mPackageUidMap.put(packageName, uid);
+            return true;
         } catch (RemoteException e) {
             // Should not happen???
-            canAdd = false;
+            return false;
         }
-
-        if (DEBUG_RESTORER) Slog.d(TAG, "canAdd=" + canAdd);
-        return canAdd;
     }
 
     private class LazyTaskWriterThread extends Thread {
@@ -995,12 +1076,17 @@
         final int mTaskId;
         final int mAffiliatedTaskId;
 
-        private OtherDeviceTask(
-                File file, ComponentName componentName, int taskId, int affiliatedTaskId) {
+        // Names of packages that launched activities in this task. All packages listed here need
+        // to be installed on the current device in order for the task to be restored successfully.
+        final ArraySet<String> mLaunchPackages;
+
+        private OtherDeviceTask(File file, ComponentName componentName, int taskId,
+                int affiliatedTaskId, ArraySet<String> launchPackages) {
             mFile = file;
             mComponentName = componentName;
             mTaskId = taskId;
             mAffiliatedTaskId = (affiliatedTaskId == INVALID_TASK_ID) ? taskId: affiliatedTaskId;
+            mLaunchPackages = launchPackages;
         }
 
         @Override
@@ -1038,6 +1124,7 @@
                     final String name = in.getName();
 
                     if (TAG_TASK.equals(name)) {
+                        final int outerDepth = in.getDepth();
                         ComponentName componentName = null;
                         int taskId = INVALID_TASK_ID;
                         int taskAffiliation = INVALID_TASK_ID;
@@ -1058,10 +1145,31 @@
                                     + " taskId=" + taskId + " file=" + file);
                             return null;
                         }
+
+                        ArraySet<String> launchPackages = null;
+                        while (((event = in.next()) != XmlPullParser.END_DOCUMENT) &&
+                                (event != XmlPullParser.END_TAG || in.getDepth() < outerDepth)) {
+                            if (event == XmlPullParser.START_TAG) {
+                                if (TaskRecord.TAG_ACTIVITY.equals(in.getName())) {
+                                    for (int j = in.getAttributeCount() - 1; j >= 0; --j) {
+                                        if (ActivityRecord.ATTR_LAUNCHEDFROMPACKAGE.equals(
+                                                in.getAttributeName(j))) {
+                                            if (launchPackages == null) {
+                                                launchPackages = new ArraySet();
+                                            }
+                                            launchPackages.add(in.getAttributeValue(j));
+                                        }
+                                    }
+                                } else {
+                                    XmlUtils.skipCurrentTag(in);
+                                }
+                            }
+                        }
                         if (DEBUG_RESTORER) Slog.d(TAG, "creating OtherDeviceTask from file="
                                 + file.getName() + " componentName=" + componentName
-                                + " taskId=" + taskId);
-                        return new OtherDeviceTask(file, componentName, taskId, taskAffiliation);
+                                + " taskId=" + taskId + " launchPackages=" + launchPackages);
+                        return new OtherDeviceTask(file, componentName, taskId,
+                                taskAffiliation, launchPackages);
                     } else {
                         Slog.wtf(TAG,
                                 "createFromFile: Unknown xml event=" + event + " name=" + name);
diff --git a/services/core/java/com/android/server/am/TaskRecord.java b/services/core/java/com/android/server/am/TaskRecord.java
index 21302b2..3011148 100644
--- a/services/core/java/com/android/server/am/TaskRecord.java
+++ b/services/core/java/com/android/server/am/TaskRecord.java
@@ -59,7 +59,7 @@
     private static final String TAG_AFFINITYINTENT = "affinity_intent";
     static final String ATTR_REALACTIVITY = "real_activity";
     private static final String ATTR_ORIGACTIVITY = "orig_activity";
-    private static final String TAG_ACTIVITY = "activity";
+    static final String TAG_ACTIVITY = "activity";
     private static final String ATTR_AFFINITY = "affinity";
     private static final String ATTR_ROOT_AFFINITY = "root_affinity";
     private static final String ATTR_ROOTHASRESET = "root_has_reset";