diff --git a/update_manager/chromeos_policy.cc b/update_manager/chromeos_policy.cc
index fc39bd7..9afc00d 100644
--- a/update_manager/chromeos_policy.cc
+++ b/update_manager/chromeos_policy.cc
@@ -21,6 +21,7 @@
 using base::Time;
 using base::TimeDelta;
 using chromeos_update_engine::ErrorCode;
+using std::get;
 using std::max;
 using std::min;
 using std::set;
@@ -28,12 +29,13 @@
 
 namespace {
 
-// Increment |url_idx|, |url_num_failures| or none of them based on the provided
-// error code. If |url_idx| is incremented, then sets |url_num_failures| to zero
-// and returns true; otherwise, returns false.
+// Examines |err_code| and decides whether the URL index needs to be advanced,
+// the error count for the URL incremented, or none of the above. In the first
+// case, returns true; in the second case, increments |*url_num_error_p| and
+// returns false; otherwise just returns false.
 //
 // TODO(garnold) Adapted from PayloadState::UpdateFailed() (to be retired).
-bool HandleErrorCode(ErrorCode err_code, int* url_idx, int* url_num_failures) {
+bool HandleErrorCode(ErrorCode err_code, int* url_num_error_p) {
   err_code = chromeos_update_engine::utils::GetBaseErrorCode(err_code);
   switch (err_code) {
     // Errors which are good indicators of a problem with a particular URL or
@@ -64,8 +66,6 @@
       LOG(INFO) << "Advancing download URL due to error "
                 << chromeos_update_engine::utils::CodeToString(err_code)
                 << " (" << static_cast<int>(err_code) << ")";
-      *url_idx += 1;
-      *url_num_failures = 0;
       return true;
 
     // Errors which seem to be just transient network/communication related
@@ -84,7 +84,7 @@
       LOG(INFO) << "Incrementing URL failure count due to error "
                 << chromeos_update_engine::utils::CodeToString(err_code)
                 << " (" << static_cast<int>(err_code) << ")";
-      *url_num_failures += 1;
+      *url_num_error_p += 1;
       return false;
 
     // Errors which are not specific to a URL and hence shouldn't result in
@@ -141,9 +141,9 @@
   return false;
 }
 
-// Checks whether |download_url| can be used under given download restrictions.
-bool DownloadUrlIsUsable(const string& download_url, bool http_allowed) {
-  return http_allowed || !StartsWithASCII(download_url, "http://", false);
+// Checks whether |url| can be used under given download restrictions.
+bool IsUrlUsable(const string& url, bool http_allowed) {
+  return http_allowed || !StartsWithASCII(url, "http://", false);
 }
 
 }  // namespace
@@ -154,6 +154,8 @@
 const int ChromeOSPolicy::kTimeoutPeriodicInterval = 45 * 60;
 const int ChromeOSPolicy::kTimeoutMaxBackoffInterval = 4 * 60 * 60;
 const int ChromeOSPolicy::kTimeoutRegularFuzz = 10 * 60;
+const int ChromeOSPolicy::kAttemptBackoffMaxIntervalInDays = 16;
+const int ChromeOSPolicy::kAttemptBackoffFuzzInHours = 12;
 
 EvalStatus ChromeOSPolicy::UpdateCheckAllowed(
     EvaluationContext* ec, State* state, string* error,
@@ -265,16 +267,20 @@
     State* state,
     string* error,
     UpdateDownloadParams* result,
-    const bool interactive,
     const UpdateState& update_state) const {
-  // Set the default return values.
+  // Set the default return values. Note that we set persisted values (backoff,
+  // scattering) to the same values presented in the update state. The reason is
+  // that preemptive returns, such as the case where an update check is due,
+  // should not clear off the said values; rather, it is the deliberate
+  // inference of new values that should cause them to be reset.
   result->update_can_start = true;
-  result->p2p_allowed = false;
   result->cannot_start_reason = UpdateCannotStartReason::kUndefined;
-  result->scatter_wait_period = kZeroInterval;
-  result->scatter_check_threshold = 0;
   result->download_url_idx = -1;
-  result->download_url_num_failures = 0;
+  result->p2p_allowed = false;
+  result->do_increment_failures = false;
+  result->backoff_expiry = update_state.backoff_expiry;
+  result->scatter_wait_period = update_state.scatter_wait_period;
+  result->scatter_check_threshold = update_state.scatter_check_threshold;
 
   // Make sure that we're not due for an update check.
   UpdateCheckParams check_result;
@@ -288,6 +294,27 @@
     return EvalStatus::kSucceeded;
   }
 
+  // Check whether backoff applies, and if not then which URL can be used for
+  // downloading. These require scanning the download error log, and so they are
+  // done together.
+  UpdateBackoffAndDownloadUrlResult backoff_url_result;
+  EvalStatus backoff_url_status = UpdateBackoffAndDownloadUrl(
+      ec, state, error, &backoff_url_result, update_state);
+  if (backoff_url_status != EvalStatus::kFailed) {
+    result->download_url_idx = backoff_url_result.url_idx;
+    result->download_url_num_errors = backoff_url_result.url_num_errors;
+    result->do_increment_failures = backoff_url_result.do_increment_failures;
+    result->backoff_expiry = backoff_url_result.backoff_expiry;
+  }
+  if (backoff_url_status != EvalStatus::kSucceeded ||
+      !backoff_url_result.backoff_expiry.is_null()) {
+    if (backoff_url_status != EvalStatus::kFailed) {
+      result->update_can_start = false;
+      result->cannot_start_reason = UpdateCannotStartReason::kBackoff;
+    }
+    return backoff_url_status;
+  }
+
   DevicePolicyProvider* const dp_provider = state->device_policy_provider();
 
   const bool* device_policy_is_loaded_p = ec->GetValue(
@@ -302,7 +329,9 @@
     // presence of this attribute is merely indicative of an OOBE update, during
     // which we suppress scattering anyway.
     bool scattering_applies = false;
-    if (!interactive) {
+    result->scatter_wait_period = kZeroInterval;
+    result->scatter_check_threshold = 0;
+    if (!update_state.is_interactive) {
       const bool* is_oobe_enabled_p = ec->GetValue(
           state->config_provider()->var_is_oobe_enabled());
       if (is_oobe_enabled_p && !(*is_oobe_enabled_p)) {
@@ -344,21 +373,12 @@
     result->p2p_allowed = updater_p2p_enabled_p && *updater_p2p_enabled_p;
   }
 
-  // Determine the URL to download the update from. Note that a failure to find
-  // a download URL will only fail this policy iff no other means of download
-  // (such as P2P) are enabled.
-  UpdateDownloadUrlResult download_url_result;
-  EvalStatus download_url_status = UpdateDownloadUrl(
-      ec, state, error, &download_url_result, update_state);
-  if (download_url_status == EvalStatus::kSucceeded) {
-    result->download_url_idx = download_url_result.url_idx;
-    result->download_url_num_failures = download_url_result.url_num_failures;
-  } else if (!result->p2p_allowed) {
-    if (download_url_status != EvalStatus::kFailed) {
-      result->update_can_start = false;
-      result->cannot_start_reason = UpdateCannotStartReason::kCannotDownload;
-    }
-    return download_url_status;
+  // Store the download URL and failure increment flag. Note that no URL will
+  // only terminate evaluation if no other means of download (such as P2P) are
+  // enabled.
+  if (result->download_url_idx < 0 && !result->p2p_allowed) {
+    result->update_can_start = false;
+    result->cannot_start_reason = UpdateCannotStartReason::kCannotDownload;
   }
 
   return EvalStatus::kSucceeded;
@@ -537,29 +557,48 @@
   return TimeDelta::FromSeconds(prng->RandMinMax(interval_min, interval_max));
 }
 
-EvalStatus ChromeOSPolicy::UpdateDownloadUrl(
+EvalStatus ChromeOSPolicy::UpdateBackoffAndDownloadUrl(
     EvaluationContext* ec, State* state, std::string* error,
-    UpdateDownloadUrlResult* result, const UpdateState& update_state) const {
-  int url_idx = 0;
-  int url_num_failures = 0;
-  if (update_state.num_checks > 1) {
-    // Ignore negative URL indexes, which indicate that no previous suitable
-    // download URL was found.
-    url_idx = max(0, update_state.download_url_idx);
-    url_num_failures = update_state.download_url_num_failures;
+    UpdateBackoffAndDownloadUrlResult* result,
+    const UpdateState& update_state) const {
+  // Sanity checks.
+  DCHECK_GE(update_state.download_errors_max, 0);
+
+  // Set default result values.
+  result->do_increment_failures = false;
+  result->backoff_expiry = update_state.backoff_expiry;
+  result->url_idx = -1;
+  result->url_num_errors = 0;
+
+  const bool* is_official_build_p = ec->GetValue(
+      state->system_provider()->var_is_official_build());
+  bool is_official_build = (is_official_build_p ? *is_official_build_p : true);
+
+  // Check whether backoff is enabled.
+  bool may_backoff = false;
+  if (update_state.is_backoff_disabled) {
+    LOG(INFO) << "Backoff disabled by Omaha.";
+  } else if (update_state.is_interactive) {
+    LOG(INFO) << "No backoff for interactive updates.";
+  } else if (update_state.is_delta_payload) {
+    LOG(INFO) << "No backoff for delta payloads.";
+  } else if (!is_official_build) {
+    LOG(INFO) << "No backoff for unofficial builds.";
+  } else {
+    may_backoff = true;
   }
 
-  // Preconditions / sanity checks.
-  DCHECK_GE(update_state.download_failures_max, 0);
-  DCHECK_LT(url_idx, static_cast<int>(update_state.download_urls.size()));
-  DCHECK_LE(url_num_failures, update_state.download_failures_max);
+  // If previous backoff still in effect, block.
+  if (may_backoff && !update_state.backoff_expiry.is_null() &&
+      !ec->IsWallclockTimeGreaterThan(update_state.backoff_expiry)) {
+    LOG(INFO) << "Previous backoff has not expired, waiting.";
+    return EvalStatus::kAskMeAgainLater;
+  }
 
   // Determine whether HTTP downloads are forbidden by policy. This only
   // applies to official system builds; otherwise, HTTP is always enabled.
   bool http_allowed = true;
-  const bool* is_official_build_p = ec->GetValue(
-      state->system_provider()->var_is_official_build());
-  if (is_official_build_p && *is_official_build_p) {
+  if (is_official_build) {
     DevicePolicyProvider* const dp_provider = state->device_policy_provider();
     const bool* device_policy_is_loaded_p = ec->GetValue(
         dp_provider->var_device_policy_is_loaded());
@@ -571,30 +610,140 @@
     }
   }
 
-  // Process recent failures, stop if the URL index advances.
-  for (auto& err_code : update_state.download_url_error_codes) {
-    if (HandleErrorCode(err_code, &url_idx, &url_num_failures))
-      break;
-    if (url_num_failures > update_state.download_failures_max) {
-      url_idx++;
-      url_num_failures = 0;
-      break;
+  int url_idx = update_state.last_download_url_idx;
+  if (url_idx < 0)
+    url_idx = -1;
+  bool do_advance_url = false;
+  bool is_failure_occurred = false;
+  Time err_time;
+
+  // Scan the relevant part of the download error log, tracking which URLs are
+  // being used, and accounting the number of errors for each URL. Note that
+  // this process may not traverse all errors provided, as it may decide to bail
+  // out midway depending on the particular errors exhibited, the number of
+  // failures allowed, etc. When this ends, |url_idx| will point to the last URL
+  // used (-1 if starting fresh), |do_advance_url| will determine whether the
+  // URL needs to be advanced, and |err_time| the point in time when the last
+  // reported error occurred.  Additionally, if the error log indicates that an
+  // update attempt has failed (abnormal), then |is_failure_occurred| will be
+  // set to true.
+  const int num_urls = update_state.download_urls.size();
+  int prev_url_idx = -1;
+  int url_num_errors = update_state.last_download_url_num_errors;
+  Time prev_err_time;
+  bool is_first = true;
+  for (const auto& err_tuple : update_state.download_errors) {
+    // Do some sanity checks.
+    int used_url_idx = get<0>(err_tuple);
+    if (is_first && url_idx >= 0 && used_url_idx != url_idx) {
+      LOG(WARNING) << "First URL in error log (" << used_url_idx
+                   << ") not as expected (" << url_idx << ")";
     }
-  }
-  url_idx %= update_state.download_urls.size();
+    is_first = false;
+    url_idx = used_url_idx;
+    if (url_idx < 0 || url_idx >= num_urls) {
+      LOG(ERROR) << "Download error log contains an invalid URL index ("
+                 << url_idx << ")";
+      return EvalStatus::kFailed;
+    }
+    err_time = get<2>(err_tuple);
+    if (!(prev_err_time.is_null() || err_time >= prev_err_time)) {
+      // TODO(garnold) Monotonicity cannot really be assumed when dealing with
+      // wallclock-based timestamps. However, we're making a simplifying
+      // assumption so as to keep the policy implementation straightforward, for
+      // now. In general, we should convert all timestamp handling in the
+      // UpdateManager to use monotonic time (instead of wallclock), including
+      // the computation of various expiration times (backoff, scattering, etc).
+      // The client will do whatever conversions necessary when
+      // persisting/retrieving these values across reboots. See chromium:408794.
+      LOG(ERROR) << "Download error timestamps not monotonically increasing.";
+      return EvalStatus::kFailed;
+    }
+    prev_err_time = err_time;
 
-  // Scan through URLs until a usable one is found.
-  const int start_url_idx = url_idx;
-  while (!DownloadUrlIsUsable(update_state.download_urls[url_idx],
-                              http_allowed)) {
-    url_idx = (url_idx + 1) % update_state.download_urls.size();
-    url_num_failures = 0;
-    if (url_idx == start_url_idx)
-      return EvalStatus::kFailed;  // No usable URLs.
+    // Ignore errors that happened before the last known failed attempt.
+    if (!update_state.failures_last_updated.is_null() &&
+        err_time <= update_state.failures_last_updated)
+      continue;
+
+    if (prev_url_idx >= 0) {
+      if (url_idx < prev_url_idx) {
+        LOG(ERROR) << "The URLs in the download error log have wrapped around ("
+                   << prev_url_idx << "->" << url_idx
+                   << "). This should not have happened and means that there's "
+                      "a bug. To be conservative, we record a failed attempt "
+                      "(invalidating the rest of the error log) and resume "
+                      "download from the first usable URL.";
+        url_idx = -1;
+        is_failure_occurred = true;
+        break;
+      }
+
+      if (url_idx > prev_url_idx) {
+        url_num_errors = 0;
+        do_advance_url = false;
+      }
+    }
+
+    if (HandleErrorCode(get<1>(err_tuple), &url_num_errors) ||
+        url_num_errors > update_state.download_errors_max)
+      do_advance_url = true;
+
+    prev_url_idx = url_idx;
   }
 
+  // If required, advance to the next usable URL. If the URLs wraparound, we
+  // mark an update attempt failure. Also be sure to set the download error
+  // count to zero.
+  if (url_idx < 0 || do_advance_url) {
+    url_num_errors = 0;
+    int start_url_idx = -1;
+    do {
+      if (++url_idx == num_urls) {
+        url_idx = 0;
+        // We only mark failure if an actual advancing of a URL was required.
+        if (do_advance_url)
+          is_failure_occurred = true;
+      }
+
+      if (start_url_idx < 0)
+        start_url_idx = url_idx;
+      else if (url_idx == start_url_idx)
+        url_idx = -1;  // No usable URL.
+    } while (url_idx >= 0 &&
+             !IsUrlUsable(update_state.download_urls[url_idx], http_allowed));
+  }
+
+  // If we have a download URL but a failure was observed, compute a new backoff
+  // expiry (if allowed). The backoff period is generally 2 ^ (num_failures - 1)
+  // days, bounded by the size of int and kAttemptBackoffMaxIntervalInDays, and
+  // fuzzed by kAttemptBackoffFuzzInHours hours. Backoff expiry is computed from
+  // the latest recorded time of error.
+  Time backoff_expiry;
+  if (url_idx >= 0 && is_failure_occurred && may_backoff) {
+    CHECK(!err_time.is_null())
+        << "We must have an error timestamp if a failure occurred!";
+    const uint64_t* seed = ec->GetValue(state->random_provider()->var_seed());
+    POLICY_CHECK_VALUE_AND_FAIL(seed, error);
+    PRNG prng(*seed);
+    int exp = std::min(update_state.num_failures,
+                       static_cast<int>(sizeof(int)) * 8 - 2);
+    TimeDelta backoff_interval = TimeDelta::FromDays(
+        std::min(1 << exp, kAttemptBackoffMaxIntervalInDays));
+    TimeDelta backoff_fuzz = TimeDelta::FromHours(kAttemptBackoffFuzzInHours);
+    TimeDelta wait_period = FuzzedInterval(&prng, backoff_interval.InSeconds(),
+                                           backoff_fuzz.InSeconds());
+    backoff_expiry = err_time + wait_period;
+
+    // If the newly computed backoff already expired, nullify it.
+    if (ec->IsWallclockTimeGreaterThan(backoff_expiry))
+      backoff_expiry = Time();
+  }
+
+  result->do_increment_failures = is_failure_occurred;
+  result->backoff_expiry = backoff_expiry;
   result->url_idx = url_idx;
-  result->url_num_failures = url_num_failures;
+  result->url_num_errors = url_num_errors;
   return EvalStatus::kSucceeded;
 }
 
@@ -642,7 +791,7 @@
         prng.RandMinMax(1, scatter_factor_p->InSeconds()));
   }
 
-  // If we surpass the wait period or the max scatter period associated with
+  // If we surpassed the wait period or the max scatter period associated with
   // the update, then no wait is needed.
   Time wait_expires = (update_state.first_seen +
                        min(wait_period, update_state.scatter_wait_period_max));
diff --git a/update_manager/chromeos_policy.h b/update_manager/chromeos_policy.h
index 846bf57..8b858a2 100644
--- a/update_manager/chromeos_policy.h
+++ b/update_manager/chromeos_policy.h
@@ -15,13 +15,21 @@
 
 namespace chromeos_update_manager {
 
-// Parameters for update download URL, as determined by UpdateDownloadUrl.
-struct UpdateDownloadUrlResult {
+// Output information from UpdateBackoffAndDownloadUrl.
+struct UpdateBackoffAndDownloadUrlResult {
+  // Whether the failed attempt count (maintained by the caller) needs to be
+  // incremented.
+  bool do_increment_failures;
+  // The current backoff expiry. Null if backoff is not in effect.
+  base::Time backoff_expiry;
+  // The new URL index to use and number of download errors associated with it.
+  // Significant iff |do_increment_failures| is false and |backoff_expiry| is
+  // null. Negative value means no usable URL was found.
   int url_idx;
-  int url_num_failures;
+  int url_num_errors;
 };
 
-// Parameters for update scattering, as determined by UpdateNotScattering.
+// Parameters for update scattering, as returned by UpdateScattering.
 struct UpdateScatteringResult {
   bool is_scattering;
   base::TimeDelta wait_period;
@@ -44,7 +52,6 @@
       State* state,
       std::string* error,
       UpdateDownloadParams* result,
-      const bool interactive,
       const UpdateState& update_state) const override;
 
   EvalStatus UpdateDownloadAllowed(
@@ -90,6 +97,10 @@
   static const int kTimeoutMaxBackoffInterval;
   static const int kTimeoutRegularFuzz;
 
+  // Maximum update attempt backoff interval and fuzz.
+  static const int kAttemptBackoffMaxIntervalInDays;
+  static const int kAttemptBackoffFuzzInHours;
+
   // A private policy implementation returning the wallclock timestamp when
   // the next update check should happen.
   // TODO(garnold) We should probably change that to infer a monotonic
@@ -105,21 +116,33 @@
   // TimeDelta.
   static base::TimeDelta FuzzedInterval(PRNG* prng, int interval, int fuzz);
 
-  // A private policy for determining which download URL to use. Within
-  // |update_state|, |download_urls| should contain the download URLs as listed
-  // in the Omaha response; |download_failures_max| the maximum number of
-  // failures per URL allowed per the response; |download_url_idx| the index of
-  // the previously used URL; |download_url_num_failures| the previously known
-  // number of failures associated with that URL; and |download_url_error_codes|
-  // the list of failures occurring since the latest evaluation.
+  // A private policy for determining backoff and the download URL to use.
+  // Within |update_state|, |backoff_expiry| and |is_backoff_disabled| are used
+  // for determining whether backoff is still in effect; if not,
+  // |download_errors| is scanned past |failures_last_updated|, and a new
+  // download URL from |download_urls| is found and written to |result->url_idx|
+  // (-1 means no usable URL exists); |download_errors_max| determines the
+  // maximum number of attempts per URL, according to the Omaha response. If an
+  // update failure is identified then |result->do_increment_failures| is set to
+  // true; if backoff is enabled, a new backoff period is computed (from the
+  // time of failure) based on |num_failures|. Otherwise, backoff expiry is
+  // nullified, indicating that no backoff is in effect.
   //
-  // Upon successfully deciding a URL to use, returns |EvalStatus::kSucceeded|
-  // and writes the current URL index and the number of failures associated with
-  // it in |result|. Otherwise, returns |EvalStatus::kFailed|.
-  EvalStatus UpdateDownloadUrl(EvaluationContext* ec, State* state,
-                               std::string* error,
-                               UpdateDownloadUrlResult* result,
-                               const UpdateState& update_state) const;
+  // If backing off but the previous backoff expiry is unchanged, returns
+  // |EvalStatus::kAskMeAgainLater|. Otherwise:
+  //
+  // * If backing off with a new expiry time, then |result->backoff_expiry| is
+  //   set to this time.
+  //
+  // * Else, |result->backoff_expiry| is set to null, indicating that no backoff
+  //   is in effect.
+  //
+  // In any of these cases, returns |EvalStatus::kSucceeded|. If an error
+  // occurred, returns |EvalStatus::kFailed|.
+  EvalStatus UpdateBackoffAndDownloadUrl(
+      EvaluationContext* ec, State* state, std::string* error,
+      UpdateBackoffAndDownloadUrlResult* result,
+      const UpdateState& update_state) const;
 
   // A private policy for checking whether scattering is due. Writes in |result|
   // the decision as to whether or not to scatter; a wallclock-based scatter
diff --git a/update_manager/chromeos_policy_unittest.cc b/update_manager/chromeos_policy_unittest.cc
index 25a091e..e3f7acf 100644
--- a/update_manager/chromeos_policy_unittest.cc
+++ b/update_manager/chromeos_policy_unittest.cc
@@ -6,6 +6,7 @@
 
 #include <set>
 #include <string>
+#include <tuple>
 #include <vector>
 
 #include <base/time/time.h>
@@ -20,8 +21,10 @@
 using base::TimeDelta;
 using chromeos_update_engine::ErrorCode;
 using chromeos_update_engine::FakeClock;
+using std::make_tuple;
 using std::set;
 using std::string;
+using std::tuple;
 using std::vector;
 
 namespace chromeos_update_manager {
@@ -118,17 +121,39 @@
     fake_clock_.SetWallclockTime(curr_time);
   }
 
-  // Returns a default UpdateState structure: first seen time is calculated
-  // backward from the current wall clock time, update was seen just once;
-  // there's a single HTTP download URL with a maximum of 10 allowed failures;
-  // there is no scattering wait period and the max allowed is 7 days, there is
-  // no check threshold and none is allowed.
-  UpdateState GetDefaultUpdateState(TimeDelta update_first_seen_period) {
-    UpdateState update_state = {
-      fake_clock_.GetWallclockTime() - update_first_seen_period, 1,
-      vector<string>(1, "http://fake/url/"), 10, 0, 0, vector<ErrorCode>(),
-      TimeDelta(), TimeDelta::FromDays(7), 0, 0, 0
-    };
+  // Returns a default UpdateState structure:
+  UpdateState GetDefaultUpdateState(TimeDelta first_seen_period) {
+    Time first_seen_time = fake_clock_.GetWallclockTime() - first_seen_period;
+    UpdateState update_state = UpdateState();
+
+    // This is a non-interactive check returning a delta payload, seen for the
+    // first time (|first_seen_period| ago). Clearly, there were no failed
+    // attempts so far.
+    update_state.is_interactive = false;
+    update_state.is_delta_payload = false;
+    update_state.first_seen = first_seen_time;
+    update_state.num_checks = 1;
+    update_state.num_failures = 0;
+    update_state.failures_last_updated = Time();  // Needs to be zero.
+    // There's a single HTTP download URL with a maximum of 10 retries.
+    update_state.download_urls = vector<string>{"http://fake/url/"};
+    update_state.download_errors_max = 10;
+    // Download was never attempted.
+    update_state.last_download_url_idx = -1;
+    update_state.last_download_url_num_errors = 0;
+    // There were no download errors.
+    update_state.download_errors = vector<tuple<int, ErrorCode, Time>>();
+    // No active backoff period, backoff is not disabled by Omaha.
+    update_state.backoff_expiry = Time();
+    update_state.is_backoff_disabled = false;
+    // There is no active scattering wait period (max 7 days allowed) nor check
+    // threshold (none allowed).
+    update_state.scatter_wait_period = TimeDelta();
+    update_state.scatter_check_threshold = 0;
+    update_state.scatter_wait_period_max = TimeDelta::FromDays(7);
+    update_state.scatter_check_threshold_min = 0;
+    update_state.scatter_check_threshold_max = 0;
+
     return update_state;
   }
 
@@ -436,7 +461,7 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kFailed,
-                     &Policy::UpdateCanStart, &result, false, update_state);
+                     &Policy::UpdateCanStart, &result, update_state);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartNotAllowedCheckDue) {
@@ -449,7 +474,7 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded,
-                     &Policy::UpdateCanStart, &result, false, update_state);
+                     &Policy::UpdateCanStart, &result, update_state);
   EXPECT_FALSE(result.update_can_start);
   EXPECT_EQ(UpdateCannotStartReason::kCheckDue, result.cannot_start_reason);
 }
@@ -465,11 +490,12 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded,
-                     &Policy::UpdateCanStart, &result, false, update_state);
+                     &Policy::UpdateCanStart, &result, update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedBlankPolicy) {
@@ -482,11 +508,223 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded,
-                     &Policy::UpdateCanStart, &result, false, update_state);
+                     &Policy::UpdateCanStart, &result, update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
+}
+
+TEST_F(UmChromeOSPolicyTest,
+       UpdateCanStartNotAllowedBackoffNewWaitPeriodApplies) {
+  // The UpdateCanStart policy returns false; failures are reported and a new
+  // backoff period is enacted.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_FALSE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kBackoff, result.cannot_start_reason);
+  EXPECT_TRUE(result.do_increment_failures);
+  EXPECT_LT(curr_time, result.backoff_expiry);
+}
+
+TEST_F(UmChromeOSPolicyTest,
+       UpdateCanStartNotAllowedBackoffPrevWaitPeriodStillApplies) {
+  // The UpdateCanStart policy returns false; a previously enacted backoff
+  // period still applies.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+  update_state.failures_last_updated = curr_time;
+  update_state.backoff_expiry = curr_time + TimeDelta::FromMinutes(3);
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kAskMeAgainLater, &Policy::UpdateCanStart,
+                     &result, update_state);
+  EXPECT_FALSE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kBackoff, result.cannot_start_reason);
+  EXPECT_FALSE(result.do_increment_failures);
+  EXPECT_LT(curr_time, result.backoff_expiry);
+}
+
+TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedBackoffSatisfied) {
+  // The UpdateCanStart policy returns true; a previously enacted backoff period
+  // has elapsed, we're good to go.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+  update_state.failures_last_updated = curr_time - TimeDelta::FromSeconds(1);
+  update_state.backoff_expiry = curr_time - TimeDelta::FromSeconds(1);
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart,
+                     &result, update_state);
+  EXPECT_TRUE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kUndefined, result.cannot_start_reason);
+  EXPECT_EQ(0, result.download_url_idx);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
+  EXPECT_EQ(Time(), result.backoff_expiry);
+}
+
+TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedBackoffDisabled) {
+  // The UpdateCanStart policy returns false; failures are reported but backoff
+  // is disabled.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+  update_state.is_backoff_disabled = true;
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_TRUE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kUndefined, result.cannot_start_reason);
+  EXPECT_EQ(0, result.download_url_idx);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_TRUE(result.do_increment_failures);
+  EXPECT_EQ(Time(), result.backoff_expiry);
+}
+
+TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedNoBackoffInteractive) {
+  // The UpdateCanStart policy returns false; failures are reported but this is
+  // an interactive update check.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+  update_state.is_interactive = true;
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_TRUE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kUndefined, result.cannot_start_reason);
+  EXPECT_EQ(0, result.download_url_idx);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_TRUE(result.do_increment_failures);
+  EXPECT_EQ(Time(), result.backoff_expiry);
+}
+
+TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedNoBackoffDelta) {
+  // The UpdateCanStart policy returns false; failures are reported but this is
+  // a delta payload.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+  update_state.is_delta_payload = true;
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_TRUE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kUndefined, result.cannot_start_reason);
+  EXPECT_EQ(0, result.download_url_idx);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_TRUE(result.do_increment_failures);
+  EXPECT_EQ(Time(), result.backoff_expiry);
+}
+
+TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedNoBackoffUnofficialBuild) {
+  // The UpdateCanStart policy returns false; failures are reported but this is
+  // an unofficial build.
+
+  SetUpdateCheckAllowed(false);
+
+  const Time curr_time = fake_clock_.GetWallclockTime();
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(10));
+  update_state.download_errors_max = 1;
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(8));
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kDownloadTransferError,
+      curr_time - TimeDelta::FromSeconds(2));
+
+  fake_state_.system_provider()->var_is_official_build()->
+      reset(new bool(false));
+
+  // Check that UpdateCanStart returns false and a new backoff expiry is
+  // generated.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_TRUE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kUndefined, result.cannot_start_reason);
+  EXPECT_EQ(0, result.download_url_idx);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_TRUE(result.do_increment_failures);
+  EXPECT_EQ(Time(), result.backoff_expiry);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartFailsScatteringFailed) {
@@ -497,13 +735,16 @@
 
   // Override the default seed variable with a null value so that the policy
   // request would fail.
+  // TODO(garnold) This failure may or may not fail a number
+  // sub-policies/decisions, like scattering and backoff. We'll need a more
+  // deliberate setup to ensure that we're failing what we want to be failing.
   fake_state_.random_provider()->var_seed()->reset(nullptr);
 
   // Check that the UpdateCanStart fails.
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(1));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kFailed,
-                     &Policy::UpdateCanStart, &result, false, update_state);
+                     &Policy::UpdateCanStart, &result, update_state);
 }
 
 TEST_F(UmChromeOSPolicyTest,
@@ -523,7 +764,7 @@
   // generated.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_FALSE(result.update_can_start);
   EXPECT_EQ(UpdateCannotStartReason::kScattering, result.cannot_start_reason);
   EXPECT_LT(TimeDelta(), result.scatter_wait_period);
@@ -547,7 +788,7 @@
   // generated.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kAskMeAgainLater, &Policy::UpdateCanStart,
-                     &result, false, update_state);
+                     &result, update_state);
   EXPECT_FALSE(result.update_can_start);
   EXPECT_EQ(UpdateCannotStartReason::kScattering, result.cannot_start_reason);
   EXPECT_EQ(TimeDelta::FromSeconds(35), result.scatter_wait_period);
