diff --git a/doc/source/zuul.rst b/doc/source/zuul.rst
index 8b325ba..e4ce737 100644
--- a/doc/source/zuul.rst
+++ b/doc/source/zuul.rst
@@ -771,8 +771,11 @@
 executed are listed.  If a job is entered as a dictionary key, then
 jobs contained within that key are only executed if the key job
 succeeds.  In the above example, project-unittest, project-pep8, and
-project-pyflakes are only executed if project-merge succeeds.  This
-can help avoid running unnecessary jobs.
+project-pyflakes are only executed if project-merge succeeds.
+Furthermore, project-finaltest is executed only if project-unittest,
+project-pep8 and project-pyflakes all succeed. This can help avoid
+running unnecessary jobs while maximizing parallelism. It is also
+useful when distributing results between jobs.
 
 The special job named ``noop`` is internal to Zuul and will always
 return ``SUCCESS`` immediately.  This can be useful if you require
diff --git a/tests/fixtures/config/ansible/git/common-config/zuul.yaml b/tests/fixtures/config/ansible/git/common-config/zuul.yaml
index aa70054..50f353d 100644
--- a/tests/fixtures/config/ansible/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/ansible/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -41,7 +39,7 @@
     pre-run: pre
     post-run: post
     vars:
-      flagpath: "{{zuul._test.test_root}}/{{zuul.uuid}}.flag"
+      flagpath: '{{zuul._test.test_root}}/{{zuul.uuid}}.flag'
     roles:
       - zuul: bare-role
 
diff --git a/tests/fixtures/config/ansible/git/org_project/.zuul.yaml b/tests/fixtures/config/ansible/git/org_project/.zuul.yaml
index b38f88e..24ba019 100644
--- a/tests/fixtures/config/ansible/git/org_project/.zuul.yaml
+++ b/tests/fixtures/config/ansible/git/org_project/.zuul.yaml
@@ -4,7 +4,6 @@
 
 - project:
     name: org/project
-
     check:
       jobs:
         - python27
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/A.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/A.yaml
new file mode 100644
index 0000000..f679dce
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/A.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/B.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/B.yaml
new file mode 100644
index 0000000..f679dce
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/B.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/C.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/C.yaml
new file mode 100644
index 0000000..f679dce
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/C.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/D.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/D.yaml
new file mode 100644
index 0000000..f679dce
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/D.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/E.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/E.yaml
new file mode 100644
index 0000000..f679dce
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/E.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/F.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/F.yaml
new file mode 100644
index 0000000..f679dce
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/F.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/G.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/G.yaml
new file mode 100644
index 0000000..f679dce
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/G.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/playbooks/project-test1.yaml b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/project-test1.yaml
new file mode 100644
index 0000000..f679dce
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/playbooks/project-test1.yaml
@@ -0,0 +1,2 @@
+- hosts: all
+  tasks: []
diff --git a/tests/fixtures/config/dependency-graph/git/common-config/zuul.yaml b/tests/fixtures/config/dependency-graph/git/common-config/zuul.yaml
new file mode 100644
index 0000000..60f3651
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/common-config/zuul.yaml
@@ -0,0 +1,73 @@
+- pipeline:
+    name: gate
+    manager: dependent
+    success-message: Build succeeded (gate).
+    source: gerrit
+    trigger:
+      gerrit:
+        - event: comment-added
+          approval:
+            - approved: 1
+    success:
+      gerrit:
+        verified: 2
+        submit: true
+    failure:
+      gerrit:
+        verified: -2
+    start:
+      gerrit:
+        verified: 0
+    precedence: high
+
+- job:
+    name: A
+
+- job:
+    name: B
+
+- job:
+    name: C
+
+- job:
+    name: D
+
+- job:
+    name: E
+
+- job:
+    name: F
+
+- job:
+    name: G
+
+- project:
+    name: org/project
+    gate:
+      jobs:
+        # Job dependencies, starting with A
+        #     A
+        #    / \
+        #   B   C
+        #  / \ / \
+        # D   F   E
+        #     |
+        #     G
+        # This is intentionally not listed in the natural order to
+        # ensure that we can reference dependencies before they are
+        # defined.
+        - E:
+            dependencies: C
+        - A
+        - B:
+            dependencies: A
+        - C:
+            dependencies: A
+        - F:
+            dependencies:
+              - B
+              - C
+        - D:
+            dependencies: B
+        - G:
+            dependencies: F
diff --git a/tests/fixtures/config/dependency-graph/git/org_project/README b/tests/fixtures/config/dependency-graph/git/org_project/README
new file mode 100644
index 0000000..9daeafb
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/git/org_project/README
@@ -0,0 +1 @@
+test
diff --git a/tests/fixtures/config/dependency-graph/main.yaml b/tests/fixtures/config/dependency-graph/main.yaml
new file mode 100644
index 0000000..d9868fa
--- /dev/null
+++ b/tests/fixtures/config/dependency-graph/main.yaml
@@ -0,0 +1,8 @@
+- tenant:
+    name: tenant-one
+    source:
+      gerrit:
+        config-repos:
+          - common-config
+        project-repos:
+          - org/project
diff --git a/tests/fixtures/config/duplicate-pipeline/git/common-config/zuul.yaml b/tests/fixtures/config/duplicate-pipeline/git/common-config/zuul.yaml
index bc88b06..5005108 100755
--- a/tests/fixtures/config/duplicate-pipeline/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/duplicate-pipeline/git/common-config/zuul.yaml
@@ -2,8 +2,7 @@
     name: dup1
     manager: independent
     success-message: Build succeeded (dup1).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: change-restored
@@ -18,8 +17,7 @@
     name: dup2
     manager: independent
     success-message: Build succeeded (dup2).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: change-restored
@@ -39,7 +37,6 @@
       queue: integrated
       jobs:
         - project-test1
-
     dup2:
       queue: integrated
       jobs:
