Scatter downloads to reduce bandwidth spikes.

Support in update_engine to honor the enterprise policy to scatter the
downloading of ChromeOS automatic updates so that we reduce bandwidth
spikes caused due to simultaneous downloads of updates by a large number
of enterprise devices.

This has no effect on consumer devices.

BUG=chromeos-29615: Implement scattering of downloads in UpdateEngine
TEST=Manually tested all scenarios, Unit tests added for all new code.
CQ-DEPEND=I1f56b5516970d5988eebb2cf8f93f6905823801d
Change-Id: I4a8f4974467a064d723ab13cbd78b1ca3ceff420
Reviewed-on: https://gerrit.chromium.org/gerrit/21574
Commit-Ready: Jay Srinivasan <jaysri@chromium.org>
Reviewed-by: Jay Srinivasan <jaysri@chromium.org>
Tested-by: Jay Srinivasan <jaysri@chromium.org>
diff --git a/omaha_request_action.cc b/omaha_request_action.cc
index 9be4fdc..ae8e5e7 100644
--- a/omaha_request_action.cc
+++ b/omaha_request_action.cc
@@ -7,13 +7,14 @@
 #include <inttypes.h>
 
 #include <sstream>
+#include <string>
 
+#include <base/logging.h>
+#include <base/rand_util.h>
 #include <base/string_number_conversions.h>
 #include <base/string_util.h>
 #include <base/stringprintf.h>
 #include <base/time.h>
-#include <base/logging.h>
-#include <libxml/parser.h>
 #include <libxml/xpath.h>
 #include <libxml/xpathInternals.h>
 
@@ -183,7 +184,7 @@
 }
 
 OmahaRequestAction::OmahaRequestAction(PrefsInterface* prefs,
-                                       const OmahaRequestParams& params,
+                                       OmahaRequestParams* params,
                                        OmahaEvent* event,
                                        HttpFetcher* http_fetcher,
                                        bool ping_only)
@@ -239,7 +240,7 @@
     return;
   }
   string request_post(FormatRequest(event_.get(),
-                                    params_,
+                                    *params_,
                                     ping_only_,
                                     ping_active_days_,
                                     ping_roll_call_days_,
@@ -247,9 +248,9 @@
 
   http_fetcher_->SetPostData(request_post.data(), request_post.size(),
                              kHttpContentTypeTextXml);
-  LOG(INFO) << "Posting an Omaha request to " << params_.update_url;
+  LOG(INFO) << "Posting an Omaha request to " << params_->update_url;
   LOG(INFO) << "Request: " << request_post;
-  http_fetcher_->BeginTransfer(params_.update_url);
+  http_fetcher_->BeginTransfer(params_->update_url);
 }
 
 void OmahaRequestAction::TerminateProcessing() {
@@ -463,12 +464,18 @@
     return;
   }
 
-  if (params_.update_disabled) {
+  if (params_->update_disabled) {
     LOG(INFO) << "Ignoring Omaha updates as updates are disabled by policy.";
     completer.set_code(kActionCodeOmahaUpdateIgnoredPerPolicy);
     return;
   }
 
+  if (ShouldDeferDownload(updatecheck_node)) {
+    LOG(INFO) << "Ignoring Omaha updates as updates are deferred by policy.";
+    completer.set_code(kActionCodeOmahaUpdateDeferredPerPolicy);
+    return;
+  }
+
   // In best-effort fashion, fetch the rest of the expected attributes
   // from the updatecheck node, then return the object
   output_object.update_exists = true;
@@ -487,4 +494,170 @@
   SetOutputObject(output_object);
 }
 
-};  // namespace chromeos_update_engine
+bool OmahaRequestAction::ShouldDeferDownload(xmlNode* updatecheck_node) {
+  // We should defer the downloads only if we've first satisfied the
+  // wall-clock-based-waiting period and then the update-check-based waiting
+  // period, if required.
+
+  if (!params_->wall_clock_based_wait_enabled) {
+    // Wall-clock-based waiting period is not enabled, so no scattering needed.
+    return false;
+  }
+
+  switch (IsWallClockBasedWaitingSatisfied(updatecheck_node)) {
+    case kWallClockWaitNotSatisfied:
+      // We haven't even satisfied the first condition, passing the
+      // wall-clock-based waiting period, so we should defer the downloads
+      // until that happens.
+      LOG(INFO) << "wall-clock-based-wait not satisfied.";
+      return true;
+
+    case kWallClockWaitDoneButUpdateCheckWaitRequired:
+      LOG(INFO) << "wall-clock-based-wait satisfied and "
+                << "update-check-based-wait required.";
+      return !IsUpdateCheckCountBasedWaitingSatisfied(updatecheck_node);
+
+    case kWallClockWaitDoneAndUpdateCheckWaitNotRequired:
+      // Wall-clock-based waiting period is satisfied, and it's determined
+      // that we do not need the update-check-based wait. so no need to
+      // defer downloads.
+      LOG(INFO) << "wall-clock-based-wait satisfied and "
+                << "update-check-based-wait is not required.";
+      return false;
+
+    default:
+      // Returning false for this default case so we err on the
+      // side of downloading updates than deferring in case of any bugs.
+      NOTREACHED();
+      return false;
+  }
+}
+
+OmahaRequestAction::WallClockWaitResult
+OmahaRequestAction::IsWallClockBasedWaitingSatisfied(
+    xmlNode* updatecheck_node) {
+  Time update_published_time;
+
+  // UpdatePublishedOn must be in GMT.
+  if (!Time::FromString(
+      XmlGetProperty(updatecheck_node, "UpdatePublishedOn").c_str(),
+          &update_published_time)) {
+    LOG(INFO) << "UpdatePublishedOn not present in rule. Treating as 0.";
+    return kWallClockWaitDoneAndUpdateCheckWaitNotRequired;
+  }
+
+  TimeDelta elapsed_time = Time::Now() - update_published_time;
+  TimeDelta max_scatter_period = TimeDelta::FromDays(
+      ParseInt(XmlGetProperty(updatecheck_node, "MaxDaysToScatter")));
+
+  LOG(INFO) << "Update Published On = "
+            << utils::ToString(update_published_time)
+            << ", Waiting Period = "
+            << utils::FormatSecs(params_->waiting_period.InSeconds())
+            << ", Time Elapsed = "
+            << utils::FormatSecs(elapsed_time.InSeconds())
+            << ", MaxDaysToScatter = "
+            << max_scatter_period.InDays();
+
+  if (!XmlGetProperty(updatecheck_node, "deadline").empty()) {
+    // The deadline is set for all rules which serve a delta update from a
+    // previous FSI, which means this update will be applied mostly in OOBE
+    // cases. For these cases, we shouldn't scatter so as to finish the OOBE
+    // quickly.
+    LOG(INFO) << "Not scattering as deadline flag is set";
+    return kWallClockWaitDoneAndUpdateCheckWaitNotRequired;
+  }
+
+  if (max_scatter_period.InDays() == 0) {
+    // This means the Omaha rule creator decides that this rule
+    // should not be scattered irrespective of the policy.
+    LOG(INFO) << "Not scattering as MaxDaysToScatter in rule is 0.";
+    return kWallClockWaitDoneAndUpdateCheckWaitNotRequired;
+  }
+
+  if (elapsed_time > max_scatter_period) {
+    // This means it's been a while since the update was published and
+    // we are less likely to cause bandwidth spikes by downloading now.
+    // This also establishes an upperbound wait in terms of wall-clock time
+    // so as to prevent machines from not getting updated for too long.
+    LOG(INFO) << "Not scattering as we're past the MaxDaysToScatter limit.";
+    return kWallClockWaitDoneAndUpdateCheckWaitNotRequired;
+  }
+
+  // This means we are required to participate in scattering.
+  // See if our turn has arrived now.
+  TimeDelta remaining_wait_time = params_->waiting_period - elapsed_time;
+  if (remaining_wait_time.InSeconds() <= 0) {
+    // Yes, it's our turn now.
+    LOG(INFO) << "Successfully passed the wall-clock-based-wait.";
+
+    // But we can't download until the update-check-count-based wait is also
+    // satisfied, so mark it as required now if update checks are enabled.
+    return params_->update_check_count_wait_enabled ?
+              kWallClockWaitDoneButUpdateCheckWaitRequired :
+              kWallClockWaitDoneAndUpdateCheckWaitNotRequired;
+  }
+
+  // Not our turn yet, so we have to wait until our turn to
+  // help scatter the downloads across all clients of the enterprise.
+  LOG(INFO) << "Update deferred for another "
+            << utils::FormatSecs(remaining_wait_time.InSeconds())
+            << " per policy.";
+  return kWallClockWaitNotSatisfied;
+}
+
+bool OmahaRequestAction::IsUpdateCheckCountBasedWaitingSatisfied(
+    xmlNode* updatecheck_node) {
+  int64 update_check_count_value;
+
+  if (prefs_->Exists(kPrefsUpdateCheckCount)) {
+    if (!prefs_->GetInt64(kPrefsUpdateCheckCount, &update_check_count_value)) {
+      // We are unable to read the update check count from file for some reason.
+      // So let's proceed anyway so as to not stall the update.
+      LOG(ERROR) << "Unable to read update check count. "
+                 << "Skipping update-check-count-based-wait.";
+      return true;
+    }
+  } else {
+    // This file does not exist. This means we haven't started our update
+    // check count down yet, so this is the right time to start the count down.
+    update_check_count_value = base::RandInt(
+      params_->min_update_checks_needed,
+      params_->max_update_checks_allowed);
+
+    LOG(INFO) << "Randomly picked update check count value = "
+              << update_check_count_value;
+
+    // Write out the initial value of update_check_count_value.
+    if (!prefs_->SetInt64(kPrefsUpdateCheckCount, update_check_count_value)) {
+      // We weren't able to write the update check count file for some reason.
+      // So let's proceed anyway so as to not stall the update.
+      LOG(ERROR) << "Unable to write update check count. "
+                 << "Skipping update-check-count-based-wait.";
+      return true;
+    }
+  }
+
+  if (update_check_count_value == 0) {
+    LOG(INFO) << "Successfully passed the update-check-based-wait.";
+    return true;
+  }
+
+  if (update_check_count_value < 0 ||
+      update_check_count_value > params_->max_update_checks_allowed) {
+    // We err on the side of skipping scattering logic instead of stalling
+    // a machine from receiving any updates in case of any unexpected state.
+    LOG(ERROR) << "Invalid value for update check count detected. "
+               << "Skipping update-check-count-based-wait.";
+    return true;
+  }
+
+  // Legal value, we need to wait for more update checks to happen
+  // until this becomes 0.
+  LOG(INFO) << "Deferring Omaha updates for another "
+            << update_check_count_value
+            << " update checks per policy";
+  return false;
+}
+
+}  // namespace chromeos_update_engine
diff --git a/omaha_request_action.h b/omaha_request_action.h
index b3df207..2bbbc71 100644
--- a/omaha_request_action.h
+++ b/omaha_request_action.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2011 The Chromium OS Authors. All rights reserved.
+// Copyright (c) 2012 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -13,6 +13,7 @@
 
 #include <base/memory/scoped_ptr.h>
 #include <curl/curl.h>
