diff --git a/resources/sql/autopatches/20140706.harbormasterdepend.1.php b/resources/sql/autopatches/20140706.harbormasterdepend.1.php
new file mode 100644
--- /dev/null
+++ b/resources/sql/autopatches/20140706.harbormasterdepend.1.php
@@ -0,0 +1,56 @@
+<?php
+
+$plan_table = new HarbormasterBuildPlan();
+$step_table = new HarbormasterBuildStep();
+$conn_w = $plan_table->establishConnection('w');
+foreach (new LiskMigrationIterator($plan_table) as $plan) {
+
+  echo pht(
+    "Migrating build plan %d: %s...\n",
+    $plan->getID(),
+    $plan->getName());
+
+  // Load all build steps in order using the step sequence.
+  $steps = queryfx_all(
+    $conn_w,
+    'SELECT id FROM %T WHERE buildPlanPHID = %s ORDER BY sequence ASC;',
+    $step_table->getTableName(),
+    $plan->getPHID());
+
+  $previous_step = null;
+  $sequence = 1;
+  foreach ($steps as $step) {
+    $id = $step['id'];
+
+    $loaded_step = id(new HarbormasterBuildStep())->load($id);
+
+    $depends_on = $loaded_step->getDetail('depends_on');
+    if ($depends_on !== null) {
+      // This plan already contains steps with depends_on set, so
+      // we skip since there's nothing to migrate.
+      break;
+    }
+
+    if ($previous_step === null) {
+      $depends_on = array();
+    } else {
+      $depends_on = array($previous_step->getPHID());
+    }
+
+    $loaded_step->setDetail('depends_on', $depends_on);
+    queryfx(
+      $conn_w,
+      'UPDATE %T SET details = %s WHERE id = %d',
+      $step_table->getTableName(),
+      json_encode($loaded_step->getDetails()),
+      $loaded_step->getID());
+
+    $previous_step = $loaded_step;
+
+    echo pht(
+      "  Migrated build step %d.\n",
+      $sequence);
+    $sequence++;
+  }
+
+}
diff --git a/src/__phutil_library_map__.php b/src/__phutil_library_map__.php
--- a/src/__phutil_library_map__.php
+++ b/src/__phutil_library_map__.php
@@ -5,7 +5,6 @@
  * @generated
  * @phutil-library-version 2
  */
