diff --git a/cloud/bmaas/bmdb/model/migrations/1672743627_installation_tags.down.sql b/cloud/bmaas/bmdb/model/migrations/1672743627_installation_tags.down.sql
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/cloud/bmaas/bmdb/model/migrations/1672743627_installation_tags.down.sql
diff --git a/cloud/bmaas/bmdb/model/migrations/1672743627_installation_tags.up.sql b/cloud/bmaas/bmdb/model/migrations/1672743627_installation_tags.up.sql
new file mode 100644
index 0000000..37f7b3a
--- /dev/null
+++ b/cloud/bmaas/bmdb/model/migrations/1672743627_installation_tags.up.sql
@@ -0,0 +1,19 @@
+CREATE TABLE machine_os_installation_request (
+    machine_id UUID NOT NULL REFERENCES machines(machine_id) ON DELETE RESTRICT,
+    -- Version of this request, for example monotonic epoch counter. Used to
+    -- match successful installation (represented by OS installation report) to
+    -- pending request, making sure that we don't perform spurious re-installs.
+    generation INT NOT NULL,
+    -- Serialized cloud.bmaas.server.api.OSInstallationRequest.
+    os_installation_request_raw BYTEA NOT NULL,
+    CONSTRAINT "primary" PRIMARY KEY (machine_id)
+);
+
+CREATE TABLE machine_os_installation_report (
+    machine_id UUID NOT NULL REFERENCES machines(machine_id) ON DELETE RESTRICT,
+    -- Matches generation in machine_os_installation_request. Not constrained on
+    -- purpose, as a mismatch between generations implies an actionable
+    -- installation request and is a valid state of the system.
+    generation INT NOT NULL,
+    CONSTRAINT "primary" PRIMARY KEY (machine_id)
+);
diff --git a/cloud/bmaas/bmdb/model/queries.sql b/cloud/bmaas/bmdb/model/queries.sql
index 4e32cff..8f40aac 100644
--- a/cloud/bmaas/bmdb/model/queries.sql
+++ b/cloud/bmaas/bmdb/model/queries.sql
@@ -42,8 +42,6 @@
   AND session_id = $2
   AND process = $3;
 
--- Example tag processing queries follow.
-
 -- name: MachineAddProvided :exec
 INSERT INTO machine_provided (
     machine_id, provider, provider_id
@@ -79,6 +77,25 @@
     hardware_report_raw = $2
 ;
 
+-- name: MachineSetOSInstallationRequest :exec
+INSERT INTO machine_os_installation_request (
+    machine_id, generation, os_installation_request_raw
+) VALUES (
+    $1, $2, $3
+) ON CONFLICT (machine_id) DO UPDATE SET
+    generation = $2,
+    os_installation_request_raw = $3
+;
+
+-- name: MachineSetOSInstallationReport :exec
+INSERT INTO machine_os_installation_report (
+    machine_id, generation
+) VALUES (
+    $1, $2
+) ON CONFLICT (machine_id) DO UPDATE SET
+    generation = $2
+;
+
 -- name: GetMachinesForAgentStart :many
 -- Get machines that need agent installed for the first time. Machine can be
 -- assumed to be 'new', with no previous attempts or failures.
@@ -126,6 +143,25 @@
   AND work.machine_id IS NULL
 LIMIT $1;
 
+-- name: GetExactMachineForOSInstallation :many
+SELECT
+    machine_os_installation_request.*
+FROM machines
+LEFT JOIN machine_os_installation_request ON machines.machine_id = machine_os_installation_request.machine_id
+LEFT JOIN machine_os_installation_report ON machines.machine_id = machine_os_installation_report.machine_id
+WHERE
+    -- We are only interested in one concrete machine.
+    machines.machine_id = $1
+    -- We must have an installation request.
+    AND machine_os_installation_request.machine_id IS NOT NULL
+    -- And we either must have no installation report, or the installation
+    -- report's generation must not match the installation request's generation.
+    AND (
+        machine_os_installation_report.machine_id IS NULL
+        OR machine_os_installation_report.generation != machine_os_installation_request.generation
+    )
+LIMIT $2;
+
 -- name: AuthenticateAgentConnection :many
 SELECT
     machine_agent_started.*
@@ -133,4 +169,4 @@
 INNER JOIN machine_agent_started ON machines.machine_id = machine_agent_started.machine_id
 WHERE
     machines.machine_id = $1
-    AND machine_agent_started.agent_public_key = $2;
\ No newline at end of file
+    AND machine_agent_started.agent_public_key = $2;