+#include <libxml/parser.h>
 
 #include "update_engine/action.h"
 #include "update_engine/http_fetcher.h"
@@ -114,6 +115,14 @@
   static const int kNeverPinged = -1;
   static const int kPingTimeJump = -2;
 
+  // These are the possible outcome upon checking whether we satisfied
+  // the wall-clock-based-wait.
+  enum WallClockWaitResult {
+    kWallClockWaitNotSatisfied,
+    kWallClockWaitDoneButUpdateCheckWaitRequired,
+    kWallClockWaitDoneAndUpdateCheckWaitNotRequired,
+  };
+
   // The ctor takes in all the parameters that will be used for making
   // the request to Omaha. For some of them we have constants that
   // should be used.
@@ -129,7 +138,7 @@
   // or
   // OmahaRequestAction(..., NULL, new WhateverHttpFetcher);
   OmahaRequestAction(PrefsInterface* prefs,
-                     const OmahaRequestParams& params,
+                     OmahaRequestParams* params,
                      OmahaEvent* event,
                      HttpFetcher* http_fetcher,
                      bool ping_only);
@@ -163,11 +172,26 @@
   // number of days since the last ping sent for |key|.
   int CalculatePingDays(const std::string& key);
 
+  // Returns true if the download of a new update should be deferred.
+  // False if the update can be downloaded.
+  bool ShouldDeferDownload(xmlNode* updatecheck_node);
+
+  // Returns true if the basic wall-clock-based waiting period has been
+  // satisfied based on the scattering policy setting. False otherwise.
+  // If true, it also indicates whether the additional update-check-count-based
+  // waiting period also needs to be satisfied before the download can begin.
+  WallClockWaitResult IsWallClockBasedWaitingSatisfied(
+      xmlNode* updatecheck_node);
+
+  // Returns true if the update-check-count-based waiting period has been
+  // satisfied. False otherwise.
+  bool IsUpdateCheckCountBasedWaitingSatisfied(xmlNode* updatecheck_node);
+
   // Access to the preferences store.
   PrefsInterface* prefs_;
 
-  // These are data that are passed in the request to the Omaha server.
-  const OmahaRequestParams& params_;
+  // Contains state that is relevant in the processing of the Omaha request.
+  OmahaRequestParams* params_;
 
   // Pointer to the OmahaEvent info. This is an UpdateCheck request if NULL.
   scoped_ptr<OmahaEvent> event_;
diff --git a/omaha_request_action_unittest.cc b/omaha_request_action_unittest.cc
index e4ab729..d8bef5e 100644
--- a/omaha_request_action_unittest.cc
+++ b/omaha_request_action_unittest.cc
@@ -16,8 +16,10 @@
 #include "update_engine/omaha_hash_calculator.h"
 #include "update_engine/omaha_request_action.h"
 #include "update_engine/omaha_request_params.h"
+#include "update_engine/prefs.h"
 #include "update_engine/prefs_mock.h"
 #include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
 
 using base::Time;
 using base::TimeDelta;