diff --git a/tests/fixtures/config/in-repo/git/common-config/zuul.yaml b/tests/fixtures/config/in-repo/git/common-config/zuul.yaml
index d8b7200..55169ce 100644
--- a/tests/fixtures/config/in-repo/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/in-repo/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: tenant-one-gate
     manager: dependent
     success-message: Build succeeded (tenant-one-gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
diff --git a/tests/fixtures/config/merges/git/common-config/zuul.yaml b/tests/fixtures/config/merges/git/common-config/zuul.yaml
index bb91f3a..ab4e24c 100644
--- a/tests/fixtures/config/merges/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/merges/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -37,16 +35,13 @@
     precedence: high
 
 - job:
-    name:
-      project-test1
+    name: project-test1
 
 - job:
-    name:
-      project-test2
+    name: project-test2
 
 - job:
-    name:
-      project-merge
+    name: project-merge
     hold-following-changes: true
 
 - project:
@@ -75,6 +70,6 @@
     merge-mode: cherry-pick
     gate:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
diff --git a/tests/fixtures/config/multi-tenant/git/common-config/zuul.yaml b/tests/fixtures/config/multi-tenant/git/common-config/zuul.yaml
index 08117d6..004f2df 100644
--- a/tests/fixtures/config/multi-tenant/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/multi-tenant/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -14,8 +13,7 @@
         verified: -1
 
 - job:
-    name:
-      python27
+    name: python27
     nodes:
       - name: controller
         image: ubuntu-trusty
diff --git a/tests/fixtures/config/multi-tenant/git/tenant-one-config/zuul.yaml b/tests/fixtures/config/multi-tenant/git/tenant-one-config/zuul.yaml
index 4a653f6..5769cf5 100644
--- a/tests/fixtures/config/multi-tenant/git/tenant-one-config/zuul.yaml
+++ b/tests/fixtures/config/multi-tenant/git/tenant-one-config/zuul.yaml
@@ -2,8 +2,7 @@
     name: tenant-one-gate
     manager: dependent
     success-message: Build succeeded (tenant-one-gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -28,8 +27,7 @@
         image: controller-image
 
 - job:
-    name:
-      project1-test1
+    name: project1-test1
 
 - project:
     name: org/project1
diff --git a/tests/fixtures/config/multi-tenant/git/tenant-two-config/zuul.yaml b/tests/fixtures/config/multi-tenant/git/tenant-two-config/zuul.yaml
index 7c79720..19782ce 100644
--- a/tests/fixtures/config/multi-tenant/git/tenant-two-config/zuul.yaml
+++ b/tests/fixtures/config/multi-tenant/git/tenant-two-config/zuul.yaml
@@ -2,8 +2,7 @@
     name: tenant-two-gate
     manager: dependent
     success-message: Build succeeded (tenant-two-gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -28,8 +27,7 @@
         image: controller-image
 
 - job:
-    name:
-      project2-test1
+    name: project2-test1
 
 - project:
     name: org/project2
diff --git a/tests/fixtures/config/one-job-project/git/common-config/zuul.yaml b/tests/fixtures/config/one-job-project/git/common-config/zuul.yaml
index 148ba42..4579062 100644
--- a/tests/fixtures/config/one-job-project/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/one-job-project/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -39,8 +37,7 @@
 - pipeline:
     name: post
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: ref-updated
diff --git a/tests/fixtures/config/openstack/git/project-config/zuul.yaml b/tests/fixtures/config/openstack/git/project-config/zuul.yaml
index 420d979..760adb8 100644
--- a/tests/fixtures/config/openstack/git/project-config/zuul.yaml
+++ b/tests/fixtures/config/openstack/git/project-config/zuul.yaml
@@ -1,11 +1,8 @@
-# Pipeline definitions
-
 - pipeline:
     name: check
     manager: independent
     success-message: Build succeeded (check).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -20,8 +17,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -39,8 +35,6 @@
         verified: 0
     precedence: high
 
-# Job definitions
-
 - job:
     name: base
     timeout: 30
@@ -78,8 +72,6 @@
       - openstack/keystone
       - openstack/nova
 
-# Project definitions
-
 - project:
     name: openstack/nova
     templates:
diff --git a/tests/fixtures/config/requirements/email/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/email/git/common-config/zuul.yaml
index 09e0cc6..78d2a18 100644
--- a/tests/fixtures/config/requirements/email/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/email/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: pipeline
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -19,8 +18,7 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
diff --git a/tests/fixtures/config/requirements/newer-than/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/newer-than/git/common-config/zuul.yaml
index cd76afd..1e84e18 100644
--- a/tests/fixtures/config/requirements/newer-than/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/newer-than/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: pipeline
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -20,8 +19,7 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
diff --git a/tests/fixtures/config/requirements/older-than/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/older-than/git/common-config/zuul.yaml
index 8dca5e6..efbd79a 100644
--- a/tests/fixtures/config/requirements/older-than/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/older-than/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: pipeline
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -20,8 +19,7 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
diff --git a/tests/fixtures/config/requirements/reject-username/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/reject-username/git/common-config/zuul.yaml
index 92c7de2..7212944 100644
--- a/tests/fixtures/config/requirements/reject-username/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/reject-username/git/common-config/zuul.yaml
@@ -1,11 +1,10 @@
 - pipeline:
     name: pipeline
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     reject:
       approval:
-        - username: 'jenkins'
+        - username: jenkins
     trigger:
       gerrit:
         - event: comment-added
@@ -19,13 +18,12 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
           reject-approval:
-            - username: 'jenkins'
+            - username: jenkins
     success:
       gerrit:
         verified: 1
diff --git a/tests/fixtures/config/requirements/reject/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/reject/git/common-config/zuul.yaml
index 12a2538..9f5b125 100644
--- a/tests/fixtures/config/requirements/reject/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/reject/git/common-config/zuul.yaml
@@ -1,15 +1,18 @@
 - pipeline:
     name: pipeline
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     require:
       approval:
         - username: jenkins
-          verified: [1, 2]
+          verified:
+            - 1
+            - 2
     reject:
       approval:
-        - verified: [-1, -2]
+        - verified:
+            - -1
+            - -2
     trigger:
       gerrit:
         - event: comment-added
@@ -23,16 +26,19 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
           require-approval:
             - username: jenkins
-              verified: [1, 2]
+              verified:
+                - 1
+                - 2
           reject-approval:
-            - verified: [-1, -2]
+            - verified:
+                - -1
+                - -2
     success:
       gerrit:
         verified: 1
diff --git a/tests/fixtures/config/requirements/state/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/state/git/common-config/zuul.yaml
index 9491bff..01ceb46 100644
--- a/tests/fixtures/config/requirements/state/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/state/git/common-config/zuul.yaml
@@ -1,10 +1,9 @@
 - pipeline:
     name: current-check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     require:
-      current-patchset: True
+      current-patchset: true
     trigger:
       gerrit:
         - event: patchset-created
@@ -19,10 +18,9 @@
 - pipeline:
     name: open-check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     require:
-      open: True
+      open: true
     trigger:
       gerrit:
         - event: patchset-created
@@ -37,8 +35,7 @@
 - pipeline:
     name: status-check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     require:
       status: NEW
     trigger:
diff --git a/tests/fixtures/config/requirements/username/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/username/git/common-config/zuul.yaml
index ca2ff97..9789e71 100644
--- a/tests/fixtures/config/requirements/username/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/username/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: pipeline
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -19,8 +18,7 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
diff --git a/tests/fixtures/config/requirements/vote1/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/vote1/git/common-config/zuul.yaml
index 00afe79..7989363 100644
--- a/tests/fixtures/config/requirements/vote1/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/vote1/git/common-config/zuul.yaml
@@ -1,4 +1,3 @@
-
 - pipeline:
     name: pipeline
     manager: independent
@@ -6,8 +5,7 @@
       approval:
         - username: jenkins
           verified: 1
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -21,8 +19,7 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
diff --git a/tests/fixtures/config/requirements/vote2/git/common-config/zuul.yaml b/tests/fixtures/config/requirements/vote2/git/common-config/zuul.yaml
index 73db7a7..9348afb 100644
--- a/tests/fixtures/config/requirements/vote2/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/requirements/vote2/git/common-config/zuul.yaml
@@ -4,9 +4,10 @@
     require:
       approval:
         - username: jenkins
-          verified: [1, 2]
-    source:
-      gerrit
+          verified:
+            - 1
+            - 2
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -20,14 +21,15 @@
 - pipeline:
     name: trigger
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
           require-approval:
             - username: jenkins
-              verified: [1, 2]
+              verified:
+                - 1
+                - 2
     success:
       gerrit:
         verified: 1
diff --git a/tests/fixtures/config/single-tenant/git/common-config/zuul.yaml b/tests/fixtures/config/single-tenant/git/common-config/zuul.yaml
index b91bf6f..47c173d 100644
--- a/tests/fixtures/config/single-tenant/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -39,8 +37,7 @@
 - pipeline:
     name: post
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: ref-updated
@@ -49,8 +46,7 @@
 - pipeline:
     name: experimental
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -107,23 +103,26 @@
 - job:
     name: project-testfile
     files:
-      - '.*-requires'
+      - .*-requires
 
 - project:
     name: org/project
     check:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
     gate:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
-              - project-testfile
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
+        - project-testfile:
+            dependencies: project-merge
     post:
       jobs:
         - project-post
@@ -132,48 +131,58 @@
     name: org/project1
     check:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
-              - project1-project2-integration
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
+        - project1-project2-integration:
+            dependencies: project-merge
     gate:
       queue: integrated
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
-              - project1-project2-integration
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
+        - project1-project2-integration:
+            dependencies: project-merge
 
 - project:
     name: org/project2
     gate:
       queue: integrated
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
-              - project1-project2-integration
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
+        - project1-project2-integration:
+            dependencies: project-merge
 
 - project:
     name: org/project3
     check:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
-              - project1-project2-integration
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
+        - project1-project2-integration:
+            dependencies: project-merge
     gate:
       queue: integrated
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
-              - project1-project2-integration
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
+        - project1-project2-integration:
+            dependencies: project-merge
     post:
       jobs:
         - project-post
@@ -182,9 +191,9 @@
     name: org/experimental-project
     experimental:
       jobs:
-        - project-merge:
-            jobs:
-              - experimental-project-test
+        - project-merge
+        - experimental-project-test:
+            dependencies: project-merge
 
 - project:
     name: org/noop-project
@@ -199,16 +208,18 @@
     name: org/nonvoting-project
     check:
       jobs:
-        - nonvoting-project-merge:
-            jobs:
-              - nonvoting-project-test1
-              - nonvoting-project-test2
+        - nonvoting-project-merge
+        - nonvoting-project-test1:
+            dependencies: nonvoting-project-merge
+        - nonvoting-project-test2:
+            dependencies: nonvoting-project-merge
     gate:
       jobs:
-        - nonvoting-project-merge:
-            jobs:
-              - nonvoting-project-test1
-              - nonvoting-project-test2
+        - nonvoting-project-merge
+        - nonvoting-project-test1:
+            dependencies: nonvoting-project-merge
+        - nonvoting-project-test2:
+            dependencies: nonvoting-project-merge
 
 - project:
     name: org/no-jobs-project
diff --git a/tests/fixtures/config/single-tenant/git/layout-disabled-at/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-disabled-at/zuul.yaml
index 4cf6f16..bdc19ac 100644
--- a/tests/fixtures/config/single-tenant/git/layout-disabled-at/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-disabled-at/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
diff --git a/tests/fixtures/config/single-tenant/git/layout-dont-ignore-ref-deletes/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-dont-ignore-ref-deletes/zuul.yaml
index 30e574a..334d9ac 100644
--- a/tests/fixtures/config/single-tenant/git/layout-dont-ignore-ref-deletes/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-dont-ignore-ref-deletes/zuul.yaml
@@ -1,13 +1,12 @@
 - pipeline:
     name: post
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: ref-updated
           ref: ^(?!refs/).*$
-          ignore-deletes: False
+          ignore-deletes: false
 
 - job:
     name: project-post
@@ -20,4 +19,3 @@
     post:
       jobs:
         - project-post
-
diff --git a/tests/fixtures/config/single-tenant/git/layout-footer-message/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-footer-message/zuul.yaml
index 0c04070..c698378 100644
--- a/tests/fixtures/config/single-tenant/git/layout-footer-message/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-footer-message/zuul.yaml
@@ -2,8 +2,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     failure-message: Build failed.  For information on how to proceed, see http://wiki.example.org/Test_Failures
     footer-message: For CI problems and help debugging, contact ci@example.org
     trigger:
@@ -35,4 +34,3 @@
     gate:
       jobs:
         - project-test1
-
diff --git a/tests/fixtures/config/single-tenant/git/layout-idle/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-idle/zuul.yaml
index f71f3e4..d1fa04b 100644
--- a/tests/fixtures/config/single-tenant/git/layout-idle/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-idle/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: periodic
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       timer:
         - time: '* * * * * */1'
diff --git a/tests/fixtures/config/single-tenant/git/layout-inheritance/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-inheritance/zuul.yaml
index 3070af0..ab8c9a5 100644
--- a/tests/fixtures/config/single-tenant/git/layout-inheritance/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-inheritance/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -13,7 +12,6 @@
       gerrit:
         verified: -1
 
-
 - job:
     name: project-test-irrelevant-starts-empty
 
diff --git a/tests/fixtures/config/single-tenant/git/layout-irrelevant-files/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-irrelevant-files/zuul.yaml
index f243bcc..5d72fc0 100644
--- a/tests/fixtures/config/single-tenant/git/layout-irrelevant-files/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-irrelevant-files/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -13,7 +12,6 @@
       gerrit:
         verified: -1
 
-
 - job:
     name: project-test-irrelevant-files
 
diff --git a/tests/fixtures/config/single-tenant/git/layout-mutex-reconfiguration/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-mutex-reconfiguration/zuul.yaml
index 12f1747..0e332e4 100644
--- a/tests/fixtures/config/single-tenant/git/layout-mutex-reconfiguration/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-mutex-reconfiguration/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
diff --git a/tests/fixtures/config/single-tenant/git/layout-mutex/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-mutex/zuul.yaml
index e91903a..bb92b7a 100644
--- a/tests/fixtures/config/single-tenant/git/layout-mutex/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-mutex/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
diff --git a/tests/fixtures/config/single-tenant/git/layout-no-timer/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-no-timer/zuul.yaml
index f754e37..ab919a4 100644
--- a/tests/fixtures/config/single-tenant/git/layout-no-timer/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-no-timer/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -18,8 +17,7 @@
     manager: independent
     # Trigger is required, set it to one that is a noop
     # during tests that check the timer trigger.
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: ref-updated
diff --git a/tests/fixtures/config/single-tenant/git/layout-repo-deleted/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-repo-deleted/zuul.yaml
index 2bffc3e..5851d75 100644
--- a/tests/fixtures/config/single-tenant/git/layout-repo-deleted/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-repo-deleted/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -60,13 +58,15 @@
     name: org/delete-project
     check:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
     gate:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
diff --git a/tests/fixtures/config/single-tenant/git/layout-smtp/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-smtp/zuul.yaml
index 9effb1f..be90d48 100644
--- a/tests/fixtures/config/single-tenant/git/layout-smtp/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-smtp/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -23,8 +22,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -69,13 +67,15 @@
     name: org/project
     check:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
     gate:
       jobs:
-        - project-merge:
-            jobs:
-              - project-test1
-              - project-test2
+        - project-merge
+        - project-test1:
+            dependencies: project-merge
+        - project-test2:
+            dependencies: project-merge
diff --git a/tests/fixtures/config/single-tenant/git/layout-tags/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-tags/zuul.yaml
index c921c90..07f0657 100644
--- a/tests/fixtures/config/single-tenant/git/layout-tags/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-tags/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -34,19 +33,23 @@
     check:
       jobs:
         - merge:
-            jobs:
-              - test1
-              - test2
-              - integration
             tags:
               - extratag
+        - test1:
+            dependencies: merge
+        - test2:
+            dependencies: merge
+        - integration:
+            dependencies: merge
 
 - project:
     name: org/project2
     check:
       jobs:
-        - merge:
-            jobs:
-              - test1
-              - test2
-              - integration
+        - merge
+        - test1:
+            dependencies: merge
+        - test2:
+            dependencies: merge
+        - integration:
+            dependencies: merge
diff --git a/tests/fixtures/config/single-tenant/git/layout-timer-smtp/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-timer-smtp/zuul.yaml
index 4a14107..2a2eca5 100644
--- a/tests/fixtures/config/single-tenant/git/layout-timer-smtp/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-timer-smtp/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: periodic
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       timer:
         - time: '* * * * * */1'
@@ -10,7 +9,7 @@
       smtp:
         to: alternative_me@example.com
         from: zuul_from@example.com
-        subject: 'Periodic check for {change.project} succeeded'
+        subject: Periodic check for {change.project} succeeded
 
 - job:
     name: project-bitrot-stable-old
diff --git a/tests/fixtures/config/single-tenant/git/layout-timer/zuul.yaml b/tests/fixtures/config/single-tenant/git/layout-timer/zuul.yaml
index f69a91d..8072644 100644
--- a/tests/fixtures/config/single-tenant/git/layout-timer/zuul.yaml
+++ b/tests/fixtures/config/single-tenant/git/layout-timer/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -16,8 +15,7 @@
 - pipeline:
     name: periodic
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       timer:
         - time: '* * * * * */1'
diff --git a/tests/fixtures/config/success-url/git/common-config/zuul.yaml b/tests/fixtures/config/success-url/git/common-config/zuul.yaml
index 7edb340..f2d5251 100644
--- a/tests/fixtures/config/success-url/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/success-url/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -18,7 +17,6 @@
       gerrit:
         verified: -1
 
-
 - job:
     name: docs-draft-test
     success-url: http://docs-draft.example.org/{build.parameters[LOG_PATH]}/publish-docs/
diff --git a/tests/fixtures/config/templated-project/git/common-config/zuul.yaml b/tests/fixtures/config/templated-project/git/common-config/zuul.yaml
index 22a2d6d..8d2c8a0 100644
--- a/tests/fixtures/config/templated-project/git/common-config/zuul.yaml
+++ b/tests/fixtures/config/templated-project/git/common-config/zuul.yaml
@@ -1,8 +1,7 @@
 - pipeline:
     name: check
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: patchset-created
@@ -17,8 +16,7 @@
     name: gate
     manager: dependent
     success-message: Build succeeded (gate).
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: comment-added
@@ -39,8 +37,7 @@
 - pipeline:
     name: post
     manager: independent
-    source:
-      gerrit
+    source: gerrit
     trigger:
       gerrit:
         - event: ref-updated
@@ -56,15 +53,15 @@
 - project-template:
     name: test-three-and-four
     check:
-       jobs:
-         - layered-project-test3
-         - layered-project-test4
+      jobs:
+        - layered-project-test3
+        - layered-project-test4
 
 - project-template:
     name: test-five
     check:
       jobs:
-         - layered-project-foo-test5
+        - layered-project-foo-test5
 
 - job:
     name: project-test1
diff --git a/tests/unit/test_model.py b/tests/unit/test_model.py
index 04d1473..ee7c6ab 100644
--- a/tests/unit/test_model.py
+++ b/tests/unit/test_model.py
@@ -225,7 +225,7 @@
         self.assertFalse(python27diablo.changeMatches(change))
         self.assertFalse(python27essex.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -253,7 +253,7 @@
         self.assertTrue(python27diablo.changeMatches(change))
         self.assertFalse(python27essex.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -282,7 +282,7 @@
         self.assertFalse(python27diablo.changeMatches(change))
         self.assertTrue(python27essex.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -439,7 +439,7 @@
         self.assertTrue(python27.changeMatches(change))
         self.assertFalse(python27diablo.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -453,7 +453,7 @@
         self.assertTrue(python27.changeMatches(change))
         self.assertTrue(python27diablo.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual(len(item.getJobs()), 1)
         job = item.getJobs()[0]
         self.assertEqual(job.name, 'python27')
@@ -506,7 +506,7 @@
         self.assertTrue(base.changeMatches(change))
         self.assertFalse(python27.changeMatches(change))
 
-        item.freezeJobTree()
+        item.freezeJobGraph()
         self.assertEqual([], item.getJobs())
 
     def test_job_source_project(self):
@@ -609,3 +609,56 @@
         for x in range(10):
             self.db.update('job-name', 100, 'SUCCESS')
         self.assertEqual(self.db.getEstimatedTime('job-name'), 100)
+
+
+class TestGraph(BaseTestCase):
+    def test_job_graph_disallows_multiple_jobs_with_same_name(self):
+        graph = model.JobGraph()
+        job1 = model.Job('job')
+        job2 = model.Job('job')
+        graph.addJob(job1)
+        with testtools.ExpectedException(Exception,
+                                         "Job job already added"):
+            graph.addJob(job2)
+
+    def test_job_graph_disallows_circular_dependencies(self):
+        graph = model.JobGraph()
+        jobs = [model.Job('job%d' % i) for i in range(0, 10)]
+        prevjob = None
+        for j in jobs[:3]:
+            if prevjob:
+                j.dependencies = frozenset([prevjob.name])
+            graph.addJob(j)
+            prevjob = j
+        # 0 triggers 1 triggers 2 triggers 3...
+
+        # Cannot depend on itself
+        with testtools.ExpectedException(
+                Exception,
+                "Dependency cycle detected in job jobX"):
+            j = model.Job('jobX')
+            j.dependencies = frozenset([j.name])
+            graph.addJob(j)
+
+        # Disallow circular dependencies
+        with testtools.ExpectedException(
+                Exception,
+                "Dependency cycle detected in job job3"):
+            jobs[4].dependencies = frozenset([jobs[3].name])
+            graph.addJob(jobs[4])
+            jobs[3].dependencies = frozenset([jobs[4].name])
+            graph.addJob(jobs[3])
+
+        jobs[5].dependencies = frozenset([jobs[4].name])
+        graph.addJob(jobs[5])
+
+        with testtools.ExpectedException(
+                Exception,
+                "Dependency cycle detected in job job3"):
+            jobs[3].dependencies = frozenset([jobs[5].name])
+            graph.addJob(jobs[3])
+
+        jobs[3].dependencies = frozenset([jobs[2].name])
+        graph.addJob(jobs[3])
+        jobs[6].dependencies = frozenset([jobs[2].name])
+        graph.addJob(jobs[6])
diff --git a/tests/unit/test_scheduler.py b/tests/unit/test_scheduler.py
index e32e41b..a923ff1 100755
--- a/tests/unit/test_scheduler.py
+++ b/tests/unit/test_scheduler.py
@@ -4478,6 +4478,117 @@
         self.assertIn('project-test2 : SKIPPED', A.messages[1])
 
 
+class TestDependencyGraph(ZuulTestCase):
+    tenant_config_file = 'config/dependency-graph/main.yaml'
+
+    def test_dependeny_graph_dispatch_jobs_once(self):
+        "Test a job in a dependency graph is queued only once"
+        # Job dependencies, starting with A
+        #     A
+        #    / \
+        #   B   C
+        #  / \ / \
+        # D   F   E
+        #     |
+        #     G
+
+        self.executor_server.hold_jobs_in_build = True
+        change = self.fake_gerrit.addFakeChange(
+            'org/project', 'master', 'change')
+        change.addApproval('code-review', 2)
+        self.fake_gerrit.addEvent(change.addApproval('approved', 1))
+
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['A'])
+
+        self.executor_server.release('A')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['B', 'C'])
+
+        self.executor_server.release('B')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['C', 'D'])
+
+        self.executor_server.release('D')
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['C'])
+
+        self.executor_server.release('C')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['E', 'F'])
+
+        self.executor_server.release('F')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['E', 'G'])
+
+        self.executor_server.release('G')
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['E'])
+
+        self.executor_server.release('E')
+        self.waitUntilSettled()
+        self.assertEqual(len(self.builds), 0)
+
+        self.executor_server.hold_jobs_in_build = False
+        self.executor_server.release()
+        self.waitUntilSettled()
+
+        self.assertEqual(len(self.builds), 0)
+        self.assertEqual(len(self.history), 7)
+
+        self.assertEqual(change.data['status'], 'MERGED')
+        self.assertEqual(change.reported, 2)
+
+    def test_jobs_launched_only_if_all_dependencies_are_successful(self):
+        "Test that a job waits till all dependencies are successful"
+        # Job dependencies, starting with A
+        #     A
+        #    / \
+        #   B   C*
+        #  / \ / \
+        # D   F   E
+        #     |
+        #     G
+
+        self.executor_server.hold_jobs_in_build = True
+        change = self.fake_gerrit.addFakeChange(
+            'org/project', 'master', 'change')
+        change.addApproval('code-review', 2)
+
+        self.executor_server.failJob('C', change)
+
+        self.fake_gerrit.addEvent(change.addApproval('approved', 1))
+
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['A'])
+
+        self.executor_server.release('A')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['B', 'C'])
+
+        self.executor_server.release('B')
+        self.waitUntilSettled()
+        self.assertEqual(sorted(b.name for b in self.builds), ['C', 'D'])
+
+        self.executor_server.release('D')
+        self.waitUntilSettled()
+        self.assertEqual([b.name for b in self.builds], ['C'])
+
+        self.executor_server.release('C')
+        self.waitUntilSettled()
+        self.assertEqual(len(self.builds), 0)
+
+        self.executor_server.hold_jobs_in_build = False
+        self.executor_server.release()
+        self.waitUntilSettled()
+
+        self.assertEqual(len(self.builds), 0)
+        self.assertEqual(len(self.history), 4)
+
+        self.assertEqual(change.data['status'], 'NEW')
+        self.assertEqual(change.reported, 2)
+
+
 class TestDuplicatePipeline(ZuulTestCase):
     tenant_config_file = 'config/duplicate-pipeline/main.yaml'
 
