Index: trunk/src/org/openstreetmap/josm/actions/UploadSelectionAction.java
===================================================================
--- trunk/src/org/openstreetmap/josm/actions/UploadSelectionAction.java	(revision 15424)
+++ trunk/src/org/openstreetmap/josm/actions/UploadSelectionAction.java	(revision 15426)
@@ -68,5 +68,5 @@
             setEnabled(false);
         }
-        if (isEnabled() && selection.stream().noneMatch(OsmPrimitive::isModified)) {
+        if (isEnabled() && selection.parallelStream().noneMatch(OsmPrimitive::isModified)) {
             setEnabled(false);
         }
@@ -74,5 +74,5 @@
 
     protected Set<OsmPrimitive> getDeletedPrimitives(DataSet ds) {
-        return ds.allPrimitives().stream()
+        return ds.allPrimitives().parallelStream()
                 .filter(p -> p.isDeleted() && !p.isNew() && p.isVisible() && p.isModified())
                 .collect(Collectors.toSet());
@@ -80,5 +80,5 @@
 
     protected Set<OsmPrimitive> getModifiedPrimitives(Collection<OsmPrimitive> primitives) {
-        return primitives.stream()
+        return primitives.parallelStream()
                 .filter(p -> p.isNewOrUndeleted() || (p.isModified() && !p.isIncomplete()))
                 .collect(Collectors.toSet());
@@ -124,9 +124,5 @@
      */
     protected boolean hasPrimitivesToDelete(Collection<OsmPrimitive> primitives) {
-        for (OsmPrimitive p: primitives) {
-            if (p.isDeleted() && p.isModified() && !p.isNew())
-                return true;
-        }
-        return false;
+        return primitives.parallelStream().anyMatch(p -> p.isDeleted() && p.isModified() && !p.isNew());
     }
 
@@ -240,5 +236,5 @@
 
         /**
-         *
+         * Constructs a new {@code DeletedParentsChecker}.
          * @param layer the data layer for which a collection of selected primitives is uploaded
          * @param toUpload the collection of primitives to upload
@@ -278,5 +274,5 @@
          */
         protected Set<OsmPrimitive> getPrimitivesToCheckForParents() {
-            return toUpload.stream().filter(p -> p.isDeleted() && !p.isNewOrUndeleted()).collect(Collectors.toSet());
+            return toUpload.parallelStream().filter(p -> p.isDeleted() && !p.isNewOrUndeleted()).collect(Collectors.toSet());
         }
 
@@ -291,5 +287,5 @@
                     OsmPrimitive current = toCheck.pop();
                     synchronized (this) {
-                        reader = new OsmServerBackreferenceReader(current);
+                        reader = new OsmServerBackreferenceReader(current).setAllowIncompleteParentWays(true);
                     }
                     getProgressMonitor().subTask(tr("Reading parents of ''{0}''", current.getDisplayName(DefaultNameFormatter.getInstance())));
@@ -302,4 +298,5 @@
                     for (OsmPrimitive p: ds.allPrimitives()) {
                         if (canceled) return;
+                        if (p instanceof Node || (p instanceof Way && !(current instanceof Node))) continue;
                         OsmPrimitive myDeletedParent = layer.data.getPrimitiveById(p);
                         // our local dataset includes a deleted parent of a primitive we want
Index: trunk/src/org/openstreetmap/josm/io/OsmServerBackreferenceReader.java
===================================================================
--- trunk/src/org/openstreetmap/josm/io/OsmServerBackreferenceReader.java	(revision 15424)
+++ trunk/src/org/openstreetmap/josm/io/OsmServerBackreferenceReader.java	(revision 15426)
@@ -42,4 +42,6 @@
     /** true if this reader should complete incomplete primitives */
     private boolean readFull;
+    /** true if this reader should allow incomplete parent ways */
+    private boolean allowIncompleteParentWays;
 
     /**
@@ -113,10 +115,33 @@
 
     /**
-     * Set true if this reader should reads immediate children of referring primitives too. False, otherweise.
-     *
-     * @param readFull true if this reader should reads immediate children of referring primitives too. False, otherweise.
-     */
-    public void setReadFull(boolean readFull) {
+     * Set true if this reader should reads immediate children of referring primitives too. False, otherwise.
+     *
+     * @param readFull true if this reader should reads immediate children of referring primitives too. False, otherwise.
+     * @return {@code this}, for easy chaining
+     * @since 15426
+     */
+    public OsmServerBackreferenceReader setReadFull(boolean readFull) {
         this.readFull = readFull;
+        return this;
+    }
+
+    /**
+     * Determines if this reader allows to return incomplete parent ways of a node.
+     * @return {@code true} if this reader allows to return incomplete parent ways of a node
+     * @since 15426
+     */
+    public boolean isAllowIncompleteParentWays() {
+        return allowIncompleteParentWays;
+    }
+
+    /**
+     * Sets whether this reader allows to return incomplete parent ways of a node.
+     * @param allowIncompleteWays {@code true} if this reader allows to return incomplete parent ways of a node
+     * @return {@code this}, for easy chaining
+     * @since 15426
+     */
+    public OsmServerBackreferenceReader setAllowIncompleteParentWays(boolean allowIncompleteWays) {
+        this.allowIncompleteParentWays = allowIncompleteWays;
+        return this;
     }
 
@@ -175,5 +200,5 @@
      * <ul>
      *   <li>if this reader reads referers for a {@link org.openstreetmap.josm.data.osm.Node}, referring ways are always
-     *     read individually from the server</li>
+     *     read fully, unless {@link #setAllowIncompleteParentWays(boolean)} is set to true.</li>
      *   <li>if this reader reads referers for an {@link Way} or a {@link Relation}, referring relations
      *    are only read fully if {@link #setReadFull(boolean)} is set to true.</li>
@@ -191,5 +216,5 @@
         try {
             Collection<Way> waysToCheck = new ArrayList<>(ds.getWays());
-            if (isReadFull() || primitiveType == OsmPrimitiveType.NODE) {
+            if (isReadFull() || (primitiveType == OsmPrimitiveType.NODE && !isAllowIncompleteParentWays())) {
                 for (Way way: waysToCheck) {
                     if (!way.isNew() && way.hasIncompleteNodes()) {