@@ -36,7 +38,8 @@
 class OmahaRequestActionTest : public ::testing::Test { };
 
 namespace {
-const OmahaRequestParams kDefaultTestParams(
+
+OmahaRequestParams kDefaultTestParams(
     OmahaRequestParams::kOsPlatform,
     OmahaRequestParams::kOsVersion,
     "service_pack",
@@ -49,7 +52,7 @@
     false,  // delta okay
     "http://url",
     false, // update_disabled
-    "");   // target_version_prefix
+    ""); // target_version_prefix);
 
 string GetNoUpdateResponse(const string& app_id) {
   return string(
@@ -59,6 +62,37 @@
       "status=\"ok\"/><updatecheck status=\"noupdate\"/></app></gupdate>";
 }
 
+string GetUpdateResponse2(const string& app_id,
+                          const string& display_version,
+                          const string& more_info_url,
+                          const string& prompt,
+                          const string& codebase,
+                          const string& hash,
+                          const string& needsadmin,
+                          const string& size,
+                          const string& deadline,
+                          Time published_on,
+                          const string& max_days_to_scatter) {
+  return string(
+      "<?xml version=\"1.0\" encoding=\"UTF-8\"?><gupdate "
+      "xmlns=\"http://www.google.com/update2/response\" "
+      "protocol=\"2.0\"><app "
+      "appid=\"") + app_id + "\" status=\"ok\"><ping "
+      "status=\"ok\"/><updatecheck DisplayVersion=\"" + display_version + "\" "
+      "ChromeOSVersion=\"" + display_version + "\" "
+      "MoreInfo=\"" + more_info_url + "\" Prompt=\"" + prompt + "\" "
+      "IsDelta=\"true\" "
+      "UpdatePublishedOn=\"" + utils::ToString(published_on) + "\" "
+      "MaxDaysToScatter=\"" + max_days_to_scatter + "\" "
+      "codebase=\"" + codebase + "\" "
+      "hash=\"not-applicable\" "
+      "sha256=\"" + hash + "\" "
+      "needsadmin=\"" + needsadmin + "\" "
+      "size=\"" + size + "\" " +
+      (deadline.empty() ? "" : ("deadline=\"" + deadline + "\" ")) +
+      "status=\"ok\"/></app></gupdate>";
+}
+
 string GetUpdateResponse(const string& app_id,
                          const string& display_version,
                          const string& more_info_url,
@@ -68,19 +102,17 @@
                          const string& needsadmin,
                          const string& size,
                          const string& deadline) {
-  return string(
-      "<?xml version=\"1.0\" encoding=\"UTF-8\"?><gupdate "
-      "xmlns=\"http://www.google.com/update2/response\" "
-      "protocol=\"2.0\"><app "
-      "appid=\"") + app_id + "\" status=\"ok\"><ping "
-      "status=\"ok\"/><updatecheck DisplayVersion=\"" + display_version + "\" "
-      "ChromeOSVersion=\"" + display_version + "\" "
-      "MoreInfo=\"" + more_info_url + "\" Prompt=\"" + prompt + "\" "
-      "IsDelta=\"true\" "
-      "codebase=\"" + codebase + "\" hash=\"not-applicable\" "
-      "sha256=\"" + hash + "\" needsadmin=\"" + needsadmin + "\" "
-      "size=\"" + size + "\" deadline=\"" + deadline +
-      "\" status=\"ok\"/></app></gupdate>";
+  return GetUpdateResponse2(app_id,
+                            display_version,
+                            more_info_url,
+                            prompt,
+                            codebase,
+                            hash,
+                            needsadmin,
+                            size,
+                            deadline,
+                            Time::Now(),
+                            "7");
 }
 
 class OmahaRequestActionTestProcessorDelegate : public ActionProcessorDelegate {
@@ -157,7 +189,7 @@
 // OmahaRequestAction constructor. out_post_data may be null; if non-null, the
 // post-data received by the mock HttpFetcher is returned.
 bool TestUpdateCheck(PrefsInterface* prefs,
-                     const OmahaRequestParams& params,
+                     OmahaRequestParams params,
                      const string& http_response,
                      int fail_http_response_code,
                      bool ping_only,
@@ -173,7 +205,7 @@
   }
   NiceMock<PrefsMock> local_prefs;
   OmahaRequestAction action(prefs ? prefs : &local_prefs,
-                            params,
+                            &params,
                             NULL,
                             fetcher,
                             ping_only);
@@ -202,7 +234,7 @@
 // Tests Event requests -- they should always succeed. |out_post_data|
 // may be null; if non-null, the post-data received by the mock
 // HttpFetcher is returned.
-void TestEvent(const OmahaRequestParams& params,
+void TestEvent(OmahaRequestParams params,
                OmahaEvent* event,
                const string& http_response,
                vector<char>* out_post_data) {
@@ -211,7 +243,7 @@
                                                  http_response.size(),
                                                  NULL);
   NiceMock<PrefsMock> prefs;
-  OmahaRequestAction action(&prefs, params, event, fetcher, false);
+  OmahaRequestAction action(&prefs, &params, event, fetcher, false);
   OmahaRequestActionTestProcessorDelegate delegate;
   delegate.loop_ = loop;
   ActionProcessor processor;
@@ -284,7 +316,7 @@
                                         "HASH1234=",  // checksum
                                         "false",  // needs admin
                                         "123",  // size
-                                        "20101020"),  // deadline
+                                        ""),  // deadline
                       -1,
                       false,  // ping_only
                       kActionCodeOmahaUpdateIgnoredPerPolicy,
@@ -293,7 +325,6 @@
   EXPECT_FALSE(response.update_exists);
 }
 
-
 TEST(OmahaRequestActionTest, NoUpdatesSentWhenBlockedByPolicyTest) {
   OmahaResponse response;
   OmahaRequestParams params = kDefaultTestParams;
@@ -310,6 +341,265 @@
   EXPECT_FALSE(response.update_exists);
 }
 
+TEST(OmahaRequestActionTest, WallClockBasedWaitAloneCausesScattering) {
+  OmahaResponse response;
+  OmahaRequestParams params = kDefaultTestParams;
+  params.wall_clock_based_wait_enabled = true;
+  params.update_check_count_wait_enabled = false;
+  params.waiting_period = TimeDelta::FromDays(2);
+
+  string prefs_dir;
+  EXPECT_TRUE(utils::MakeTempDirectory("/tmp/ue_ut_prefs.XXXXXX",
+                                       &prefs_dir));
+  ScopedDirRemover temp_dir_remover(prefs_dir);
+
+  Prefs prefs;
+  LOG_IF(ERROR, !prefs.Init(FilePath(prefs_dir)))
+      << "Failed to initialize preferences.";
+
+  ASSERT_FALSE(
+      TestUpdateCheck(&prefs,  // prefs
+                      params,
+                      GetUpdateResponse2(OmahaRequestParams::kAppId,
+                                         "1.2.3.4",  // version
+                                         "http://more/info",
+                                         "true",  // prompt
+                                         "http://code/base",  // dl url
+                                         "HASH1234=",  // checksum
+                                         "false",  // needs admin
+                                         "123",  // size
+                                         "",  // deadline
+                                         Time::Now(), // published on
+                                         "7"), // max days to scatter
+                      -1,
+                      false,  // ping_only
+                      kActionCodeOmahaUpdateDeferredPerPolicy,
+                      &response,
+                      NULL));
+  EXPECT_FALSE(response.update_exists);
+}
+
+TEST(OmahaRequestActionTest, NoWallClockBasedWaitCausesNoScattering) {
+  OmahaResponse response;
+  OmahaRequestParams params = kDefaultTestParams;
+  params.wall_clock_based_wait_enabled = false;
+  params.waiting_period = TimeDelta::FromDays(2);
+
+  params.update_check_count_wait_enabled = true;
+  params.min_update_checks_needed = 1;
+  params.max_update_checks_allowed = 8;
+
+  string prefs_dir;
+  EXPECT_TRUE(utils::MakeTempDirectory("/tmp/ue_ut_prefs.XXXXXX",
+                                       &prefs_dir));
+  ScopedDirRemover temp_dir_remover(prefs_dir);
+
+  Prefs prefs;
+  LOG_IF(ERROR, !prefs.Init(FilePath(prefs_dir)))
+      << "Failed to initialize preferences.";
+
+  ASSERT_TRUE(
+      TestUpdateCheck(&prefs,  // prefs
+                      params,
+                      GetUpdateResponse2(OmahaRequestParams::kAppId,
+                                         "1.2.3.4",  // version
+                                         "http://more/info",
+                                         "true",  // prompt
+                                         "http://code/base",  // dl url
+                                         "HASH1234=",  // checksum
+                                         "false",  // needs admin
+                                         "123",  // size
+                                         "",  // deadline
+                                         Time::Now(), // published on
+                                         "7"), // max days to scatter
+                      -1,
+                      false,  // ping_only
+                      kActionCodeSuccess,
+                      &response,
+                      NULL));
+  EXPECT_TRUE(response.update_exists);
+}
+
+TEST(OmahaRequestActionTest, ZeroMaxDaysToScatterCausesNoScattering) {
+  OmahaResponse response;
+  OmahaRequestParams params = kDefaultTestParams;
+  params.wall_clock_based_wait_enabled = true;
+  params.waiting_period = TimeDelta::FromDays(2);
+
+  params.update_check_count_wait_enabled = true;
+  params.min_update_checks_needed = 1;
+  params.max_update_checks_allowed = 8;
+
+  string prefs_dir;
+  EXPECT_TRUE(utils::MakeTempDirectory("/tmp/ue_ut_prefs.XXXXXX",
+                                       &prefs_dir));
+  ScopedDirRemover temp_dir_remover(prefs_dir);
+
+  Prefs prefs;
+  LOG_IF(ERROR, !prefs.Init(FilePath(prefs_dir)))
+      << "Failed to initialize preferences.";
+
+  ASSERT_TRUE(
+      TestUpdateCheck(&prefs,  // prefs
+                      params,
+                      GetUpdateResponse2(OmahaRequestParams::kAppId,
+                                         "1.2.3.4",  // version
+                                         "http://more/info",
+                                         "true",  // prompt
+                                         "http://code/base",  // dl url
+                                         "HASH1234=",  // checksum
+                                         "false",  // needs admin
+                                         "123",  // size
+                                         "",  // deadline
+                                         Time::Now(), // published on
+                                         "0"), // max days to scatter
+                      -1,
+                      false,  // ping_only
+                      kActionCodeSuccess,
+                      &response,
+                      NULL));
+  EXPECT_TRUE(response.update_exists);
+}
+
+
+TEST(OmahaRequestActionTest, ZeroUpdateCheckCountCausesNoScattering) {
+  OmahaResponse response;
+  OmahaRequestParams params = kDefaultTestParams;
+  params.wall_clock_based_wait_enabled = true;
+  params.waiting_period = TimeDelta();
+
+  params.update_check_count_wait_enabled = true;
+  params.min_update_checks_needed = 0;
+  params.max_update_checks_allowed = 0;
+
+  string prefs_dir;
+  EXPECT_TRUE(utils::MakeTempDirectory("/tmp/ue_ut_prefs.XXXXXX",
+                                       &prefs_dir));
+  ScopedDirRemover temp_dir_remover(prefs_dir);
+
+  Prefs prefs;
+  LOG_IF(ERROR, !prefs.Init(FilePath(prefs_dir)))
+      << "Failed to initialize preferences.";
+
+  ASSERT_TRUE(TestUpdateCheck(
+                      &prefs,  // prefs
+                      params,
+                      GetUpdateResponse2(OmahaRequestParams::kAppId,
+                                         "1.2.3.4",  // version
+                                         "http://more/info",
+                                         "true",  // prompt
+                                         "http://code/base",  // dl url
+                                         "HASH1234=",  // checksum
+                                         "false",  // needs admin
+                                         "123",  // size
+                                         "",  // deadline
+                                         Time::Now(), // published on
+                                         "7"), // max days to scatter
+                      -1,
+                      false,  // ping_only
+                      kActionCodeSuccess,
+                      &response,
+                      NULL));
+
+  int64 count;
+  ASSERT_TRUE(prefs.GetInt64(kPrefsUpdateCheckCount, &count));
+  ASSERT_TRUE(count == 0);
+  EXPECT_TRUE(response.update_exists);
+}
+
+TEST(OmahaRequestActionTest, NonZeroUpdateCheckCountCausesScattering) {
+  OmahaResponse response;
+  OmahaRequestParams params = kDefaultTestParams;
+  params.wall_clock_based_wait_enabled = true;
+  params.waiting_period = TimeDelta();
+
+  params.update_check_count_wait_enabled = true;
+  params.min_update_checks_needed = 1;
+  params.max_update_checks_allowed = 8;
+
+  string prefs_dir;
+  EXPECT_TRUE(utils::MakeTempDirectory("/tmp/ue_ut_prefs.XXXXXX",
+                                       &prefs_dir));
+  ScopedDirRemover temp_dir_remover(prefs_dir);
+
+  Prefs prefs;
+  LOG_IF(ERROR, !prefs.Init(FilePath(prefs_dir)))
+      << "Failed to initialize preferences.";
+
+  ASSERT_FALSE(TestUpdateCheck(
+                      &prefs,  // prefs
+                      params,
+                      GetUpdateResponse2(OmahaRequestParams::kAppId,
+                                         "1.2.3.4",  // version
+                                         "http://more/info",
+                                         "true",  // prompt
+                                         "http://code/base",  // dl url
+                                         "HASH1234=",  // checksum
+                                         "false",  // needs admin
+                                         "123",  // size
+                                         "",  // deadline
+                                         Time::Now(), // published on
+                                         "7"), // max days to scatter
+                      -1,
+                      false,  // ping_only
+                      kActionCodeOmahaUpdateDeferredPerPolicy,
+                      &response,
+                      NULL));
+
+  int64 count;
+  ASSERT_TRUE(prefs.GetInt64(kPrefsUpdateCheckCount, &count));
+  ASSERT_TRUE(count > 0);
+  EXPECT_FALSE(response.update_exists);
+}
+
+TEST(OmahaRequestActionTest, ExistingUpdateCheckCountCausesScattering) {
+  OmahaResponse response;
+  OmahaRequestParams params = kDefaultTestParams;
+  params.wall_clock_based_wait_enabled = true;
+  params.waiting_period = TimeDelta();
+
+  params.update_check_count_wait_enabled = true;
+  params.min_update_checks_needed = 1;
+  params.max_update_checks_allowed = 8;
+
+  string prefs_dir;
+  EXPECT_TRUE(utils::MakeTempDirectory("/tmp/ue_ut_prefs.XXXXXX",
+                                       &prefs_dir));
+  ScopedDirRemover temp_dir_remover(prefs_dir);
+
+  Prefs prefs;
+  LOG_IF(ERROR, !prefs.Init(FilePath(prefs_dir)))
+      << "Failed to initialize preferences.";
+
+  ASSERT_TRUE(prefs.SetInt64(kPrefsUpdateCheckCount, 5));
+
+  ASSERT_FALSE(TestUpdateCheck(
+                      &prefs,  // prefs
+                      params,
+                      GetUpdateResponse2(OmahaRequestParams::kAppId,
+                                         "1.2.3.4",  // version
+                                         "http://more/info",
+                                         "true",  // prompt
+                                         "http://code/base",  // dl url
+                                         "HASH1234=",  // checksum
+                                         "false",  // needs admin
+                                         "123",  // size
+                                         "",  // deadline
+                                         Time::Now(), // published on
+                                         "7"), // max days to scatter
+                      -1,
+                      false,  // ping_only
+                      kActionCodeOmahaUpdateDeferredPerPolicy,
+                      &response,
+                      NULL));
+
+  int64 count;
+  ASSERT_TRUE(prefs.GetInt64(kPrefsUpdateCheckCount, &count));
+  // count remains the same, as the decrementing happens in update_attempter
+  // which this test doesn't exercise.
+  ASSERT_TRUE(count == 5);
+  EXPECT_FALSE(response.update_exists);
+}
 
 TEST(OmahaRequestActionTest, NoOutputPipeTest) {
   const string http_response(GetNoUpdateResponse(OmahaRequestParams::kAppId));
@@ -317,7 +607,8 @@
   GMainLoop *loop = g_main_loop_new(g_main_context_default(), FALSE);
 
   NiceMock<PrefsMock> prefs;
-  OmahaRequestAction action(&prefs, kDefaultTestParams, NULL,
+  OmahaRequestParams params = kDefaultTestParams;
+  OmahaRequestAction action(&prefs, &params, NULL,
                             new MockHttpFetcher(http_response.data(),
                                                 http_response.size(),
                                                 NULL),
@@ -473,7 +764,8 @@
   GMainLoop *loop = g_main_loop_new(g_main_context_default(), FALSE);
 
   NiceMock<PrefsMock> prefs;
-  OmahaRequestAction action(&prefs, kDefaultTestParams, NULL,
+  OmahaRequestParams params = kDefaultTestParams;
+  OmahaRequestAction action(&prefs, &params, NULL,
                             new MockHttpFetcher(http_response.data(),
                                                 http_response.size(),
                                                 NULL),
@@ -511,7 +803,7 @@
                             false,  // delta okay
                             "http://url",
                             false,   // update_disabled
-                            ""); // target_version_prefix
+                            "");  // target_version_prefix
   OmahaResponse response;
   ASSERT_FALSE(
       TestUpdateCheck(NULL,  // prefs
@@ -680,9 +972,10 @@
 TEST(OmahaRequestActionTest, IsEventTest) {
   string http_response("doesn't matter");
   NiceMock<PrefsMock> prefs;
+  OmahaRequestParams params = kDefaultTestParams;
   OmahaRequestAction update_check_action(
       &prefs,
-      kDefaultTestParams,
+      &params,
       NULL,
       new MockHttpFetcher(http_response.data(),
                           http_response.size(),
@@ -690,9 +983,10 @@
       false);
   EXPECT_FALSE(update_check_action.IsEvent());
 
+  params = kDefaultTestParams;
   OmahaRequestAction event_action(
       &prefs,
-      kDefaultTestParams,
+      &params,
       new OmahaEvent(OmahaEvent::kTypeUpdateComplete),
       new MockHttpFetcher(http_response.data(),
                           http_response.size(),
diff --git a/omaha_request_params.h b/omaha_request_params.h
index 482a8b7..7435468 100644
--- a/omaha_request_params.h
+++ b/omaha_request_params.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2011 The Chromium OS Authors. All rights reserved.
+// Copyright (c) 2012 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -8,6 +8,7 @@
 #include <string>
 
 #include <base/basictypes.h>
+#include <base/time.h>
 #include <gtest/gtest_prod.h>  // for FRIEND_TEST
 
 // This gathers local system information and prepares info used by the
@@ -15,8 +16,11 @@
 
 namespace chromeos_update_engine {
 
-// This struct encapsulates the data Omaha gets for the request.
-// These strings in this struct should not be XML escaped.
+// This struct encapsulates the data Omaha gets for the request, along with
+// essential state needed for the processing of the request/response.
+// The strings in this struct should not be XML escaped.
+// TODO (jaysri): Consider renaming this to reflect its lifetime more
+// appropriately.
 struct OmahaRequestParams {
 
   OmahaRequestParams()
@@ -24,7 +28,11 @@
         os_version(kOsVersion),
         app_id(kAppId),
         delta_okay(true),
-        update_disabled(false) {}
+        update_disabled(false),
+        wall_clock_based_wait_enabled(false),
+        update_check_count_wait_enabled(false),
+        min_update_checks_needed(kDefaultMinUpdateChecks),
+        max_update_checks_allowed(kDefaultMaxUpdateChecks) {}
 
   OmahaRequestParams(const std::string& in_os_platform,
                      const std::string& in_os_version,
@@ -51,7 +59,11 @@
         delta_okay(in_delta_okay),
         update_url(in_update_url),
         update_disabled(in_update_disabled),
-        target_version_prefix(in_target_version_prefix) {}
+        target_version_prefix(in_target_version_prefix),
+        wall_clock_based_wait_enabled(false),
+        update_check_count_wait_enabled(false),
+        min_update_checks_needed(kDefaultMinUpdateChecks),
+        max_update_checks_allowed(kDefaultMaxUpdateChecks) {}
 
   std::string os_platform;
   std::string os_version;
@@ -71,11 +83,20 @@
   bool update_disabled;
   std::string target_version_prefix;
 
+  bool wall_clock_based_wait_enabled;
+  base::TimeDelta waiting_period;
+
+  bool update_check_count_wait_enabled;
+  int64 min_update_checks_needed;
+  int64 max_update_checks_allowed;
+
   // Suggested defaults
   static const char* const kAppId;
   static const char* const kOsPlatform;
   static const char* const kOsVersion;
   static const char* const kUpdateUrl;
+  static const int64 kDefaultMinUpdateChecks = 0;
+  static const int64 kDefaultMaxUpdateChecks = 8;
 };
 
 class OmahaRequestDeviceParams : public OmahaRequestParams {
diff --git a/prefs.cc b/prefs.cc
index 067f768..cb6e4f7 100644
--- a/prefs.cc
+++ b/prefs.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2011 The Chromium OS Authors. All rights reserved.
+// Copyright (c) 2012 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -33,6 +33,8 @@
 const char kPrefsUpdateStateSignatureBlob[] = "update-state-signature-blob";
 const char kPrefsUpdateStateSignedSHA256Context[] =
     "update-state-signed-sha-256-context";
+const char kPrefsUpdateCheckCount[] = "update-check-count";
+const char kPrefsWallClockWaitPeriod[] = "wall-clock-wait-period";
 
 bool Prefs::Init(const FilePath& prefs_dir) {
   prefs_dir_ = prefs_dir;
@@ -43,8 +45,6 @@
   FilePath filename;
   TEST_AND_RETURN_FALSE(GetFileNameForKey(key, &filename));
   if (!file_util::ReadFileToString(filename, value)) {
-    PLOG(INFO) << "Unable to read prefs from " << filename.value()
-               << ". This is likely harmless.";
     return false;
   }
   return true;
@@ -72,6 +72,18 @@
   return SetString(key, base::Int64ToString(value));
 }
 
+bool Prefs::Exists(const string& key) {
+  FilePath filename;
+  TEST_AND_RETURN_FALSE(GetFileNameForKey(key, &filename));
+  return file_util::PathExists(filename);
+}
+
+bool Prefs::Delete(const string& key) {
+  FilePath filename;
+  TEST_AND_RETURN_FALSE(GetFileNameForKey(key, &filename));
+  return file_util::Delete(filename, false);
+}
+
 bool Prefs::GetFileNameForKey(const std::string& key, FilePath* filename) {
   // Allows only non-empty keys containing [A-Za-z0-9_-].
   TEST_AND_RETURN_FALSE(!key.empty());
diff --git a/prefs.h b/prefs.h
index cccfed5..e128eda 100644
--- a/prefs.h
+++ b/prefs.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Copyright (c) 2012 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -30,6 +30,9 @@
   bool GetInt64(const std::string& key, int64_t* value);
   bool SetInt64(const std::string& key, const int64_t value);
 
+  bool Exists(const std::string& key);
+  bool Delete(const std::string& key);
+
  private:
   FRIEND_TEST(PrefsTest, GetFileNameForKey);
   FRIEND_TEST(PrefsTest, GetFileNameForKeyBadCharacter);
diff --git a/prefs_interface.h b/prefs_interface.h
index 624005e..3cb4059 100644
--- a/prefs_interface.h
+++ b/prefs_interface.h
@@ -24,6 +24,8 @@
 extern const char kPrefsUpdateStateSHA256Context[];
 extern const char kPrefsUpdateStateSignatureBlob[];
 extern const char kPrefsUpdateStateSignedSHA256Context[];
+extern const char kPrefsUpdateCheckCount[];
+extern const char kPrefsWallClockWaitPeriod[];
 
 // The prefs interface allows access to a persistent preferences
 // store. The two reasons for providing this as an interface are
@@ -50,6 +52,14 @@
   // false otherwise.
   virtual bool SetInt64(const std::string& key, const int64_t value) = 0;
 
+  // Returns true if the setting exists (i.e. a file with the given key
+  // exists in the prefs directory)
+  virtual bool Exists(const std::string& key) = 0;
+
+  // Returns true if successfully deleted the file corresponding to
+  // this key. Calling with non-existent keys does nothing.
+  virtual bool Delete(const std::string& key) = 0;
+
   virtual ~PrefsInterface() {}
 };
 
diff --git a/prefs_mock.h b/prefs_mock.h
index cf030f0..963b981 100644
--- a/prefs_mock.h
+++ b/prefs_mock.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Copyright (c) 2012 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -17,6 +17,9 @@
                                const std::string& value));
   MOCK_METHOD2(GetInt64, bool(const std::string& key, int64_t* value));
   MOCK_METHOD2(SetInt64, bool(const std::string& key, const int64_t value));
+
+  MOCK_METHOD1(Exists, bool(const std::string& key));
+  MOCK_METHOD1(Delete, bool(const std::string& key));
 };
 
 }  // namespace chromeos_update_engine
diff --git a/prefs_unittest.cc b/prefs_unittest.cc
index 54a637e..87c41b6 100644
--- a/prefs_unittest.cc
+++ b/prefs_unittest.cc
@@ -187,4 +187,29 @@
   EXPECT_EQ(StringPrintf("%" PRIi64, kint64min), value);
 }
 
+TEST_F(PrefsTest, ExistsWorks) {
+  const char kKey[] = "exists-key";
+
+  // test that the key doesn't exist before we set it.
+  EXPECT_FALSE(prefs_.Exists(kKey));
+
+  // test that the key exists after we set it.
+  ASSERT_TRUE(prefs_.SetInt64(kKey, 8));
+  EXPECT_TRUE(prefs_.Exists(kKey));
+}
+
+TEST_F(PrefsTest, DeleteWorks) {
+  const char kKey[] = "delete-key";
+
+  // test that it's alright to delete a non-existent key.
+  EXPECT_TRUE(prefs_.Delete(kKey));
+
+  // delete the key after we set it.
+  ASSERT_TRUE(prefs_.SetInt64(kKey, 0));
+  EXPECT_TRUE(prefs_.Delete(kKey));
+
+  // make sure it doesn't exist anymore.
+  EXPECT_FALSE(prefs_.Exists(kKey));
+}
+
 }  // namespace chromeos_update_engine
diff --git a/update_attempter.cc b/update_attempter.cc
index d6c5496..da9e7cc 100644
--- a/update_attempter.cc
+++ b/update_attempter.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2011 The Chromium OS Authors. All rights reserved.
+// Copyright (c) 2012 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -132,7 +132,8 @@
       policy_provider_(NULL),
       is_using_test_url_(false),
       is_test_update_attempted_(false),
-      gpio_handler_(gpio_handler) {
+      gpio_handler_(gpio_handler),
+      init_waiting_period_from_prefs_(true) {
   if (utils::FileExists(kUpdateCompletedMarker))
     status_ = UPDATE_STATUS_UPDATED_NEED_REBOOT;
 }
@@ -160,6 +161,31 @@
     // Update in progress. Do nothing
     return;
   }
+
+  if (!CalculateUpdateParams(app_version,
+                             omaha_url,
+                             obey_proxies,
+                             interactive,
+                             is_test)) {
+    return;
+  }
+
+  BuildUpdateActions(interactive);
+
+  SetStatusAndNotify(UPDATE_STATUS_CHECKING_FOR_UPDATE,
+                     kUpdateNoticeUnspecified);
+
+  // Just in case we didn't update boot flags yet, make sure they're updated
+  // before any update processing starts.
+  start_action_processor_ = true;
+  UpdateBootFlags();
+}
+
+bool UpdateAttempter::CalculateUpdateParams(const string& app_version,
+                                            const string& omaha_url,
+                                            bool obey_proxies,
+                                            bool interactive,
+                                            bool is_test) {
   http_response_code_ = 0;
 
   // Lazy initialize the policy provider, or reload the latest policy data.
@@ -171,6 +197,9 @@
 
   // If the release_track is specified by policy, that takes precedence.
   string release_track;
+
+  // Take a copy of the old scatter value before we update it.
+  int64 old_scatter_factor_in_secs = scatter_factor_.InSeconds();
   if (policy_provider_->device_policy_is_loaded()) {
     const policy::DevicePolicy& device_policy =
                                 policy_provider_->GetDevicePolicy();
@@ -178,6 +207,63 @@
     device_policy.GetUpdateDisabled(&omaha_request_params_.update_disabled);
     device_policy.GetTargetVersionPrefix(
       &omaha_request_params_.target_version_prefix);
+    int64 new_scatter_factor_in_secs = 0;
+    device_policy.GetScatterFactorInSeconds(&new_scatter_factor_in_secs);
+    scatter_factor_ = TimeDelta::FromSeconds(new_scatter_factor_in_secs);
+  }
+
+  if (scatter_factor_.InSeconds() != old_scatter_factor_in_secs) {
+    int64 wait_period_in_secs = 0;
+    if (init_waiting_period_from_prefs_ &&
+        prefs_->GetInt64(kPrefsWallClockWaitPeriod, &wait_period_in_secs) &&
+        wait_period_in_secs >= 0 &&
+        wait_period_in_secs <= scatter_factor_.InSeconds()) {
+      // This means:
+      // 1. This is the first update check to come this far in this process.
+      // 2. There's a persisted value for the waiting period available.
+      // 3. And that persisted value is still valid.
+      // So, in this case, we should reuse the persisted value instead of
+      // generating a new random value to improve the chances of a good
+      // distribution for scattering.
+      omaha_request_params_.waiting_period =
+        TimeDelta::FromSeconds(wait_period_in_secs);
+      LOG(INFO) << "Using persisted value for wall clock based waiting period.";
+    } else {
+      // In this case, we should regenerate the waiting period to make sure
+      // it's within the bounds of the new scatter factor value.
+      omaha_request_params_.waiting_period = TimeDelta::FromSeconds(
+          base::RandInt(0, scatter_factor_.InSeconds()));
+
+      LOG(INFO) << "Generated new value of " << utils::FormatSecs(
+                    omaha_request_params_.waiting_period.InSeconds())
+                << " for wall clock based waiting period.";
+
+      // Do a best-effort to persist this. We'll work fine even if the
+      // persistence fails.
+      prefs_->SetInt64(kPrefsWallClockWaitPeriod,
+                       omaha_request_params_.waiting_period.InSeconds());
+    }
+  }
+
+  // We should reset this value since we're past the first initialization
+  // of the waiting period for this process.
+  init_waiting_period_from_prefs_ = false;
+
+  if (scatter_factor_.InSeconds() == 0) {
+    // This means the scattering feature is turned off. Make sure to disable
+    // all the knobs so that we don't invoke any scattering related code.
+    omaha_request_params_.wall_clock_based_wait_enabled = false;
+    omaha_request_params_.update_check_count_wait_enabled = false;
+    prefs_->Delete(kPrefsWallClockWaitPeriod);
+    prefs_->Delete(kPrefsUpdateCheckCount);
+  } else {
+    // This means the scattering policy is turned on. We'll do wall-clock-
+    // based-wait by default. And if we don't have any issues in accessing
+    // the file system to do update the update check count value, we'll
+    // turn that on as well.
+    omaha_request_params_.wall_clock_based_wait_enabled = true;
+    bool decrement_succeeded = DecrementUpdateCheckCount();
+    omaha_request_params_.update_check_count_wait_enabled = decrement_succeeded;
   }
 
   // Determine whether an alternative test address should be used.
@@ -191,13 +277,23 @@
                                   omaha_url_to_use,
                                   release_track)) {
     LOG(ERROR) << "Unable to initialize Omaha request device params.";
-    return;
+    return false;
   }
 
   LOG(INFO) << "update_disabled = "
             << (omaha_request_params_.update_disabled ? "true" : "false")
             << ", target_version_prefix = "
-            << omaha_request_params_.target_version_prefix;
+            << omaha_request_params_.target_version_prefix
+            << ", scatter_factor_in_seconds = "
+            << utils::FormatSecs(scatter_factor_.InSeconds());
+
+  LOG(INFO) << "Wall Clock Based Wait Enabled = "
+            << omaha_request_params_.wall_clock_based_wait_enabled
+            << ", Update Check Count Wait Enabled = "
+            << omaha_request_params_.update_check_count_wait_enabled
+            << ", Waiting Period = "
+            << utils::FormatSecs(
+                   omaha_request_params_.waiting_period.InSeconds());
 
   obeying_proxies_ = true;
   if (obey_proxies || proxy_manual_checks_ == 0) {
@@ -217,6 +313,10 @@
       "direct connections.";
 
   DisableDeltaUpdateIfNeeded();
+  return true;
+}
+
+void UpdateAttempter::BuildUpdateActions(bool interactive) {
   CHECK(!processor_->IsRunning());
   processor_->set_delegate(this);
 
@@ -229,7 +329,7 @@
   update_check_fetcher->set_check_certificate(CertificateChecker::kUpdate);
   shared_ptr<OmahaRequestAction> update_check_action(
       new OmahaRequestAction(prefs_,
-                             omaha_request_params_,
+                             &omaha_request_params_,
                              NULL,
                              update_check_fetcher,  // passes ownership
                              false));
@@ -241,7 +341,7 @@
       new FilesystemCopierAction(true, false));
   shared_ptr<OmahaRequestAction> download_started_action(
       new OmahaRequestAction(prefs_,
-                             omaha_request_params_,
+                             &omaha_request_params_,
                              new OmahaEvent(
                                  OmahaEvent::kTypeUpdateDownloadStarted),
                              new LibcurlHttpFetcher(GetProxyResolver()),
@@ -255,7 +355,7 @@
                              download_fetcher)));  // passes ownership
   shared_ptr<OmahaRequestAction> download_finished_action(
       new OmahaRequestAction(prefs_,
-                             omaha_request_params_,
+                             &omaha_request_params_,
                              new OmahaEvent(
                                  OmahaEvent::kTypeUpdateDownloadFinished),
                              new LibcurlHttpFetcher(GetProxyResolver()),
@@ -268,7 +368,7 @@
       new PostinstallRunnerAction);
   shared_ptr<OmahaRequestAction> update_complete_action(
       new OmahaRequestAction(prefs_,
-                             omaha_request_params_,
+                             &omaha_request_params_,
                              new OmahaEvent(OmahaEvent::kTypeUpdateComplete),
                              new LibcurlHttpFetcher(GetProxyResolver()),
                              false));
@@ -313,14 +413,6 @@
               kernel_filesystem_verifier_action.get());
   BondActions(kernel_filesystem_verifier_action.get(),
               postinstall_runner_action.get());
-
-  SetStatusAndNotify(UPDATE_STATUS_CHECKING_FOR_UPDATE,
-                     kUpdateNoticeUnspecified);
-
-  // Just in case we didn't update boot flags yet, make sure they're updated
-  // before any update processing starts.
-  start_action_processor_ = true;
-  UpdateBootFlags();
 }
 
 void UpdateAttempter::CheckForUpdate(const string& app_version,
@@ -385,6 +477,19 @@
     prefs_->SetInt64(kPrefsDeltaUpdateFailures, 0);
     prefs_->SetString(kPrefsPreviousVersion, omaha_request_params_.app_version);
     DeltaPerformer::ResetUpdateProgress(prefs_, false);
+
+    // Since we're done with scattering fully at this point, this is the
+    // safest point delete the state files, as we're sure that the status is
+    // set to reboot (which means no more updates will be applied until reboot)
+    // This deletion is required for correctness as we want the next update
+    // check to re-create a new random number for the update check count.
+    // Similarly, we also delete the wall-clock-wait period that was persisted
+    // so that we start with a new random value for the next update check
+    // after reboot so that the same device is not favored or punished in any
+    // way.
+    prefs_->Delete(kPrefsUpdateCheckCount);
+    prefs_->Delete(kPrefsWallClockWaitPeriod);
+
     SetStatusAndNotify(UPDATE_STATUS_UPDATED_NEED_REBOOT,
                        kUpdateNoticeUnspecified);
 
@@ -645,7 +750,7 @@
   LOG(INFO) << "Update failed -- reporting the error event.";
   shared_ptr<OmahaRequestAction> error_event_action(
       new OmahaRequestAction(prefs_,
-                             omaha_request_params_,
+                             &omaha_request_params_,
                              error_event_.release(),  // Pass ownership.
                              new LibcurlHttpFetcher(GetProxyResolver()),
                              false));
@@ -759,7 +864,7 @@
   if (!processor_->IsRunning()) {
     shared_ptr<OmahaRequestAction> ping_action(
         new OmahaRequestAction(prefs_,
-                               omaha_request_params_,
+                               &omaha_request_params_,
                                NULL,
                                new LibcurlHttpFetcher(GetProxyResolver()),
                                true));
@@ -786,4 +891,53 @@
                      kUpdateNoticeUnspecified);
 }
 
+
+bool UpdateAttempter::DecrementUpdateCheckCount() {
+  int64 update_check_count_value;
+
+  if (!prefs_->Exists(kPrefsUpdateCheckCount)) {
+    // This file does not exist. This means we haven't started our update
+    // check count down yet, so nothing more to do. This file will be created
+    // later when we first satisfy the wall-clock-based-wait period.
+    LOG(INFO) << "No existing update check count. That's normal.";
+    return true;
+  }
+
+  if (prefs_->GetInt64(kPrefsUpdateCheckCount, &update_check_count_value)) {
+    // Only if we're able to read a proper integer value, then go ahead
+    // and decrement and write back the result in the same file, if needed.
+    LOG(INFO) << "Update check count = " << update_check_count_value;
+
+    if (update_check_count_value == 0) {
+      // It could be 0, if, for some reason, the file didn't get deleted
+      // when we set our status to waiting for reboot. so we just leave it
+      // as is so that we can prevent another update_check wait for this client.
+      LOG(INFO) << "Not decrementing update check count as it's already 0.";
+      return true;
+    }
+
+    if (update_check_count_value > 0)
+      update_check_count_value--;
+    else
+      update_check_count_value = 0;
+
+    // Write out the new value of update_check_count_value.
+    if (prefs_->SetInt64(kPrefsUpdateCheckCount, update_check_count_value)) {
+      // We successfully wrote out te new value, so enable the
+      // update check based wait.
+      LOG(INFO) << "New update check count = " << update_check_count_value;
+      return true;
+    }
+  }
+
+  LOG(INFO) << "Deleting update check count state due to read/write errors.";
+
+  // We cannot read/write to the file, so disable the update check based wait
+  // so that we don't get stuck in this OS version by any chance (which could
+  // happen if there's some bug that causes to read/write incorrectly).
+  // Also attempt to delete the file to do our best effort to cleanup.
+  prefs_->Delete(kPrefsUpdateCheckCount);
+  return false;
+}
+
 }  // namespace chromeos_update_engine
diff --git a/update_attempter.h b/update_attempter.h
index 950163e..b38367d 100644
--- a/update_attempter.h
+++ b/update_attempter.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2011 The Chromium OS Authors. All rights reserved.
+// Copyright (c) 2012 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -225,6 +225,24 @@
   // update has been applied.
   void PingOmaha();
 
+  // Helper method of Update() to calculate the update-related parameters
+  // from various sources and set the appropriate state. Please refer to
+  // Update() method for the meaning of the parametes.
+  bool CalculateUpdateParams(const std::string& app_version,
+                             const std::string& omaha_url,
+                             bool obey_proxies,
+                             bool interactive,
+                             bool is_test);
+
+  // Helper method of Update() to construct the sequence of actions to
+  // be performed for an update check. Please refer to
+  // Update() method for the meaning of the parametes.
+  void BuildUpdateActions(bool interactive);
+
+  // Decrements the count in the kUpdateCheckCountFilePath.
+  // Returns True if successfully decremented, false otherwise.
+  bool DecrementUpdateCheckCount();
+
   // Last status notification timestamp used for throttling. Use monotonic
   // TimeTicks to ensure that notifications are sent even if the system clock is
   // set back in the middle of an update.
@@ -315,6 +333,13 @@
   // GPIO handler object.
   GpioHandler* gpio_handler_;
 
+  // The current scatter factor as found in the policy setting.
+  base::TimeDelta scatter_factor_;
+
+  // True if we have to initialize the waiting period in prefs, if available.
+  // False otherwise.
+  bool init_waiting_period_from_prefs_;
+
   DISALLOW_COPY_AND_ASSIGN(UpdateAttempter);
 };
 
diff --git a/update_attempter_unittest.cc b/update_attempter_unittest.cc
index 04648e3..5a0bed6 100644
--- a/update_attempter_unittest.cc
+++ b/update_attempter_unittest.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2011 The Chromium OS Authors. All rights reserved.
+// Copyright (c) 2012 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -13,6 +13,7 @@
 #include "update_engine/mock_dbus_interface.h"
 #include "update_engine/mock_http_fetcher.h"
 #include "update_engine/postinstall_runner_action.h"
+#include "update_engine/prefs.h"
 #include "update_engine/prefs_mock.h"
 #include "update_engine/test_utils.h"
 #include "update_engine/update_attempter.h"
@@ -82,6 +83,14 @@
   static gboolean StaticReadTargetVersionPrefixFromPolicyTestStart(
       gpointer data);
 
+  void ReadScatterFactorFromPolicyTestStart();
+  static gboolean StaticReadScatterFactorFromPolicyTestStart(
+      gpointer data);
+
+  void DecrementUpdateCheckCountTestStart();
+  static gboolean StaticDecrementUpdateCheckCountTestStart(
+      gpointer data);
+
   MockDbusGlib dbus_;
   UpdateAttempterUnderTest attempter_;
   ActionProcessorMock* processor_;
@@ -114,7 +123,7 @@
   scoped_ptr<MockHttpFetcher> fetcher(new MockHttpFetcher("", 0, NULL));
   fetcher->FailTransfer(500);  // Sets the HTTP response code.
   OmahaRequestParams params;
-  OmahaRequestAction action(&prefs_, params, NULL, fetcher.release(), false);
+  OmahaRequestAction action(&prefs_, &params, NULL, fetcher.release(), false);
   ObjectCollectorAction<OmahaResponse> collector_action;
   BondActions(&action, &collector_action);
   OmahaResponse response;
@@ -147,7 +156,7 @@
             GetErrorCodeForAction(NULL, kActionCodeSuccess));
 
   OmahaRequestParams params;