diff --git a/zuul/configloader.py b/zuul/configloader.py
index 3f72212..8bae3c5 100644
--- a/zuul/configloader.py
+++ b/zuul/configloader.py
@@ -193,6 +193,7 @@
                'roles': to_list(role),
                'repos': to_list(str),
                'vars': dict,
+               'dependencies': to_list(str),
                }
 
         return vs.Schema(job)
@@ -276,6 +277,8 @@
             # accumulate onto any previously applied tags.
             job.tags = job.tags.union(set(tags))
 
+        job.dependencies = frozenset(as_list(conf.get('dependencies')))
+
         roles = []
         for role in conf.get('roles', []):
             if 'zuul' in role:
@@ -364,45 +367,33 @@
             project_pipeline = model.ProjectPipelineConfig()
             project_template.pipelines[pipeline.name] = project_pipeline
             project_pipeline.queue_name = conf_pipeline.get('queue')
-            project_pipeline.job_tree = ProjectTemplateParser._parseJobTree(
+            ProjectTemplateParser._parseJobList(
                 tenant, layout, conf_pipeline.get('jobs', []),
-                source_context, start_mark)
+                source_context, start_mark, project_pipeline.job_list)
         return project_template
 
     @staticmethod
-    def _parseJobTree(tenant, layout, conf, source_context,
-                      start_mark, tree=None):
-        if not tree:
-            tree = model.JobTree(None)
+    def _parseJobList(tenant, layout, conf, source_context,
+                      start_mark, job_list):
         for conf_job in conf:
             if isinstance(conf_job, six.string_types):
                 job = model.Job(conf_job)