@@ -573,7 +814,7 @@
   // Check that the UpdateCanStart returns false.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_FALSE(result.update_can_start);
   EXPECT_EQ(UpdateCannotStartReason::kScattering, result.cannot_start_reason);
   EXPECT_LE(2, result.scatter_check_threshold);
@@ -597,7 +838,7 @@
   // Check that the UpdateCanStart returns false.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_FALSE(result.update_can_start);
   EXPECT_EQ(UpdateCannotStartReason::kScattering, result.cannot_start_reason);
   EXPECT_EQ(3, result.scatter_check_threshold);
@@ -622,12 +863,13 @@
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_EQ(TimeDelta(), result.scatter_wait_period);
   EXPECT_EQ(0, result.scatter_check_threshold);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest,
@@ -641,6 +883,7 @@
       new TimeDelta(TimeDelta::FromSeconds(1)));
 
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(1));
+  update_state.is_interactive = true;
   update_state.scatter_check_threshold = 0;
   update_state.scatter_check_threshold_min = 2;
   update_state.scatter_check_threshold_max = 5;
@@ -648,12 +891,13 @@
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     true, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_EQ(TimeDelta(), result.scatter_wait_period);
   EXPECT_EQ(0, result.scatter_check_threshold);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest,
@@ -668,6 +912,7 @@
   fake_state_.system_provider()->var_is_oobe_complete()->reset(new bool(false));
 
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromSeconds(1));
+  update_state.is_interactive = true;
   update_state.scatter_check_threshold = 0;
   update_state.scatter_check_threshold_min = 2;
   update_state.scatter_check_threshold_max = 5;