-
 phutil_register_library_map(array(
   '__library_version__' => 2,
   'class' =>
@@ -722,6 +721,7 @@
     'HarbormasterBuildArtifactQuery' => 'applications/harbormaster/query/HarbormasterBuildArtifactQuery.php',
     'HarbormasterBuildCommand' => 'applications/harbormaster/storage/HarbormasterBuildCommand.php',
     'HarbormasterBuildEngine' => 'applications/harbormaster/engine/HarbormasterBuildEngine.php',
+    'HarbormasterBuildGraph' => 'applications/harbormaster/engine/HarbormasterBuildGraph.php',
     'HarbormasterBuildItem' => 'applications/harbormaster/storage/build/HarbormasterBuildItem.php',
     'HarbormasterBuildItemQuery' => 'applications/harbormaster/query/HarbormasterBuildItemQuery.php',
     'HarbormasterBuildLog' => 'applications/harbormaster/storage/build/HarbormasterBuildLog.php',
@@ -782,7 +782,6 @@
     'HarbormasterPlanDisableController' => 'applications/harbormaster/controller/HarbormasterPlanDisableController.php',
     'HarbormasterPlanEditController' => 'applications/harbormaster/controller/HarbormasterPlanEditController.php',
     'HarbormasterPlanListController' => 'applications/harbormaster/controller/HarbormasterPlanListController.php',
-    'HarbormasterPlanOrderController' => 'applications/harbormaster/controller/HarbormasterPlanOrderController.php',
     'HarbormasterPlanRunController' => 'applications/harbormaster/controller/HarbormasterPlanRunController.php',
     'HarbormasterPlanViewController' => 'applications/harbormaster/controller/HarbormasterPlanViewController.php',
     'HarbormasterPublishFragmentBuildStepImplementation' => 'applications/harbormaster/step/HarbormasterPublishFragmentBuildStepImplementation.php',
@@ -3447,6 +3446,7 @@
     'HarbormasterBuildArtifactQuery' => 'PhabricatorCursorPagedPolicyAwareQuery',
     'HarbormasterBuildCommand' => 'HarbormasterDAO',
     'HarbormasterBuildEngine' => 'Phobject',
+    'HarbormasterBuildGraph' => 'AbstractDirectedGraph',
     'HarbormasterBuildItem' => 'HarbormasterDAO',
     'HarbormasterBuildItemQuery' => 'PhabricatorCursorPagedPolicyAwareQuery',
     'HarbormasterBuildLog' =>
@@ -3536,7 +3536,6 @@
     'HarbormasterPlanDisableController' => 'HarbormasterPlanController',
     'HarbormasterPlanEditController' => 'HarbormasterPlanController',
     'HarbormasterPlanListController' => 'HarbormasterPlanController',
-    'HarbormasterPlanOrderController' => 'HarbormasterController',
     'HarbormasterPlanRunController' => 'HarbormasterController',
     'HarbormasterPlanViewController' => 'HarbormasterPlanController',
     'HarbormasterPublishFragmentBuildStepImplementation' => 'HarbormasterBuildStepImplementation',
diff --git a/src/applications/harbormaster/controller/HarbormasterBuildableViewController.php b/src/applications/harbormaster/controller/HarbormasterBuildableViewController.php
--- a/src/applications/harbormaster/controller/HarbormasterBuildableViewController.php
+++ b/src/applications/harbormaster/controller/HarbormasterBuildableViewController.php
@@ -179,29 +179,7 @@
         ->setHref($view_uri);
 
       $status = $build->getBuildStatus();
-      switch ($status) {
-        case HarbormasterBuild::STATUS_INACTIVE:
-          $item->setBarColor('grey');
-          break;
-        case HarbormasterBuild::STATUS_PENDING:
-          $item->setBarColor('blue');
-          break;
-        case HarbormasterBuild::STATUS_BUILDING:
-          $item->setBarColor('yellow');
-          break;
-        case HarbormasterBuild::STATUS_PASSED:
-          $item->setBarColor('green');
-          break;
-        case HarbormasterBuild::STATUS_FAILED:
-          $item->setBarColor('red');
-          break;
-        case HarbormasterBuild::STATUS_ERROR:
-          $item->setBarColor('red');
-          break;
-        case HarbormasterBuild::STATUS_STOPPED:
-          $item->setBarColor('black');
-          break;
-      }
+      $item->setBarColor(HarbormasterBuild::getBuildStatusColor($status));
 
       $item->addAttribute(HarbormasterBuild::getBuildStatusName($status));
 
diff --git a/src/applications/harbormaster/controller/HarbormasterPlanOrderController.php b/src/applications/harbormaster/controller/HarbormasterPlanOrderController.php
deleted file mode 100644
--- a/src/applications/harbormaster/controller/HarbormasterPlanOrderController.php
+++ /dev/null
@@ -1,53 +0,0 @@
-<?php
-
-final class HarbormasterPlanOrderController extends HarbormasterController {
-
-  private $id;
-
-  public function willProcessRequest(array $data) {
-    $this->id = idx($data, 'id');
-  }
-
-  public function processRequest() {
-    $request = $this->getRequest();
-    $user = $request->getUser();
-
-    $request->validateCSRF();
-
-    $this->requireApplicationCapability(
-      HarbormasterCapabilityManagePlans::CAPABILITY);
-
-    $plan = id(new HarbormasterBuildPlanQuery())
-      ->setViewer($user)
-      ->withIDs(array($this->id))
-      ->executeOne();
-    if (!$plan) {
-      return new Aphront404Response();
-    }
-
-    // Load all steps.
-    $order = $request->getStrList('order');
-    $steps = id(new HarbormasterBuildStepQuery())
-      ->setViewer($user)
-      ->withIDs($order)
-      ->execute();
-    $steps = array_select_keys($steps, $order);
-    $reordered_steps = array();
-
-    // Apply sequences.
-    $sequence = 1;
-    foreach ($steps as $step) {
-      $step->setSequence($sequence++);
-      $step->save();
-
-      $reordered_steps[] = $step;
-    }
-
-    // NOTE: Reordering steps may invalidate artifacts. This is fine; the UI
-    // will show that there are ordering issues.
-
-    // Force the page to re-render.
-    return id(new AphrontRedirectResponse());
-  }
-
-}
diff --git a/src/applications/harbormaster/controller/HarbormasterPlanViewController.php b/src/applications/harbormaster/controller/HarbormasterPlanViewController.php
--- a/src/applications/harbormaster/controller/HarbormasterPlanViewController.php
+++ b/src/applications/harbormaster/controller/HarbormasterPlanViewController.php
@@ -50,9 +50,21 @@
     $crumbs = $this->buildApplicationCrumbs();
     $crumbs->addTextCrumb(pht('Plan %d', $id));
 
-    list($step_list, $has_any_conflicts) = $this->buildStepList($plan);
+    list($step_list, $has_any_conflicts, $would_deadlock) =
+      $this->buildStepList($plan);
 
-    if ($has_any_conflicts) {
+    if ($would_deadlock) {
+      $box->setFormErrors(
+        array(
+          pht(
+            'This build plan will deadlock when executed, due to '.
+            'circular dependencies present in the build plan. '.
+            'Examine the step list and resolve the deadlock.'),
+        ));
+    } else if ($has_any_conflicts) {
+      // A deadlocking build will also cause all the artifacts to be
+      // invalid, so we just skip showing this message if that's the
+      // case.
       $box->setFormErrors(
         array(
           pht(
@@ -77,138 +89,180 @@
     $request = $this->getRequest();
     $viewer = $request->getUser();
 
-    $list_id = celerity_generate_unique_node_id();
+    list($run_order, $would_deadlock) = 
+      HarbormasterBuildGraph::determineDependencyExecution($plan);
 
     $steps = id(new HarbormasterBuildStepQuery())
       ->setViewer($viewer)
       ->withBuildPlanPHIDs(array($plan->getPHID()))
       ->execute();
+    $steps = mpull($steps, null, 'getPHID');
+
+    $first_to_deadlock = null;
+    if ($would_deadlock) {
+      // Add all of the remaining steps that couldn't be calculated to
+      // a final row in the run order so that they will still be rendered.
+      // Keep track of the first step placed in the list, so we know when
+      // we've switched to deadlocked steps when rendering.
+      $final_row = array();
+      foreach ($steps as $step) {
+        $present_in_run_order = false;
+        foreach ($run_order as $run_row) {
+          foreach ($run_row as $run_step) {
+            if ($run_step->getPHID() === $step->getPHID()) {
+              $present_in_run_order = true;
+              break;
+            }
+          }
+
+          if ($present_in_run_order) {
+            break;
+          }
+        }
+
+        if ($present_in_run_order) {
+          continue;
+        }
+
+        if ($first_to_deadlock === null) {
+          $first_to_deadlock = $step->getPHID();
+        }
+
+        $final_row[] = $step;
+      }
+
+      $run_order[] = $final_row;
+    }
 
     $can_edit = $this->hasApplicationCapability(
       HarbormasterCapabilityManagePlans::CAPABILITY);
 
-    $i = 1;
     $step_list = id(new PHUIObjectItemListView())
       ->setUser($viewer)
       ->setNoDataString(
-        pht('This build plan does not have any build steps yet.'))
-      ->setID($list_id);
-    Javelin::initBehavior(
-      'harbormaster-reorder-steps',
-      array(
-        'listID' => $list_id,
-        'orderURI' => '/harbormaster/plan/order/'.$plan->getID().'/',
-      ));
+        pht('This build plan does not have any build steps yet.'));
 
+    $i = 0;
     $has_any_conflicts = false;
-    foreach ($steps as $step) {
-      $implementation = null;
-      try {
-        $implementation = $step->getStepImplementation();
-      } catch (Exception $ex) {
-        // We can't initialize the implementation.  This might be because
-        // it's been renamed or no longer exists.
+    $is_deadlocking = false;
+    foreach ($run_order as $run_row) {
+      $i++;
+      $a = 1;
+      foreach ($run_row as $run_ref) {
+        $step = $steps[$run_ref->getPHID()];
+
+        $implementation = null;
+        try {
+          $implementation = $step->getStepImplementation();
+        } catch (Exception $ex) {
+          // We can't initialize the implementation.  This might be because
+          // it's been renamed or no longer exists.
+          $item = id(new PHUIObjectItemView())
+            ->setObjectName(pht('Step %d.%d', $i, $a++))
+            ->setHeader(pht('Unknown Implementation'))
+            ->setBarColor('red')
+            ->addAttribute(pht(
+              'This step has an invalid implementation (%s).',
+              $step->getClassName()))
+            ->addAction(
+              id(new PHUIListItemView())
+                ->setIcon('fa-times')
+                ->addSigil('harbormaster-build-step-delete')
+                ->setWorkflow(true)
+                ->setRenderNameAsTooltip(true)
+                ->setName(pht('Delete'))
+                ->setHref(
+                  $this->getApplicationURI('step/delete/'.$step->getID().'/')));
+          $step_list->addItem($item);
+          continue;
+        }
         $item = id(new PHUIObjectItemView())
-          ->setObjectName(pht('Step %d', $i++))
-          ->setHeader(pht('Unknown Implementation'))
-          ->setBarColor('red')
-          ->addAttribute(pht(
-            'This step has an invalid implementation (%s).',
-            $step->getClassName()))
+          ->setObjectName(pht('Step %d.%d', $i, $a++))
+          ->setHeader($step->getName());
+
+        $item->addAttribute($implementation->getDescription());
+
+        $step_id = $step->getID();
+        $edit_uri = $this->getApplicationURI("step/edit/{$step_id}/");
+        $delete_uri = $this->getApplicationURI("step/delete/{$step_id}/");
+
+        if ($can_edit) {
+          $item->setHref($edit_uri);
+        }
+
+        $item
+          ->setHref($edit_uri)
           ->addAction(
             id(new PHUIListItemView())
               ->setIcon('fa-times')
               ->addSigil('harbormaster-build-step-delete')
               ->setWorkflow(true)
-              ->setRenderNameAsTooltip(true)
-              ->setName(pht('Delete'))
+              ->setDisabled(!$can_edit)
               ->setHref(
                 $this->getApplicationURI('step/delete/'.$step->getID().'/')));
-        $step_list->addItem($item);
-        continue;
-      }
-      $item = id(new PHUIObjectItemView())
-        ->setObjectName('Step '.$i++)
-        ->setHeader($step->getName());
-
-      $item->addAttribute($implementation->getDescription());
-
-      $step_id = $step->getID();
-      $edit_uri = $this->getApplicationURI("step/edit/{$step_id}/");
-      $delete_uri = $this->getApplicationURI("step/delete/{$step_id}/");
-
-      if ($can_edit) {
-        $item->setHref($edit_uri);
-        $item->setGrippable(true);
-        $item->addSigil('build-step');
-        $item->setMetadata(
-          array(
-            'stepID' => $step->getID(),
-          ));
-      }
 
-      $item
-        ->setHref($edit_uri)
-        ->addAction(
-          id(new PHUIListItemView())
-            ->setIcon('fa-times')
-            ->addSigil('harbormaster-build-step-delete')
-            ->setWorkflow(true)
-            ->setDisabled(!$can_edit)
-            ->setHref(
-              $this->getApplicationURI('step/delete/'.$step->getID().'/')));
-
-      $depends = $step->getStepImplementation()->getDependencies($step);
-      $inputs = $step->getStepImplementation()->getArtifactInputs();
-      $outputs = $step->getStepImplementation()->getArtifactOutputs();
-
-      $has_conflicts = false;
-      if ($depends || $inputs || $outputs) {
-        $available_artifacts =
-          HarbormasterBuildStepImplementation::loadAvailableArtifacts(
-            $plan,
-            $step,
-            null);
-
-        list($depends_ui, $has_conflicts) = $this->buildDependsOnList(
-            $depends,
-            pht('Depends On'),
-            $steps);
-
-        list($inputs_ui, $has_conflicts) = $this->buildArtifactList(
-            $inputs,
-            'in',
-            pht('Input Artifacts'),
-            $available_artifacts);
-
-        list($outputs_ui) = $this->buildArtifactList(
-            $outputs,
-            'out',
-            pht('Output Artifacts'),
-            array());
-
-        $item->appendChild(
-          phutil_tag(
-            'div',
-            array(
-              'class' => 'harbormaster-artifact-io',
-            ),
-            array(
-              $depends_ui,
-              $inputs_ui,
-              $outputs_ui,
-            )));
-      }
+        $depends = $step->getStepImplementation()->getDependencies($step);
+        $inputs = $step->getStepImplementation()->getArtifactInputs();
+        $outputs = $step->getStepImplementation()->getArtifactOutputs();
+
+        $has_conflicts = false;
+        if ($depends || $inputs || $outputs) {
+          $available_artifacts =
+            HarbormasterBuildStepImplementation::loadAvailableArtifacts(
+              $plan,
+              $step,
+              null);
+
+          list($depends_ui, $has_conflicts) = $this->buildDependsOnList(
+              $depends,
+              pht('Depends On'),
+              $steps);
+
+          list($inputs_ui, $has_conflicts) = $this->buildArtifactList(
+              $inputs,
+              'in',
+              pht('Input Artifacts'),
+              $available_artifacts);
+
+          list($outputs_ui) = $this->buildArtifactList(
+              $outputs,
+              'out',
+              pht('Output Artifacts'),
+              array());
+
+          $item->appendChild(
+            phutil_tag(
+              'div',
+              array(
+                'class' => 'harbormaster-artifact-io',
+              ),
+              array(
+                $depends_ui,
+                $inputs_ui,
+                $outputs_ui,
+              )));
+        }
 
-      if ($has_conflicts) {
-        $has_any_conflicts = true;
-        $item->setBarColor('red');
-      }
+        if ($has_conflicts) {
+          $has_any_conflicts = true;
+          $item->setBarColor('red');
+        }
+
+        if ($would_deadlock) {
+          if ($step->getPHID() === $first_to_deadlock) {
+            $is_deadlocking = true;
+          }
+
+          if ($is_deadlocking) {
+            $item->setBarColor('red');
+          }
+        }
 
-      $step_list->addItem($item);
+        $step_list->addItem($item);
+      }
     }
 
-    return array($step_list, $has_any_conflicts);
+    return array($step_list, $has_any_conflicts, $would_deadlock);
   }
 
   private function buildActionList(HarbormasterBuildPlan $plan) {
@@ -397,6 +451,10 @@
     array $steps) {
     $has_conflicts = false;
 
+    if (count($artifacts) === 0) {
+      return null;
+    }
+
     $this->requireResource('harbormaster-css');
 
     $steps = mpull($steps, null, 'getPHID');
diff --git a/src/applications/harbormaster/controller/HarbormasterStepEditController.php b/src/applications/harbormaster/controller/HarbormasterStepEditController.php
--- a/src/applications/harbormaster/controller/HarbormasterStepEditController.php
+++ b/src/applications/harbormaster/controller/HarbormasterStepEditController.php
@@ -116,11 +116,6 @@
       array_unshift($xactions, $depends_on_xaction);
 
       if ($is_new) {
-        // This is okay, but a little iffy. We should move it inside the editor
-        // if we create plans elsewhere.
-        $steps = $plan->loadOrderedBuildSteps();
-        $step->setSequence(count($steps) + 1);
-
         // When creating a new step, make sure we have a create transaction
         // so we'll apply the transactions even if the step has no
         // configurable options.
@@ -163,16 +158,14 @@
         $step_ref,
         HarbormasterBuildArtifact::TYPE_BUILD_STATE);
 
-    if (count($previous_artifacts) > 0) {
-      $form
-        ->appendChild(
-          id(new AphrontFormTokenizerControl())
-            ->setDatasource((string)$datasource_uri)
-            ->setName('dependsOn')
-            ->setLabel(pht('Depends On'))
-            ->setError($e_depends_on)
-            ->setValue($v_depends_on));
-    }
+    $form
+      ->appendChild(
+        id(new AphrontFormTokenizerControl())
+          ->setDatasource((string)$datasource_uri)
+          ->setName('dependsOn')
+          ->setLabel(pht('Depends On'))
+          ->setError($e_depends_on)
+          ->setValue($v_depends_on));
 
     $field_list->appendFieldsToForm($form);
 
diff --git a/src/applications/harbormaster/engine/HarbormasterBuildEngine.php b/src/applications/harbormaster/engine/HarbormasterBuildEngine.php
--- a/src/applications/harbormaster/engine/HarbormasterBuildEngine.php
+++ b/src/applications/harbormaster/engine/HarbormasterBuildEngine.php
@@ -155,6 +155,28 @@
       ->withBuildPlanPHIDs(array($build->getBuildPlan()->getPHID()))
       ->execute();
 
+    $runnable = $this->determineRunnableSteps($build, $targets, $steps);
+
+    if (!$runnable) {
+      return;
+    }
+
+    foreach ($runnable as $runnable_step) {
+      $target = HarbormasterBuildTarget::initializeNewBuildTarget(
+        $build,
+        $runnable_step,
+        $build->retrieveVariablesFromBuild());
+      $target->save();
+
+      $this->queueNewBuildTarget($target);
+    }
+  }
+
+  protected function determineRunnableSteps(
+    HarbormasterBuild $build,
+    array $targets,
+    array $steps) {
+
     // Identify steps which are in various states.
 
     $queued = array();
@@ -232,7 +254,7 @@
     if (count($failed)) {
       $build->setBuildStatus(HarbormasterBuild::STATUS_FAILED);
       $build->save();
-      return;
+      return null;
     }
 
     // If every step is complete, we're done with this build. Mark it passed
@@ -240,7 +262,7 @@
     if (count($complete) == count($steps)) {
       $build->setBuildStatus(HarbormasterBuild::STATUS_PASSED);
       $build->save();
-      return;
+      return null;
     }
 
     // Identify all the steps which are ready to run (because all their
@@ -248,7 +270,7 @@
 
     $runnable = array();
     foreach ($steps as $step) {
-      $dependencies = $step->getDetail('depends_on');
+      $dependencies = $step->getDetail('depends_on', array());
 
       if (isset($queued[$step->getPHID()])) {
         $can_run = true;
@@ -269,21 +291,12 @@
       // This means the build is deadlocked, and the user has configured
       // circular dependencies.  It should not normally be possible yet,
       // but we should communicate it more clearly.
-      $build->setBuildStatus(HarbormasterBuild::STATUS_FAILED);
+      $build->setBuildStatus(HarbormasterBuild::STATUS_DEADLOCKED);
       $build->save();
-      return;
-    }
-
-    foreach ($runnable as $runnable_step) {
-      $target = HarbormasterBuildTarget::initializeNewBuildTarget(
-        $build,
-        $runnable_step,
-        $build->retrieveVariablesFromBuild());
-      $target->save();
-
-      $this->queueNewBuildTarget($target);
+      return null;
     }
 
+    return $runnable;
   }
 
 
@@ -369,7 +382,8 @@
         $all_pass = false;
       }
       if ($build->getBuildStatus() == HarbormasterBuild::STATUS_FAILED ||
-          $build->getBuildStatus() == HarbormasterBuild::STATUS_ERROR) {
+          $build->getBuildStatus() == HarbormasterBuild::STATUS_ERROR ||
+          $build->getBuildStatus() == HarbormasterBuild::STATUS_DEADLOCKED) {
         $any_fail = true;
       }
     }
diff --git a/src/applications/harbormaster/engine/HarbormasterBuildGraph.php b/src/applications/harbormaster/engine/HarbormasterBuildGraph.php
new file mode 100644
--- /dev/null
+++ b/src/applications/harbormaster/engine/HarbormasterBuildGraph.php
@@ -0,0 +1,61 @@
+<?php
+
+/**
+ * Directed graph representing a build plan
+ */
+final class HarbormasterBuildGraph extends AbstractDirectedGraph {
+
+  private $stepMap;
+  
+  public static function determineDependencyExecution(
+    HarbormasterBuildPlan $plan) {
+    
+    $steps = id(new HarbormasterBuildStepQuery())
+      ->setViewer(PhabricatorUser::getOmnipotentUser())
+      ->withBuildPlanPHIDs(array($plan->getPHID()))
+      ->execute();
+      
+    $steps_by_phid = mpull($steps, null, 'getPHID');
+    $step_phids = mpull($steps, 'getPHID');
+    
+    if (count($steps) === 0) {
+      return array(array(), false);
+    }
+    
+    $graph = id(new HarbormasterBuildGraph($steps_by_phid))
+      ->addNodes($step_phids);
+    
+    list($result_phids, $would_deadlock) =
+      $graph->getBestEffortTopographicallySortedNodesByRow();
+    
+    $results = array();
+    foreach ($result_phids as $row_phids) {
+      $row = array();
+      foreach ($row_phids as $phid) {
+        $row[] = $steps_by_phid[$phid];
+      }
+      $results[] = $row;
+    }
+    
+    return array($results, $would_deadlock);
+  }
+  
+  public function __construct($step_map) {
+    $this->stepMap = $step_map;
+  }
+  
+  protected function loadEdges(array $nodes) {
+    $map = array();
+    foreach ($nodes as $node) {
+      $deps = $this->stepMap[$node]->getDetail('depends_on', array());
+      
+      $map[$node] = array();
+      foreach ($deps as $dep) {
+        $map[$node][] = $dep;
+      }
+    }
+    
+    return $map;
+  }
+
+}
diff --git a/src/applications/harbormaster/query/HarbormasterBuildStepQuery.php b/src/applications/harbormaster/query/HarbormasterBuildStepQuery.php
--- a/src/applications/harbormaster/query/HarbormasterBuildStepQuery.php
+++ b/src/applications/harbormaster/query/HarbormasterBuildStepQuery.php
@@ -22,14 +22,6 @@
     return $this;
   }
 
-  public function getPagingColumn() {
-    return 'sequence';
-  }
-
-  public function getReversePaging() {
-    return true;
-  }
-
   protected function loadPage() {
     $table = new HarbormasterBuildStep();
     $conn_r = $table->establishConnection('r');
diff --git a/src/applications/harbormaster/step/HarbormasterBuildStepImplementation.php b/src/applications/harbormaster/step/HarbormasterBuildStepImplementation.php
--- a/src/applications/harbormaster/step/HarbormasterBuildStepImplementation.php
+++ b/src/applications/harbormaster/step/HarbormasterBuildStepImplementation.php
@@ -136,11 +136,17 @@
     $current_build_step,
     $artifact_type) {
 
-    $build_steps = $build_plan->loadOrderedBuildSteps();
+    list($run_order, $will_deadlock) = 
+      HarbormasterBuildGraph::determineDependencyExecution($build_plan);
+
+    if ($will_deadlock) {
+      // Build would deadlock, so there's no valid artifacts.
+      return array();
+    }
 
     return self::getAvailableArtifacts(
       $build_plan,
-      $build_steps,
+      $run_order,
       $current_build_step,
       $artifact_type);
   }
@@ -150,19 +156,33 @@
    */
   public static function getAvailableArtifacts(
     HarbormasterBuildPlan $build_plan,
-    array $build_steps,
+    array $run_order,
     $current_build_step,
     $artifact_type) {
 
     $artifact_arrays = array();
-    foreach ($build_steps as $build_step) {
-      if ($current_build_step !== null &&
-        $build_step->getPHID() === $current_build_step->getPHID()) {
+    foreach ($run_order as $run_row) {
+      // If any of the build steps in the run row include the current step,
+      // then break, because we can't depend on artifacts from build steps
+      // that happen in parallel to us.
+      $should_break = false;
+      foreach ($run_row as $build_step) {
+        if ($current_build_step !== null &&
+          $build_step->getPHID() === $current_build_step->getPHID()) {
+          $should_break = true;
+          break;
+        }
+      }
+
+      if ($should_break) {
         break;
       }
 
-      $implementation = $build_step->getStepImplementation();
-      $artifact_arrays[] = $implementation->getFullArtifactOutputs($build_step);
+      foreach ($run_row as $build_step) {
+        $implementation = $build_step->getStepImplementation();
+        $artifact_arrays[] =
+          $implementation->getFullArtifactOutputs($build_step);
+      }
     }
 
     $artifacts = array();
diff --git a/src/applications/harbormaster/storage/build/HarbormasterBuild.php b/src/applications/harbormaster/storage/build/HarbormasterBuild.php
--- a/src/applications/harbormaster/storage/build/HarbormasterBuild.php
+++ b/src/applications/harbormaster/storage/build/HarbormasterBuild.php
@@ -47,6 +47,11 @@
    */
   const STATUS_STOPPED = 'stopped';
 
+  /**
+   * The build has been deadlocked.
+   */
+  const STATUS_DEADLOCKED = 'deadlocked';
+
 
   /**
    * Get a human readable name for a build status constant.
@@ -70,6 +75,8 @@
         return pht('Unexpected Error');
       case self::STATUS_STOPPED:
         return pht('Stopped');
+      case self::STATUS_DEADLOCKED:
+        return pht('Deadlocked');
       default:
         return pht('Unknown');
     }
@@ -90,6 +97,8 @@
         return PHUIStatusItemView::ICON_MINUS;
       case self::STATUS_STOPPED:
         return PHUIStatusItemView::ICON_MINUS;
+      case self::STATUS_DEADLOCKED:
+        return PHUIStatusItemView::ICON_WARNING;
       default:
         return PHUIStatusItemView::ICON_QUESTION;
     }
@@ -106,6 +115,7 @@
         return 'green';
       case self::STATUS_FAILED:
       case self::STATUS_ERROR:
+      case self::STATUS_DEADLOCKED:
         return 'red';
       case self::STATUS_STOPPED:
         return 'dark';
diff --git a/src/applications/harbormaster/storage/configuration/HarbormasterBuildPlan.php b/src/applications/harbormaster/storage/configuration/HarbormasterBuildPlan.php
--- a/src/applications/harbormaster/storage/configuration/HarbormasterBuildPlan.php
+++ b/src/applications/harbormaster/storage/configuration/HarbormasterBuildPlan.php
@@ -39,19 +39,6 @@
     return $this->assertAttached($this->buildSteps);
   }
 
-  /**
-   * Returns a standard, ordered list of build steps for this build plan.
-   *
-   * This method should be used to load build steps for a given build plan
-   * so that the ordering is consistent.
-   */
-  public function loadOrderedBuildSteps() {
-    return id(new HarbormasterBuildStepQuery())
-      ->setViewer(PhabricatorUser::getOmnipotentUser())
-      ->withBuildPlanPHIDs(array($this->getPHID()))
-      ->execute();
-  }
-
   public function isDisabled() {
     return ($this->getPlanStatus() == self::STATUS_DISABLED);
   }
diff --git a/src/applications/harbormaster/storage/configuration/HarbormasterBuildStep.php b/src/applications/harbormaster/storage/configuration/HarbormasterBuildStep.php
--- a/src/applications/harbormaster/storage/configuration/HarbormasterBuildStep.php
+++ b/src/applications/harbormaster/storage/configuration/HarbormasterBuildStep.php
@@ -9,7 +9,6 @@
   protected $buildPlanPHID;
   protected $className;
   protected $details = array();
-  protected $sequence;
 
   private $buildPlan = self::ATTACHABLE;
   private $customFields = self::ATTACHABLE;
diff --git a/src/applications/typeahead/controller/PhabricatorTypeaheadStepDependenciesDatasourceController.php b/src/applications/typeahead/controller/PhabricatorTypeaheadStepDependenciesDatasourceController.php
--- a/src/applications/typeahead/controller/PhabricatorTypeaheadStepDependenciesDatasourceController.php
+++ b/src/applications/typeahead/controller/PhabricatorTypeaheadStepDependenciesDatasourceController.php
@@ -25,17 +25,15 @@
       ->execute();
     $steps = mpull($steps, null, 'getPHID');
 
-    $current_step = idx($steps, $step_phid);
-
     $artifacts = HarbormasterBuildStepImplementation::loadAvailableArtifacts(
       $plan,
-      $current_step,
+      null,
       HarbormasterBuildArtifact::TYPE_BUILD_STATE);
 
     $results = array();
     foreach ($artifacts as $key => $name) {
       $ref_step = idx($steps, $key);
-      if ($ref_step !== null) {
+      if ($ref_step !== null && $ref_step->getPHID() !== $step_phid) {
         $results[] = id(new PhabricatorTypeaheadResult())
           ->setName($ref_step->getName())
           ->setURI('/')
diff --git a/webroot/rsrc/js/application/harbormaster/behavior-reorder-steps.js b/webroot/rsrc/js/application/harbormaster/behavior-reorder-steps.js
deleted file mode 100644
--- a/webroot/rsrc/js/application/harbormaster/behavior-reorder-steps.js
+++ /dev/null
@@ -1,41 +0,0 @@
-/**
- * @provides javelin-behavior-harbormaster-reorder-steps
- * @requires javelin-behavior
- *           javelin-stratcom
- *           javelin-workflow
- *           javelin-dom
- *           phabricator-draggable-list
- */
-
-JX.behavior('harbormaster-reorder-steps', function(config) {
-
-  var root = JX.$(config.listID);
-
-  var list = new JX.DraggableList('build-step', root)
-    .setFindItemsHandler(function() {
-      return JX.DOM.scry(root, 'li', 'build-step');
-    });
-
-  list.listen('didDrop', function(node) {
-    var nodes = list.findItems();
-    var order = [];
-    var key;
-    for (var ii = 0; ii < nodes.length; ii++) {
-      key = JX.Stratcom.getData(nodes[ii]).stepID;
-      if (key) {
-        order.push(key);
-      }
-    }
-
-    list.lock();
-    JX.DOM.alterClass(node, 'drag-sending', true);
-
-    new JX.Workflow(config.orderURI, {order: order.join()})
-      .setHandler(function() {
-        JX.DOM.alterClass(node, 'drag-sending', false);
-        list.unlock();
-      })
-      .start();
-  });
-
-});