-                tree.addJob(job)
+                job_list.addJob(job)
             elif isinstance(conf_job, dict):
-                # A dictionary in a job tree may override params, or
-                # be the root of a sub job tree, or both.
+                # A dictionary in a job tree may override params
                 jobname, attrs = conf_job.items()[0]
-                jobs = attrs.pop('jobs', None)
                 if attrs:
                     # We are overriding params, so make a new job def
                     attrs['name'] = jobname
                     attrs['_source_context'] = source_context
                     attrs['_start_mark'] = start_mark
-                    subtree = tree.addJob(JobParser.fromYaml(
-                        tenant, layout, attrs))
+                    job_list.addJob(JobParser.fromYaml(tenant, layout, attrs))
                 else:
                     # Not overriding, so add a blank job
                     job = model.Job(jobname)
-                    subtree = tree.addJob(job)
-
-                if jobs:
-                    # This is the root of a sub tree
-                    ProjectTemplateParser._parseJobTree(
-                        tenant, layout, jobs, source_context,
-                        start_mark, subtree)
+                    job_list.addJob(job)
             else:
                 raise Exception("Job must be a string or dictionary")
-        return tree
 
 
 class ProjectParser(object):
@@ -455,7 +446,6 @@
             project.merge_mode = model.MERGER_MAP['merge-resolve']
         for pipeline in layout.pipelines.values():
             project_pipeline = model.ProjectPipelineConfig()