@@ -675,12 +920,13 @@
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     true, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_EQ(TimeDelta(), result.scatter_wait_period);
   EXPECT_EQ(0, result.scatter_check_threshold);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedWithAttributes) {
@@ -699,11 +945,12 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_TRUE(result.p2p_allowed);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedWithP2PFromUpdater) {
@@ -720,11 +967,12 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_TRUE(result.p2p_allowed);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest,
@@ -745,11 +993,12 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedWithHttpsUrl) {
@@ -764,16 +1013,47 @@
 
   // Add an HTTPS URL.
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
-  update_state.download_urls.push_back("https://secure/url/");
+  update_state.download_urls.emplace_back("https://secure/url/");
 
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(1, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
+}
+
+TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedMaxErrorsNotExceeded) {
+  // The UpdateCanStart policy returns true; the first URL has download errors
+  // but does not exceed the maximum allowed number of failures, so it is stilli
+  // usable.
+
+  SetUpdateCheckAllowed(false);
+
+  // Add a second URL; update with this URL attempted and failed enough times to
+  // disqualify the current (first) URL.
+  UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
+  update_state.num_checks = 5;
+  update_state.download_urls.emplace_back("http://another/fake/url/");
+  Time t = fake_clock_.GetWallclockTime() - TimeDelta::FromSeconds(12);
+  for (int i = 0; i < 5; i++) {
+    update_state.download_errors.emplace_back(
+        0, ErrorCode::kDownloadTransferError, t);
+    t += TimeDelta::FromSeconds(1);
+  }
+
+  // Check that the UpdateCanStart returns true.
+  UpdateDownloadParams result;
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_TRUE(result.update_can_start);
+  EXPECT_FALSE(result.p2p_allowed);
+  EXPECT_EQ(0, result.download_url_idx);
+  EXPECT_EQ(5, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedWithSecondUrlMaxExceeded) {
@@ -783,26 +1063,26 @@
   SetUpdateCheckAllowed(false);
 
   // Add a second URL; update with this URL attempted and failed enough times to
-  // disqualify the current (first) URL. This tests both the previously
-  // accounted failures (download_url_num_failures) as well as those occurring
-  // since the last call (download_url_error_codes).
+  // disqualify the current (first) URL.
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   update_state.num_checks = 10;
-  update_state.download_urls.push_back("http://another/fake/url/");
-  update_state.download_url_num_failures = 9;
-  update_state.download_url_error_codes.push_back(
-      ErrorCode::kDownloadTransferError);
-  update_state.download_url_error_codes.push_back(
-      ErrorCode::kDownloadWriteError);
+  update_state.download_urls.emplace_back("http://another/fake/url/");
+  Time t = fake_clock_.GetWallclockTime() - TimeDelta::FromSeconds(12);
+  for (int i = 0; i < 11; i++) {
+    update_state.download_errors.emplace_back(
+        0, ErrorCode::kDownloadTransferError, t);
+    t += TimeDelta::FromSeconds(1);
+  }
 
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(1, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedWithSecondUrlHardError) {
@@ -815,18 +1095,20 @@
   // causes it to switch directly to the next URL.
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   update_state.num_checks = 10;
-  update_state.download_urls.push_back("http://another/fake/url/");
-  update_state.download_url_error_codes.push_back(
-      ErrorCode::kPayloadHashMismatchError);
+  update_state.download_urls.emplace_back("http://another/fake/url/");
+  update_state.download_errors.emplace_back(
+      0, ErrorCode::kPayloadHashMismatchError,
+      fake_clock_.GetWallclockTime() - TimeDelta::FromSeconds(1));
 
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(1, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedUrlWrapsAround) {
@@ -836,27 +1118,35 @@
   SetUpdateCheckAllowed(false);
 
   // Add a second URL; update with this URL attempted and failed in a way that
-  // causes it to switch directly to the next URL.
+  // causes it to switch directly to the next URL. We must disable backoff in
+  // order for it not to interfere.
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
-  update_state.num_checks = 10;
-  update_state.download_urls.push_back("http://another/fake/url/");
-  update_state.download_url_idx = 1;
-  update_state.download_url_error_codes.push_back(
-      ErrorCode::kPayloadHashMismatchError);
+  update_state.num_checks = 1;
+  update_state.is_backoff_disabled = true;
+  update_state.download_urls.emplace_back("http://another/fake/url/");
+  update_state.download_errors.emplace_back(
+      1, ErrorCode::kPayloadHashMismatchError,
+      fake_clock_.GetWallclockTime() - TimeDelta::FromSeconds(1));
 
   // Check that the UpdateCanStart returns true.
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_FALSE(result.p2p_allowed);
   EXPECT_EQ(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_TRUE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartNotAllowedNoUsableUrls) {
   // The UpdateCanStart policy returns false; there's a single HTTP URL but its
   // use is forbidden by policy.
+  //
+  // Note: In the case where no usable URLs are found, the policy should not
+  // increment the number of failed attempts! Doing so would result in a
+  // non-idempotent semantics, and does not fall within the intended purpose of
+  // the backoff mechanism anyway.
 
   SetUpdateCheckAllowed(false);
 
@@ -867,14 +1157,21 @@
   // Check that the UpdateCanStart returns false.
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
-  ExpectPolicyStatus(EvalStatus::kFailed, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+  ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
+                     update_state);
+  EXPECT_FALSE(result.update_can_start);
+  EXPECT_EQ(UpdateCannotStartReason::kCannotDownload,
+            result.cannot_start_reason);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateCanStartAllowedNoUsableUrlsButP2PEnabled) {
   // The UpdateCanStart policy returns true; there's a single HTTP URL but its
   // use is forbidden by policy, however P2P is enabled. The result indicates
   // that no URL can be used.
+  //
+  // Note: The number of failed attempts should not increase in this case (see
+  // above test).
 
   SetUpdateCheckAllowed(false);
 
@@ -888,11 +1185,12 @@
   UpdateState update_state = GetDefaultUpdateState(TimeDelta::FromMinutes(10));
   UpdateDownloadParams result;
   ExpectPolicyStatus(EvalStatus::kSucceeded, &Policy::UpdateCanStart, &result,
-                     false, update_state);
+                     update_state);
   EXPECT_TRUE(result.update_can_start);
   EXPECT_TRUE(result.p2p_allowed);
   EXPECT_GT(0, result.download_url_idx);
-  EXPECT_EQ(0, result.download_url_num_failures);
+  EXPECT_EQ(0, result.download_url_num_errors);
+  EXPECT_FALSE(result.do_increment_failures);
 }
 
 TEST_F(UmChromeOSPolicyTest, UpdateDownloadAllowedEthernetDefault) {
diff --git a/update_manager/default_policy.cc b/update_manager/default_policy.cc
index 98c2786..5a07900 100644
--- a/update_manager/default_policy.cc
+++ b/update_manager/default_policy.cc
@@ -41,4 +41,31 @@
   return EvalStatus::kAskMeAgainLater;
 }
 
+EvalStatus DefaultPolicy::UpdateCanStart(
+    EvaluationContext* ec,
+    State* state,
+    std::string* error,
+    UpdateDownloadParams* result,
+    const UpdateState& update_state) const {
+  result->update_can_start = true;
+  result->cannot_start_reason = UpdateCannotStartReason::kUndefined;
+  result->download_url_idx = 0;
+  result->download_url_num_errors = 0;
+  result->p2p_allowed = false;
+  result->do_increment_failures = false;
+  result->backoff_expiry = base::Time();
+  result->scatter_wait_period = base::TimeDelta();
+  result->scatter_check_threshold = 0;
+  return EvalStatus::kSucceeded;
+}
+
+EvalStatus DefaultPolicy::UpdateDownloadAllowed(
+    EvaluationContext* ec,
+    State* state,
+    std::string* error,
+    bool* result) const {
+  *result = true;
+  return EvalStatus::kSucceeded;
+}
+
 }  // namespace chromeos_update_manager
diff --git a/update_manager/default_policy.h b/update_manager/default_policy.h
index 526476c..f3f663c 100644
--- a/update_manager/default_policy.h
+++ b/update_manager/default_policy.h
@@ -57,30 +57,13 @@
       UpdateCheckParams* result) const override;
 
   EvalStatus UpdateCanStart(
-      EvaluationContext* ec,
-      State* state,
-      std::string* error,
+      EvaluationContext* ec, State* state, std::string* error,
       UpdateDownloadParams* result,
-      const bool interactive,
-      const UpdateState& update_state) const override {
-    result->update_can_start = true;
-    result->p2p_allowed = false;
-    result->download_url_idx = 0;
-    result->download_url_num_failures = 0;
-    result->cannot_start_reason = UpdateCannotStartReason::kUndefined;
-    result->scatter_wait_period = base::TimeDelta();
-    result->scatter_check_threshold = 0;
-    return EvalStatus::kSucceeded;
-  }
+      const UpdateState& update_state) const override;
 
   EvalStatus UpdateDownloadAllowed(
-      EvaluationContext* ec,
-      State* state,
-      std::string* error,
-      bool* result) const override {
-    *result = true;
-    return EvalStatus::kSucceeded;
-  }
+      EvaluationContext* ec, State* state, std::string* error,
+      bool* result) const override;
 
  protected:
   // Policy override.