-  OmahaRequestAction omaha_request_action(NULL, params, NULL, NULL, false);
+  OmahaRequestAction omaha_request_action(NULL, &params, NULL, NULL, false);
   EXPECT_EQ(kActionCodeOmahaRequestError,
             GetErrorCodeForAction(&omaha_request_action, kActionCodeError));
   OmahaResponseHandlerAction omaha_response_handler_action(&prefs_);
@@ -293,6 +302,20 @@
   return FALSE;
 }
 
+gboolean UpdateAttempterTest::StaticReadScatterFactorFromPolicyTestStart(
+    gpointer data) {
+  UpdateAttempterTest* ua_test = reinterpret_cast<UpdateAttempterTest*>(data);
+  ua_test->ReadScatterFactorFromPolicyTestStart();
+  return FALSE;
+}
+
+gboolean UpdateAttempterTest::StaticDecrementUpdateCheckCountTestStart(
+    gpointer data) {
+  UpdateAttempterTest* ua_test = reinterpret_cast<UpdateAttempterTest*>(data);
+  ua_test->DecrementUpdateCheckCountTestStart();
+  return FALSE;
+}
+
 namespace {
 const string kActionTypes[] = {
   OmahaRequestAction::StaticType(),
@@ -485,4 +508,92 @@
 }
 
 
+TEST_F(UpdateAttempterTest, ReadScatterFactorFromPolicy) {
+  loop_ = g_main_loop_new(g_main_context_default(), FALSE);
+  g_idle_add(&StaticReadScatterFactorFromPolicyTestStart, this);
+  g_main_loop_run(loop_);
+  g_main_loop_unref(loop_);
+  loop_ = NULL;
+}
+
+// Tests that the scatter_factor_in_seconds value is properly fetched
+// from the device policy.
+void UpdateAttempterTest::ReadScatterFactorFromPolicyTestStart() {
+  int64 scatter_factor_in_seconds = 36000;
+
+  policy::MockDevicePolicy* device_policy = new policy::MockDevicePolicy();
+  attempter_.policy_provider_.reset(new policy::PolicyProvider(device_policy));
+
+  EXPECT_CALL(*device_policy, LoadPolicy()).WillRepeatedly(Return(true));
+
+  EXPECT_CALL(*device_policy, GetScatterFactorInSeconds(_))
+      .WillRepeatedly(DoAll(
+          SetArgumentPointee<0>(scatter_factor_in_seconds),
+          Return(true)));
+
+  attempter_.Update("", "", false, false, false);
+  EXPECT_EQ(scatter_factor_in_seconds, attempter_.scatter_factor_.InSeconds());
+
+  g_idle_add(&StaticQuitMainLoop, this);
+}
+
+TEST_F(UpdateAttempterTest, DecrementUpdateCheckCountTest) {
+  loop_ = g_main_loop_new(g_main_context_default(), FALSE);
+  g_idle_add(&StaticDecrementUpdateCheckCountTestStart, this);
+  g_main_loop_run(loop_);
+  g_main_loop_unref(loop_);
+  loop_ = NULL;
+}
+
+void UpdateAttempterTest::DecrementUpdateCheckCountTestStart() {
+  // Tests that the scatter_factor_in_seconds value is properly fetched
+  // from the device policy and is decremented if value > 0.
+  int64 initial_value = 5;
+  Prefs prefs;
+  attempter_.prefs_ = &prefs;
+
+  string prefs_dir;
+  EXPECT_TRUE(utils::MakeTempDirectory("/tmp/ue_ut_prefs.XXXXXX",
+                                       &prefs_dir));
+  ScopedDirRemover temp_dir_remover(prefs_dir);
+
+  LOG_IF(ERROR, !prefs.Init(FilePath(prefs_dir)))
+      << "Failed to initialize preferences.";
+  EXPECT_TRUE(prefs.SetInt64(kPrefsUpdateCheckCount, initial_value));
+
+  int64 scatter_factor_in_seconds = 10;
+
+  policy::MockDevicePolicy* device_policy = new policy::MockDevicePolicy();
+  attempter_.policy_provider_.reset(new policy::PolicyProvider(device_policy));
+
+  EXPECT_CALL(*device_policy, LoadPolicy()).WillRepeatedly(Return(true));
+
+  EXPECT_CALL(*device_policy, GetScatterFactorInSeconds(_))
+      .WillRepeatedly(DoAll(
+          SetArgumentPointee<0>(scatter_factor_in_seconds),
+          Return(true)));
+
+  attempter_.Update("", "", false, false, false);
+  EXPECT_EQ(scatter_factor_in_seconds, attempter_.scatter_factor_.InSeconds());
+
+  // Make sure the file still exists.
+  EXPECT_TRUE(prefs.Exists(kPrefsUpdateCheckCount));
+
+  int64 new_value;
+  EXPECT_TRUE(prefs.GetInt64(kPrefsUpdateCheckCount, &new_value));
+  EXPECT_EQ(initial_value - 1, new_value);
+
+  EXPECT_TRUE(attempter_.omaha_request_params_.update_check_count_wait_enabled);
+
+  // However, if the count is already 0, it's not decremented. Test that.
+  initial_value = 0;
+  EXPECT_TRUE(prefs.SetInt64(kPrefsUpdateCheckCount, initial_value));
+  attempter_.Update("", "", false, false, false);
+  EXPECT_TRUE(prefs.Exists(kPrefsUpdateCheckCount));
+  EXPECT_TRUE(prefs.GetInt64(kPrefsUpdateCheckCount, &new_value));
+  EXPECT_EQ(initial_value, new_value);
+
+  g_idle_add(&StaticQuitMainLoop, this);
+}
+
 }  // namespace chromeos_update_engine