-            project_pipeline.job_tree = model.JobTree(None)
             queue_name = None
             # For every template, iterate over the job tree and replace or
             # create the jobs in the final definition as needed.
@@ -467,8 +457,8 @@
                         (template.name, pipeline.name))
                     pipeline_defined = True
                     template_pipeline = template.pipelines[pipeline.name]
-                    project_pipeline.job_tree.inheritFrom(
-                        template_pipeline.job_tree)
+                    project_pipeline.job_list.inheritFrom(
+                        template_pipeline.job_list)
                     if template_pipeline.queue_name:
                         queue_name = template_pipeline.queue_name
             if queue_name:
diff --git a/zuul/manager/__init__.py b/zuul/manager/__init__.py
index e7508b6..58ad607 100644
--- a/zuul/manager/__init__.py
+++ b/zuul/manager/__init__.py
@@ -64,31 +64,29 @@
             self.log.info("    %s" % e)
         self.log.info("  Projects:")
 
-        def log_jobs(tree, indent=0):
-            istr = '    ' + ' ' * indent
-            if tree.job:
-                # TODOv3(jeblair): represent matchers
-                efilters = ''
-                # for b in tree.job._branches:
-                #     efilters += str(b)
-                # for f in tree.job._files:
-                #     efilters += str(f)
-                # if tree.job.skip_if_matcher:
-                #     efilters += str(tree.job.skip_if_matcher)
-                # if efilters:
-                #     efilters = ' ' + efilters
-                tags = []
-                if tree.job.hold_following_changes:
-                    tags.append('[hold]')
-                if not tree.job.voting:
-                    tags.append('[nonvoting]')
-                if tree.job.mutex:
-                    tags.append('[mutex: %s]' % tree.job.mutex)
-                tags = ' '.join(tags)
-                self.log.info("%s%s%s %s" % (istr, repr(tree.job),
-                                             efilters, tags))
-            for x in tree.job_trees:
-                log_jobs(x, indent + 2)
+        def log_jobs(job_list):
+            for job_name, job_variants in job_list.jobs.items():
+                for variant in job_variants:
+                    # TODOv3(jeblair): represent matchers
+                    efilters = ''
+                    # for b in tree.job._branches:
+                    #     efilters += str(b)
+                    # for f in tree.job._files:
+                    #     efilters += str(f)
+                    # if tree.job.skip_if_matcher:
+                    #     efilters += str(tree.job.skip_if_matcher)
+                    # if efilters:
+                    #     efilters = ' ' + efilters
+                    tags = []
+                    if variant.hold_following_changes:
+                        tags.append('[hold]')
+                    if not variant.voting:
+                        tags.append('[nonvoting]')
+                    if variant.mutex:
+                        tags.append('[mutex: %s]' % variant.mutex)
+                    tags = ' '.join(tags)
+                    self.log.info("      %s%s %s" % (repr(variant),
+                                                     efilters, tags))
 
         for project_name in layout.project_configs.keys():
             project_config = layout.project_configs.get(project_name)