diff --git a/update_manager/mock_policy.h b/update_manager/mock_policy.h
index f6acb7f..4fff97e 100644
--- a/update_manager/mock_policy.h
+++ b/update_manager/mock_policy.h
@@ -24,10 +24,10 @@
                      EvalStatus(EvaluationContext*, State*, std::string*,
                                 UpdateCheckParams*));
 
-  MOCK_CONST_METHOD6(UpdateCanStart,
+  MOCK_CONST_METHOD5(UpdateCanStart,
                      EvalStatus(EvaluationContext*, State*, std::string*,
                                 UpdateDownloadParams*,
-                                const bool, const UpdateState&));
+                                const UpdateState&));
 
   MOCK_CONST_METHOD4(UpdateCanStart,
                      EvalStatus(EvaluationContext*, State*, std::string*,
diff --git a/update_manager/policy.h b/update_manager/policy.h
index 8ec5c9e..40586c3 100644
--- a/update_manager/policy.h
+++ b/update_manager/policy.h
@@ -6,6 +6,7 @@
 #define UPDATE_ENGINE_UPDATE_MANAGER_POLICY_H_
 
 #include <string>
+#include <tuple>
 #include <vector>
 
 #include "update_engine/error_code.h"
@@ -41,38 +42,67 @@
 
 // Input arguments to UpdateCanStart.
 //
-// A snapshot of the state of the current update process.
+// A snapshot of the state of the current update process. This includes
+// everything that a policy might need and that occurred since the first time
+// the current payload was first seen and attempted (consecutively).
 struct UpdateState {
-  // Information pertaining to the Omaha update response.
+  // Information pertaining to the current update payload and/or check.
   //
-  // Time when update was first offered by Omaha.
+  // Whether the current update check is an interactive one. The caller should
+  // feed the value returned by the preceding call to UpdateCheckAllowed().
+  bool is_interactive;
+  // Whether it is a delta payload.
+  bool is_delta_payload;
+  // Wallclock time when payload was first (consecutively) offered by Omaha.
   base::Time first_seen;
-  // Number of update checks returning the current update.
+  // Number of consecutive update checks returning the current update.
   int num_checks;
+  // Number of update payload failures and the wallclock time when it was last
+  // updated by the updater. These should both be nullified whenever a new
+  // update is seen; they are updated at the policy's descretion (via
+  // UpdateDownloadParams.do_increment_failures) once all of the usable download
+  // URLs for the payload have been used without success. They should be
+  // persisted across reboots.
+  int num_failures;
+  base::Time failures_last_updated;
 
-  // Information pertaining to the update download URL.
+  // Information pertaining to downloading and applying of the current update.
   //
   // An array of download URLs provided by Omaha.
   std::vector<std::string> download_urls;
-  // Max number of failures allowed per download URL.
-  int download_failures_max;
-  // The index of the URL to use, as previously determined by the policy. This
-  // number is significant iff |num_checks| is greater than 1.
-  int download_url_idx;
-  // The number of failures already associated with this URL.
-  int download_url_num_failures;
-  // An array of failure error codes that occurred since the latest reported
-  // ones (included in the number above).
-  std::vector<chromeos_update_engine::ErrorCode> download_url_error_codes;
+  // Max number of errors allowed per download URL.
+  int download_errors_max;
+  // The index of the URL to download from, as determined in the previous call
+  // to the policy. For a newly seen payload, this should be -1.
+  int last_download_url_idx;
+  // The number of successive download errors pertaining to this last URL, as
+  // determined in the previous call to the policy. For a newly seen payload,
+  // this should be zero.
+  int last_download_url_num_errors;
+  // An array of errors that occurred while trying to download this update since
+  // the previous call to this policy has returned, or since this payload was
+  // first seen, or since the updater process has started (whichever is later).
+  // Includes the URL index attempted, the error code, and the wallclock-based
+  // timestamp when it occurred.
+  std::vector<std::tuple<int, chromeos_update_engine::ErrorCode, base::Time>>
+      download_errors;
+
+  // Information pertaining to update backoff mechanism.
+  //
+  // The currently known (persisted) wallclock-based backoff expiration time;
+  // zero if none.
+  base::Time backoff_expiry;
+  // Whether backoff is disabled by Omaha.
+  bool is_backoff_disabled;
 
   // Information pertaining to update scattering.
   //
-  // Scattering wallclock-based wait period, as returned by the policy.
+  // The currently knwon (persisted) scattering wallclock-based wait period and
+  // update check threshold; zero if none.
   base::TimeDelta scatter_wait_period;
+  int scatter_check_threshold;
   // Maximum wait period allowed for this update, as determined by Omaha.
   base::TimeDelta scatter_wait_period_max;
-  // Scattering update check threshold, as returned by the policy.
-  int scatter_check_threshold;
   // Minimum/maximum check threshold values.
   // TODO(garnold) These appear to not be related to the current update and so
   // should probably be obtained as variables via UpdaterProvider.
@@ -88,29 +118,46 @@
   kUndefined,
   kCheckDue,
   kScattering,
+  kBackoff,
   kCannotDownload,
 };
 
 struct UpdateDownloadParams {
   // Whether the update attempt is allowed to proceed.
   bool update_can_start;
+  // If update cannot proceed, a reason code for why it cannot do so.
+  UpdateCannotStartReason cannot_start_reason;
 
   // Attributes pertaining to the case where update is allowed. The update
   // engine uses them to choose the means for downloading and applying an
   // update.
-  bool p2p_allowed;
-  // The index of the download URL to use, and the number of failures associated
-  // with this URL. An index value of -1 indicates that no suitable URL is
-  // available, but there may be other means for download (like P2P).
+  //
+  // The index of the download URL to use, or -1 if no suitable URL was found;
+  // in the latter case, there may still be other means for download (like P2P).
+  // This value needs to be persisted and handed back to the policy on the next
+  // time it is called.
   int download_url_idx;
-  int download_url_num_failures;
+  // The number of download errors associated with this download URL. This value
+  // needs to be persisted and handed back to the policy on the next time it is
+  // called.
+  int download_url_num_errors;
+  // Whether P2P downloads are allowed.
+  bool p2p_allowed;
 
-  // Attributes pertaining to the case where update is not allowed. Some are
-  // needed for storing values to persistent storage, others for
-  // logging/metrics.
-  UpdateCannotStartReason cannot_start_reason;
-  base::TimeDelta scatter_wait_period;  // Needs to be persisted.
-  int scatter_check_threshold;  // Needs to be persisted.
+  // Other values that need to be persisted and handed to the policy as need on
+  // the next call.
+  //
+  // Whether an update failure has been identified by the policy. The client
+  // should increment and persist its update failure count, and record the time
+  // when this was done; it needs to hand these values back to the policy
+  // (UpdateState.{num_failures,failures_last_updated}) on the next time it is
+  // called.
+  bool do_increment_failures;
+  // The current backof expiry.
+  base::Time backoff_expiry;
+  // The scattering wait period and check threshold.
+  base::TimeDelta scatter_wait_period;
+  int scatter_check_threshold;
 };
 
 // The Policy class is an interface to the ensemble of policy requests that the
@@ -165,22 +212,20 @@
   // processed, or the attempt needs to be aborted. In cases where the update
   // needs to wait for some condition to be satisfied, but none of the values
   // that need to be persisted has changed, returns
-  // EvalStatus::kAskMeAgainLater. Arguments include an |interactive| flag that
-  // tells whether the update is user initiated, and an |update_state| that
+  // EvalStatus::kAskMeAgainLater. Arguments include an |update_state| that
   // encapsulates data pertaining to the current ongoing update process.
   virtual EvalStatus UpdateCanStart(
       EvaluationContext* ec,
       State* state,
       std::string* error,
       UpdateDownloadParams* result,
-      const bool interactive,
       const UpdateState& update_state) const = 0;
 
   // Checks whether downloading of an update is allowed; currently, this checks
   // whether the network connection type is suitable for updating over.  May
   // consult the shill provider as well as the device policy (if available).
   // Returns |EvalStatus::kSucceeded|, setting |result| according to whether or
-  // not the current connection can be used; on failure, returns
+  // not the current connection can be used; on error, returns
   // |EvalStatus::kFailed| and sets |error| accordingly.
   virtual EvalStatus UpdateDownloadAllowed(
       EvaluationContext* ec,
diff --git a/update_manager/update_manager_unittest.cc b/update_manager/update_manager_unittest.cc
index f6a1c01..9e21716 100644
--- a/update_manager/update_manager_unittest.cc
+++ b/update_manager/update_manager_unittest.cc
@@ -6,6 +6,7 @@
 
 #include <algorithm>
 #include <string>
+#include <tuple>
 #include <utility>
 #include <vector>
 
@@ -31,6 +32,7 @@
 using chromeos_update_engine::FakeClock;
 using std::pair;
 using std::string;
+using std::tuple;
 using std::vector;
 using testing::Return;
 using testing::StrictMock;
@@ -161,15 +163,29 @@
 }
 
 TEST_F(UmUpdateManagerTest, PolicyRequestCallUpdateCanStart) {
-  const UpdateState update_state = {
-    FixedTime(), 1,
-    vector<string>(1, "http://fake/url/"), 10, 0, 0, vector<ErrorCode>(),
-    TimeDelta::FromSeconds(15), TimeDelta::FromSeconds(60),
-    4, 2, 8
-  };
+  UpdateState update_state = UpdateState();
+  update_state.is_interactive = true;
+  update_state.is_delta_payload = false;
+  update_state.first_seen = FixedTime();
+  update_state.num_checks = 1;
+  update_state.num_failures = 0;
+  update_state.failures_last_updated = Time();
+  update_state.download_urls = vector<string>{"http://fake/url/"};
+  update_state.download_errors_max = 10;
+  update_state.last_download_url_idx = -1;
+  update_state.last_download_url_num_errors = 0;
+  update_state.download_errors = vector<tuple<int, ErrorCode, Time>>();
+  update_state.backoff_expiry = Time();
+  update_state.is_backoff_disabled = false;
+  update_state.scatter_wait_period = TimeDelta::FromSeconds(15);
+  update_state.scatter_check_threshold = 4;
+  update_state.scatter_wait_period_max = TimeDelta::FromSeconds(60);
+  update_state.scatter_check_threshold_min = 2;
+  update_state.scatter_check_threshold_max = 8;
+
   UpdateDownloadParams result;
   EXPECT_EQ(EvalStatus::kSucceeded,
-            umut_->PolicyRequest(&Policy::UpdateCanStart, &result, true,
+            umut_->PolicyRequest(&Policy::UpdateCanStart, &result,
                                  update_state));
 }