--- a/bitten/master.py
+++ b/bitten/master.py
@@ -84,7 +84,10 @@
         config = BuildConfig.fetch(self.env, build.config)
 
         if not req.args['collection']:
-            return self._process_build_initiation(req, config, build)
+            if req.method == 'DELETE':
+                return self._process_build_cancellation(req, config, build)
+            else:
+                return self._process_build_initiation(req, config, build)
 
         if req.method != 'POST':
             raise HTTPMethodNotAllowed('Method not allowed')
@@ -125,8 +128,7 @@
         build = queue.get_build_for_slave(name, properties)
         if not build:
             req.send_response(204)
-            req.send_header('Content-Type', 'text/plain')
-            req.write('No pending builds')
+            req.write('')
             raise RequestDone
 
         req.send_response(201)
@@ -135,7 +137,26 @@
         req.write('Build pending')
         raise RequestDone
 
+    def _process_build_cancellation(self, req, config, build):
+        self.log.info('Build slave %r cancelled build %d', build.slave,
+                      build.id)
+        build.status = Build.PENDING
+        build.slave = None
+        build.slave_info = {}
+        build.started = 0
+        db = self.env.get_db_cnx()
+        for step in list(BuildStep.select(self.env, build=build.id, db=db)):
+            step.delete(db=db)
+        build.update(db=db)
+        db.commit()
+
+        req.send_response(204)
+        req.write('')
+        raise RequestDone
+
     def _process_build_initiation(self, req, config, build):
+        self.log.info('Build slave %r initiated build %d', build.slave,
+                      build.id)
         build.started = int(time.time())
         build.update()
 

--- a/bitten/slave.py
+++ b/bitten/slave.py
@@ -46,6 +46,18 @@
         return response
 
 
+class SaneHTTPRequest(urllib2.Request):
+
+    def __init__(self, method, url, data=None, headers={}):
+        urllib2.Request.__init__(self, url, data, headers)
+        self.method = method
+
+    def get_method(self):
+        if self.method is None:
+            self.method = self.has_data() and 'POST' or 'GET'
+        return self.method
+
+
 class BuildSlave(object):
     """BEEP initiator implementation for the build slave."""
 
@@ -93,8 +105,8 @@
             self.opener.add_handler(urllib2.HTTPDigestAuthHandler(password_mgr))
 
     def request(self, method, url, body=None, headers=None):
-        log.debug('Sending %s request to %r', body and 'POST' or 'GET', url)
-        req = urllib2.Request(url, body, headers or {})
+        log.debug('Sending %s request to %r', method, url)
+        req = SaneHTTPRequest(method, url, body, headers or {})
         try:
             return self.opener.open(req)
         except urllib2.HTTPError, e:
@@ -152,19 +164,23 @@
         if resp.code == 201:
             self._initiate_build(resp.info().get('location'))
         elif resp.code == 204:
-            log.info(resp.read())
+            log.info('No pending builds')
         else:
             log.error('Unexpected response (%d %s)', resp.code, resp.msg)
             raise ExitSlave()
 
     def _initiate_build(self, build_url):
         log.info('Build pending at %s', build_url)
-        resp = self.request('GET', build_url)
-        if resp.code == 200:
-            self._execute_build(build_url, resp)
-        else:
-            log.error('Unexpected response (%d): %s', resp.code, resp.msg)
-            raise ExitSlave()
+        try:
+            resp = self.request('GET', build_url)
+            if resp.code == 200:
+                self._execute_build(build_url, resp)
+            else:
+                log.error('Unexpected response (%d): %s', resp.code, resp.msg)
+                self._cancel_build(build_url)
+        except KeyboardInterrupt:
+            log.warning('Build interrupted')
+            self._cancel_build(build_url)
 
     def _execute_build(self, build_url, fileobj):
         build_id = build_url and int(build_url.split('/')[-1]) or 0
@@ -204,7 +220,7 @@
                 ])
         except KeyboardInterrupt:
             log.warning('Build interrupted')
-            raise ExitSlave()
+            self._cancel_build(build_url)
         except BuildError, e:
             log.error('Build step %r failed (%s)', step.id, e)
             failed = True
@@ -220,14 +236,27 @@
             log.info('Build step %s completed successfully', step.id)
 
         if not self.local:
-            resp = self.request('POST', build_url + '/steps/', str(xml), {
-                'Content-Type': 'application/x-bitten+xml'
-            })
-            if resp.code != 201:
-                log.error('Unexpected response (%d): %s', resp.code, resp.msg)
+            try:
+                resp = self.request('POST', build_url + '/steps/', str(xml), {
+                    'Content-Type': 'application/x-bitten+xml'
+                })
+                if resp.code != 201:
+                    log.error('Unexpected response (%d): %s', resp.code,
+                              resp.msg)
+            except KeyboardInterrupt:
+                log.warning('Build interrupted')
+                self._cancel_build(build_url)
 
         return not failed or step.onerror != 'fail'
 
+    def _cancel_build(self, build_url):
+        log.info('Cancelling build at %s', build_url)
+        if not self.local:
+            resp = self.request('DELETE', build_url)
+            if resp.code not in (200, 204):
+                log.error('Unexpected response (%d): %s', resp.code, resp.msg)
+        raise ExitSlave()
+
 
 class ExitSlave(Exception):
     """Exception used internally by the slave to signal that the slave process

--- a/bitten/tests/master.py
+++ b/bitten/tests/master.py
@@ -151,8 +151,39 @@
             self.fail('Expected RequestDone')
         except RequestDone:
             self.assertEqual(204, outheaders['Status'])
-            self.assertEqual('text/plain', outheaders['Content-Type'])
-            self.assertEqual('No pending builds', outbody.getvalue())
+            self.assertEqual('', outbody.getvalue())
+
+    def test_cancel_build(self):
+        config = BuildConfig(self.env, 'test', path='somepath', active=True,
+                             recipe='<build></build>')
+        config.insert()
+        build = Build(self.env, 'test', '123', 1, slave='hal', rev_time=42,
+                      status=Build.IN_PROGRESS, started=42)
+        build.insert()
+
+        outheaders = {}
+        outbody = StringIO()
+        req = Mock(method='DELETE', base_path='',
+                   path_info='/builds/%d' % build.id,
+                   href=Href('/trac'), remote_addr='127.0.0.1', args={},
+                   perm=PermissionCache(self.env, 'hal'),
+                   send_response=lambda x: outheaders.setdefault('Status', x),
+                   send_header=lambda x, y: outheaders.setdefault(x, y),
+                   write=outbody.write)
+
+        module = BuildMaster(self.env)
+        assert module.match_request(req)
+        try:
+            module.process_request(req)
+            self.fail('Expected RequestDone')
+        except RequestDone:
+            self.assertEqual(204, outheaders['Status'])
+            self.assertEqual('', outbody.getvalue())
+
+            # Make sure the started timestamp has been set
+            build = Build.fetch(self.env, build.id)
+            self.assertEqual(Build.PENDING, build.status)
+            assert not build.started
 
     def test_initiate_build(self):
         config = BuildConfig(self.env, 'test', path='somepath', active=True,