@@ -97,7 +95,7 @@
                     self.pipeline.name)
                 if project_pipeline_config:
                     self.log.info("    %s" % project_name)
-                    log_jobs(project_pipeline_config.job_tree)
+                    log_jobs(project_pipeline_config.job_list)
         self.log.info("  On start:")
         self.log.info("    %s" % self.pipeline.start_actions)
         self.log.info("  On success:")
@@ -257,7 +255,7 @@
                 # Rebuild the frozen job tree from the new layout, if
                 # we have one.  If not, it will be built later.
                 if item.current_build_set.layout:
-                    item.freezeJobTree()
+                    item.freezeJobGraph()
 
                 # Re-set build results in case any new jobs have been
                 # added to the tree.
@@ -540,8 +538,18 @@
             item.current_build_set.layout = self.getLayout(item)
         if not item.current_build_set.layout:
             return False
-        if not item.job_tree:
-            item.freezeJobTree()
+        if item.current_build_set.config_error:
+            return False
+        if not item.job_graph:
+            try:
+                item.freezeJobGraph()
+            except Exception as e:
+                # TODOv3(jeblair): nicify this exception as it will be reported
+                self.log.exception("Error freezing job graph for %s" %
+                                   item)
+                item.setConfigError("Unable to freeze job graph: %s" %
+                                    (str(e)))
+                return False
         return True
 
     def _processOneItem(self, item, nnfi):
diff --git a/zuul/model.py b/zuul/model.py
index b57eef8..3676b68 100644
--- a/zuul/model.py
+++ b/zuul/model.py
@@ -675,6 +675,7 @@
             file_matcher=None,
             irrelevant_file_matcher=None,  # skip-if
             tags=frozenset(),
+            dependencies=frozenset(),
         )
 
         # These attributes affect how the job is actually run and more
@@ -851,60 +852,100 @@
         return True
 
 
-class JobTree(object):
-    """A JobTree holds one or more Jobs to represent Job dependencies.
+class JobList(object):
+    """ A list of jobs in a project's pipeline. """
 
