       (is (str/includes? set-cookie "HttpOnly=true"))
       (is (= (System/getProperty "user.name") (str body))))))
 
-; Marked explicit due to:
-;   FAIL in (test-killed-instances)
-;   Not intersection between used and killed instances!
-;   expected: (not-empty (set/intersection all-instance-ids killed-instance-ids))
-;     actual: (not (not-empty #{}))
-(deftest ^:parallel ^:integration-slow ^:explicit test-killed-instances
+(deftest ^:parallel ^:integration-slow test-killed-instances
   (testing-using-waiter-url
     (let [headers {:x-waiter-name (rand-name)
-                   :x-waiter-max-instances 6
+                   :x-waiter-max-instances 5
                    :x-waiter-scale-up-factor 0.99
-                   :x-waiter-scale-down-factor 0.85
+                   :x-waiter-scale-down-factor 0.99
                    :x-kitchen-delay-ms 5000}
           _ (log/info "making canary request...")
           {:keys [service-id]} (make-request-with-debug-info headers #(make-kitchen-request waiter-url %))
           request-fn (fn [] (->> #(make-kitchen-request waiter-url %)
                                  (make-request-with-debug-info headers)
-                                 (:instance-id)))
-          _ (log/info "starting parallel requests")
-          all-instance-ids (->> request-fn
-                                (parallelize-requests 12 5)
-                                (set))
-          _ (parallelize-requests 1 5 request-fn)]
-      (log/info "waiting for at least one instance to get killed")
-      (is (wait-for #(let [service-settings (service-settings waiter-url service-id)
-                           killed-instance-ids (->> (get-in service-settings [:instances :killed-instances])
-                                                    (map :id)
-                                                    (set))]
-                       (pos? (count killed-instance-ids)))
-                    :interval 2 :timeout 30)
-          (str "No killed instances found for " service-id))
-      (let [service-settings (service-settings waiter-url service-id)
-            killed-instance-ids (->> (get-in service-settings [:instances :killed-instances]) (map :id) (set))]
-        (log/info "used instances (" (count all-instance-ids) "):" all-instance-ids)
-        (log/info "killed instances (" (count killed-instance-ids) "):" killed-instance-ids)
-        (is (not-empty (set/intersection all-instance-ids killed-instance-ids))
-            "Not intersection between used and killed instances!"))
-      (delete-service waiter-url service-id))))
+                                 :instance-id))]
+      (with-service-cleanup
+        service-id
+        (log/info "starting parallel requests")
+        (let [instance-ids-atom (atom #{})
+              instance-request-fn (fn []
+                                    (let [instance-id (request-fn)]
+                                      (swap! instance-ids-atom conj instance-id)))
+              instance-ids (->> (parallelize-requests 4 25 instance-request-fn
+                                                      :canceled? (fn [] (> (count @instance-ids-atom) 2))
+                                                      :service-id service-id)
+                                (reduce set/union))]
+          (is (> (count instance-ids) 1) (str instance-ids)))
+
+        (log/info "waiting for at least one instance to get killed")
+        (is (wait-for #(->> (get-in (service-settings waiter-url service-id) [:instances :killed-instances])
+                            (map :id)
+                            set
+                            seq)
+                      :interval 2 :timeout 45)
+            (str "No killed instances found for " service-id))))))
 
 (deftest ^:parallel ^:integration-fast test-basic-priority-support
   (testing-using-waiter-url

                (make-request waiter-url "/state" :headers {"origin" "badorigin.com"} :method :post)]
            (is (= 403 status) response))
          (let [{:keys [status] :as response}
                (make-request waiter-url "/state" :headers {"origin" "badorigin.com"} :method :options )]
            (is (= 403 status) response)))))))

(deftest ^:parallel ^:integration-fast test-error-handling

            [clojure.test :refer :all]
            [clojure.tools.logging :as log]
            [clojure.walk :as walk]
            [plumbing.core :as pc]
            [waiter.interstitial :as interstitial]
            [waiter.service-description :as sd]
            [waiter.util.client-tools :refer :all]