diff --git a/utils.cc b/utils.cc
index 1cdcc5c..bf9267c 100644
--- a/utils.cc
+++ b/utils.cc
@@ -24,6 +24,7 @@
 #include <base/file_util.h>
 #include <base/logging.h>
 #include <base/rand_util.h>
+#include <base/string_number_conversions.h>
 #include <base/string_util.h>
 #include <base/stringprintf.h>
 #include <google/protobuf/stubs/common.h>
@@ -33,6 +34,7 @@
 #include "update_engine/omaha_request_params.h"
 #include "update_engine/subprocess.h"
 
+using base::Time;
 using std::min;
 using std::string;
 using std::vector;
@@ -43,6 +45,7 @@
 
 static const char kOOBECompletedMarker[] = "/home/chronos/.oobe_completed";
 static const char kDevImageMarker[] = "/root/.dev_mode";
+const char* const kStatefulPartition = "/mnt/stateful_partition";
 
 bool IsOfficialBuild() {
   return !file_util::PathExists(FilePath(kDevImageMarker));
@@ -626,7 +629,17 @@
   return str;
 }
 
-const char* const kStatefulPartition = "/mnt/stateful_partition";
+string ToString(const Time utc_time) {
+  Time::Exploded exp_time;
+  utc_time.UTCExplode(&exp_time);
+  return StringPrintf("%d/%d/%d %d:%02d:%02d GMT",
+                      exp_time.month,
+                      exp_time.day_of_month,
+                      exp_time.year,
+                      exp_time.hour,
+                      exp_time.minute,
+                      exp_time.second);
+}
 
 }  // namespace utils
 
diff --git a/utils.h b/utils.h
index 7d64ee2..cce30ca 100644
--- a/utils.h
+++ b/utils.h
@@ -90,7 +90,7 @@
                   std::string* filename,
                   int* fd);
 
-// Calls mkdtemp() with the tempate passed. Returns the generated dirname
+// Calls mkdtemp() with the template passed. Returns the generated dirname
 // in the dirname param. Returns TRUE on success. dirname must not be NULL.
 bool MakeTempDirectory(const std::string& dirname_template,
                        std::string* dirname);
@@ -136,6 +136,10 @@
                              int* out_block_count,
                              int* out_block_size);
 
+// Returns the string representation of the given UTC time.
+// such as "11/14/2011 14:05:30 GMT".
+std::string ToString(const base::Time utc_time);
+
 enum BootLoader {
   BootLoader_SYSLINUX = 0,
   BootLoader_CHROME_FIRMWARE = 1