-    If Job foo should only execute if Job bar succeeds, then there will
-    be a JobTree for foo, which will contain a JobTree for bar. A JobTree
-    can hold more than one dependent JobTrees, such that jobs bar and bang
-    both depend on job foo being successful.
-
-    A root node of a JobTree will have no associated Job."""
-
-    def __init__(self, job):
-        self.job = job
-        self.job_trees = []
-
-    def __repr__(self):
-        return '<JobTree %s %s>' % (self.job, self.job_trees)
+    def __init__(self):
+        self.jobs = OrderedDict()  # job.name -> [job, ...]
 
     def addJob(self, job):
-        if job not in [x.job for x in self.job_trees]:
-            t = JobTree(job)
-            self.job_trees.append(t)
-            return t
-        for tree in self.job_trees:
-            if tree.job == job:
-                return tree
-
-    def getJobs(self):
-        jobs = []
-        for x in self.job_trees:
-            jobs.append(x.job)
-            jobs.extend(x.getJobs())
-        return jobs
-
-    def getJobTreeForJob(self, job):
-        if self.job == job:
-            return self
-        for tree in self.job_trees:
-            ret = tree.getJobTreeForJob(job)
-            if ret:
-                return ret
-        return None
+        if job.name in self.jobs:
+            self.jobs[job.name].append(job)
+        else:
+            self.jobs[job.name] = [job]
 
     def inheritFrom(self, other):
-        if other.job:
-            if not self.job:
-                self.job = other.job.copy()
+        for jobname, jobs in other.jobs.items():
+            if jobname in self.jobs:
+                self.jobs[jobname].append(jobs)
             else:
-                self.job.applyVariant(other.job)
-        for other_tree in other.job_trees:
-            this_tree = self.getJobTreeForJob(other_tree.job)
-            if not this_tree:
-                this_tree = JobTree(None)
-                self.job_trees.append(this_tree)
-            this_tree.inheritFrom(other_tree)
+                self.jobs[jobname] = jobs
+
+
+class JobGraph(object):
+    """ A JobGraph represents the dependency graph between Job."""
+
+    def __init__(self):
+        self.jobs = OrderedDict()  # job_name -> Job
+        self._dependencies = {}  # dependent_job_name -> set(parent_job_names)
+
+    def __repr__(self):
+        return '<JobGraph %s>' % (self.jobs)
+
+    def addJob(self, job):
+        # A graph must be created after the job list is frozen,
+        # therefore we should only get one job with the same name.
+        if job.name in self.jobs:
+            raise Exception("Job %s already added" % (job.name,))
+        self.jobs[job.name] = job
+        # Append the dependency information
+        self._dependencies.setdefault(job.name, set())
+        try:
+            for dependency in job.dependencies:
+                # Make sure a circular dependency is never created
+                ancestor_jobs = self._getParentJobNamesRecursively(
+                    dependency, soft=True)
+                ancestor_jobs.add(dependency)
+                if any((job.name == anc_job) for anc_job in ancestor_jobs):
+                    raise Exception("Dependency cycle detected in job %s" %
+                                    (job.name,))
+                self._dependencies[job.name].add(dependency)
+        except Exception:
+            del self.jobs[job.name]
+            del self._dependencies[job.name]
+            raise
+
+    def getJobs(self):
+        return self.jobs.values()  # Report in the order of the layout config
+
+    def _getDirectDependentJobs(self, parent_job):
+        ret = set()
+        for dependent_name, parent_names in self._dependencies.items():
+            if parent_job in parent_names:
+                ret.add(dependent_name)
+        return ret
+
+    def getDependentJobsRecursively(self, parent_job):
+        all_dependent_jobs = set()
+        jobs_to_iterate = set([parent_job])
+        while len(jobs_to_iterate) > 0:
+            current_job = jobs_to_iterate.pop()
+            current_dependent_jobs = self._getDirectDependentJobs(current_job)
+            new_dependent_jobs = current_dependent_jobs - all_dependent_jobs
+            jobs_to_iterate |= new_dependent_jobs
+            all_dependent_jobs |= new_dependent_jobs
+        return [self.jobs[name] for name in all_dependent_jobs]
+
+    def getParentJobsRecursively(self, dependent_job):
+        return [self.jobs[name] for name in
+                self._getParentJobNamesRecursively(dependent_job)]
+
+    def _getParentJobNamesRecursively(self, dependent_job, soft=False):
+        all_parent_jobs = set()
+        jobs_to_iterate = set([dependent_job])
+        while len(jobs_to_iterate) > 0:
+            current_job = jobs_to_iterate.pop()
+            current_parent_jobs = self._dependencies.get(current_job)
+            if current_parent_jobs is None:
+                if soft:
+                    current_parent_jobs = set()
+                else:
+                    raise Exception("Dependent job %s not found: " %
+                                    (dependent_job,))
+            new_parent_jobs = current_parent_jobs - all_parent_jobs
+            jobs_to_iterate |= new_parent_jobs
+            all_parent_jobs |= new_parent_jobs
+        return all_parent_jobs
 
 
 class Build(object):
@@ -1137,7 +1178,7 @@
         self.active = False  # Whether an item is within an active window
         self.live = True  # Whether an item is intended to be processed at all
         self.layout = None  # This item's shadow layout
-        self.job_tree = None
+        self.job_graph = None
 
     def __repr__(self):
         if self.pipeline:
@@ -1165,23 +1206,33 @@
     def setReportedResult(self, result):
         self.current_build_set.result = result
 
-    def freezeJobTree(self):
+    def freezeJobGraph(self):
         """Find or create actual matching jobs for this item's change and
         store the resulting job tree."""
         layout = self.current_build_set.layout
-        self.job_tree = layout.createJobTree(self)
+        job_graph = layout.createJobGraph(self)
+        for job in job_graph.getJobs():
+            # Ensure that each jobs's dependencies are fully
+            # accessible.  This will raise an exception if not.
+            job_graph.getParentJobsRecursively(job.name)
+        self.job_graph = job_graph
 
-    def hasJobTree(self):
-        """Returns True if the item has a job tree."""
-        return self.job_tree is not None
+    def hasJobGraph(self):
+        """Returns True if the item has a job graph."""
+        return self.job_graph is not None
 
     def getJobs(self):
-        if not self.live or not self.job_tree:
+        if not self.live or not self.job_graph:
             return []
-        return self.job_tree.getJobs()
+        return self.job_graph.getJobs()
+
+    def getJob(self, name):
+        if not self.job_graph:
+            return None
+        return self.job_graph.jobs.get(name)
 
     def haveAllJobsStarted(self):
-        if not self.hasJobTree():
+        if not self.hasJobGraph():
             return False
         for job in self.getJobs():
             build = self.current_build_set.getBuild(job.name)
@@ -1193,7 +1244,7 @@
         if (self.current_build_set.config_error or
             self.current_build_set.unable_to_merge):
             return True
-        if not self.hasJobTree():
+        if not self.hasJobGraph():
             return False
         for job in self.getJobs():
             build = self.current_build_set.getBuild(job.name)
@@ -1202,7 +1253,7 @@
         return True
 
     def didAllJobsSucceed(self):
-        if not self.hasJobTree():
+        if not self.hasJobGraph():
             return False
         for job in self.getJobs():
             if not job.voting:
@@ -1215,7 +1266,7 @@
         return True
 
     def didAnyJobFail(self):
-        if not self.hasJobTree():
+        if not self.hasJobGraph():
             return False
         for job in self.getJobs():
             if not job.voting:
@@ -1234,7 +1285,7 @@
     def isHoldingFollowingChanges(self):
         if not self.live:
             return False
-        if not self.hasJobTree():
+        if not self.hasJobGraph():
             return False
         for job in self.getJobs():
             if not job.hold_following_changes:
@@ -1249,88 +1300,96 @@
             return False
         return self.item_ahead.isHoldingFollowingChanges()
 
-    def _findJobsToRun(self, job_trees, mutex):
+    def findJobsToRun(self, mutex):
         torun = []
+        if not self.live:
+            return []
+        if not self.job_graph:
+            return []
         if self.item_ahead:
             # Only run jobs if any 'hold' jobs on the change ahead
             # have completed successfully.
             if self.item_ahead.isHoldingFollowingChanges():
                 return []
-        for tree in job_trees:
-            job = tree.job
-            result = None
-            if job:
-                if not job.changeMatches(self.change):
+
+        successful_job_names = set()
+        jobs_not_started = set()
+        for job in self.job_graph.getJobs():
+            build = self.current_build_set.getBuild(job.name)
+            if build:
+                if build.result == 'SUCCESS':
+                    successful_job_names.add(job.name)
+            else:
+                jobs_not_started.add(job)
+
+        # Attempt to request nodes for jobs in the order jobs appear
+        # in configuration.
+        for job in self.job_graph.getJobs():
+            if job not in jobs_not_started:
+                continue
+            all_parent_jobs_successful = True
+            for parent_job in self.job_graph.getParentJobsRecursively(
+                    job.name):
+                if parent_job.name not in successful_job_names:
+                    all_parent_jobs_successful = False
+                    break
+            if all_parent_jobs_successful:
+                nodeset = self.current_build_set.getJobNodeSet(job.name)
+                if nodeset is None:
+                    # The nodes for this job are not ready, skip
+                    # it for now.
                     continue
-                build = self.current_build_set.getBuild(job.name)
-                if build:
-                    result = build.result
-                else:
-                    # There is no build for the root of this job tree,
-                    # so it has not run yet.
-                    nodeset = self.current_build_set.getJobNodeSet(job.name)
-                    if nodeset is None:
-                        # The nodes for this job are not ready, skip
-                        # it for now.
-                        continue
-                    if mutex.acquire(self, job):
-                        # If this job needs a mutex, either acquire it or make
-                        # sure that we have it before running the job.
-                        torun.append(job)
-            # If there is no job, this is a null job tree, and we should
-            # run all of its jobs.
-            if result == 'SUCCESS' or not job:
-                torun.extend(self._findJobsToRun(tree.job_trees, mutex))
+                if mutex.acquire(self, job):
+                    # If this job needs a mutex, either acquire it or make
+                    # sure that we have it before running the job.
+                    torun.append(job)
         return torun
 
-    def findJobsToRun(self, mutex):
-        if not self.live:
-            return []
-        tree = self.job_tree
-        if not tree:
-            return []
-        return self._findJobsToRun(tree.job_trees, mutex)
-
-    def _findJobsToRequest(self, job_trees):
+    def findJobsToRequest(self):
         build_set = self.current_build_set
         toreq = []
+        if not self.live:
+            return []
+        if not self.job_graph:
+            return []
         if self.item_ahead:
             if self.item_ahead.isHoldingFollowingChanges():
                 return []
-        for tree in job_trees:
-            job = tree.job
-            result = None
-            if job:
-                if not job.changeMatches(self.change):
-                    continue
-                build = build_set.getBuild(job.name)
-                if build:
-                    result = build.result
-                else:
-                    nodeset = build_set.getJobNodeSet(job.name)
-                    if nodeset is None:
-                        req = build_set.getJobNodeRequest(job.name)
-                        if req is None:
-                            toreq.append(job)
-            if result == 'SUCCESS' or not job:
-                toreq.extend(self._findJobsToRequest(tree.job_trees))
-        return toreq
 
-    def findJobsToRequest(self):
-        if not self.live:
-            return []
-        tree = self.job_tree
-        if not tree:
-            return []
-        return self._findJobsToRequest(tree.job_trees)
+        successful_job_names = set()
+        jobs_not_requested = set()
+        for job in self.job_graph.getJobs():
+            build = build_set.getBuild(job.name)
+            if build and build.result == 'SUCCESS':
+                successful_job_names.add(job.name)
+            else:
+                nodeset = build_set.getJobNodeSet(job.name)
+                if nodeset is None:
+                    req = build_set.getJobNodeRequest(job.name)
+                    if req is None:
+                        jobs_not_requested.add(job)
+
+        # Attempt to request nodes for jobs in the order jobs appear
+        # in configuration.
+        for job in self.job_graph.getJobs():
+            if job not in jobs_not_requested:
+                continue
+            all_parent_jobs_successful = True
+            for parent_job in self.job_graph.getParentJobsRecursively(
+                    job.name):
+                if parent_job.name not in successful_job_names:
+                    all_parent_jobs_successful = False
+                    break
+            if all_parent_jobs_successful:
+                toreq.append(job)
+        return toreq
 
     def setResult(self, build):
         if build.retry:
             self.removeBuild(build)
         elif build.result != 'SUCCESS':
-            # Get a JobTree from a Job so we can find only its dependent jobs
-            tree = self.job_tree.getJobTreeForJob(build.job)
-            for job in tree.getJobs():
+            for job in self.job_graph.getDependentJobsRecursively(
+                    build.job.name):
                 fakebuild = Build(job, None)
                 fakebuild.result = 'SKIPPED'
                 self.addBuild(fakebuild)
@@ -2014,7 +2073,7 @@
 class ProjectPipelineConfig(object):
     # Represents a project cofiguration in the context of a pipeline
     def __init__(self):
-        self.job_tree = None
+        self.job_list = JobList()
         self.queue_name = None
         self.merge_mode = None
 
@@ -2182,14 +2241,13 @@
     def addProjectConfig(self, project_config):
         self.project_configs[project_config.name] = project_config
 
-    def _createJobTree(self, change, job_trees, parent):
-        for tree in job_trees:
-            job = tree.job
-            if not job.changeMatches(change):
-                continue
+    def _createJobGraph(self, change, job_list, job_graph):
+        for jobname in job_list.jobs:
+            # This is the final job we are constructing
             frozen_job = None
+            # Whether the change matches any globally defined variant
             matched = False
-            for variant in self.getJobs(job.name):
+            for variant in self.getJobs(jobname):
                 if variant.changeMatches(change):
                     if frozen_job is None:
                         frozen_job = variant.copy()
@@ -2203,25 +2261,33 @@
                 # the job that is defined in the tree).
                 continue
             # If the job does not allow auth inheritance, do not allow
-            # the project-pipeline variant to update its execution
+            # the project-pipeline variants to update its execution
             # attributes.
             if frozen_job.auth and not frozen_job.auth.get('inherit'):
                 frozen_job.final = True
-            frozen_job.applyVariant(job)
-            frozen_tree = JobTree(frozen_job)
-            parent.job_trees.append(frozen_tree)
-            self._createJobTree(change, tree.job_trees, frozen_tree)
+            # Whether the change matches any of the project pipeline
+            # variants
+            matched = False
+            for variant in job_list.jobs[jobname]:
+                if variant.changeMatches(change):
+                    frozen_job.applyVariant(variant)
+                    matched = True
+            if not matched:
+                # A change must match at least one project pipeline
+                # job variant.
+                continue
+            job_graph.addJob(frozen_job)
 
-    def createJobTree(self, item):
+    def createJobGraph(self, item):
         project_config = self.project_configs.get(
             item.change.project.name, None)
-        ret = JobTree(None)
+        ret = JobGraph()
         # NOTE(pabelanger): It is possible for a foreign project not to have a
-        # configured pipeline, if so return an empty JobTree.
+        # configured pipeline, if so return an empty JobGraph.
         if project_config and item.pipeline.name in project_config.pipelines:
-            project_tree = \
-                project_config.pipelines[item.pipeline.name].job_tree
-            self._createJobTree(item.change, project_tree.job_trees, ret)
+            project_job_list = \
+                project_config.pipelines[item.pipeline.name].job_list
+            self._createJobGraph(item.change, project_job_list, ret)
         return ret
 
 
diff --git a/zuul/scheduler.py b/zuul/scheduler.py
index 131378e..7fb1568 100644
--- a/zuul/scheduler.py
+++ b/zuul/scheduler.py
@@ -555,11 +555,10 @@
                         project_name)
                     if new_pipeline.manager.reEnqueueItem(item,
                                                           last_head):
-                        new_jobs = item.getJobs()
                         for build in item.current_build_set.getBuilds():
-                            jobtree = item.job_tree.getJobTreeForJob(build.job)
-                            if jobtree and jobtree.job in new_jobs:
-                                build.job = jobtree.job
+                            new_job = item.getJob(build.job.name)
+                            if new_job:
+                                build.job = new_job
                             else:
                                 item.removeBuild(build)
                                 builds_to_cancel.append(build)