diff --git a/update_manager/chromeos_policy.cc b/update_manager/chromeos_policy.cc
index cba74e2..c49e3a7 100644
--- a/update_manager/chromeos_policy.cc
+++ b/update_manager/chromeos_policy.cc
@@ -211,7 +211,7 @@
       EvalStatus::kSucceeded) {
     return EvalStatus::kFailed;
   }
-  if (!ec->IsTimeGreaterThan(next_update_check))
+  if (!ec->IsWallclockTimeGreaterThan(next_update_check))
     return EvalStatus::kAskMeAgainLater;
 
   // It is time to check for an update.
@@ -604,7 +604,7 @@
   // the update, then no wait is needed.
   Time wait_expires = (update_state.first_seen +
                        min(wait_period, update_state.scatter_wait_period_max));
-  if (ec->IsTimeGreaterThan(wait_expires))
+  if (ec->IsWallclockTimeGreaterThan(wait_expires))
     wait_period = kZeroInterval;
 
   // Step 2: Maintain the update check threshold count.
diff --git a/update_manager/chromeos_policy.h b/update_manager/chromeos_policy.h
index c954f9d..889adbd 100644
--- a/update_manager/chromeos_policy.h
+++ b/update_manager/chromeos_policy.h
@@ -95,6 +95,10 @@
 
   // 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
+  // timestamp, which will make the update check intervals more resilient to
+  // clock skews. Might require switching some of the variables exported by the
+  // UpdaterProvider to report monotonic time, as well.
   EvalStatus NextUpdateCheckTime(EvaluationContext* ec, State* state,
                                  std::string* error,
                                  base::Time* next_update_check) const;
diff --git a/update_manager/evaluation_context.cc b/update_manager/evaluation_context.cc
index 2f827c1..2d5d705 100644
--- a/update_manager/evaluation_context.cc
+++ b/update_manager/evaluation_context.cc
@@ -20,6 +20,31 @@
 using chromeos_update_engine::ClockInterface;
 using std::string;
 
+namespace {
+
+// Returns whether |curr_time| surpassed |ref_time|; if not, also checks whether
+// |ref_time| is sooner than the current value of |*reeval_time|, in which case
+// the latter is updated to the former.
+bool IsTimeGreaterThanHelper(base::Time ref_time, base::Time curr_time,
+                             base::Time* reeval_time) {
+  if (curr_time > ref_time)
+    return true;
+  // Remember the nearest reference we've checked against in this evaluation.
+  if (*reeval_time > ref_time)
+    *reeval_time = ref_time;
+  return false;
+}
+
+// If |expires| never happens (maximal value), returns the maximal interval;
+// otherwise, returns the difference between |expires| and |curr|.
+TimeDelta GetTimeout(base::Time curr, base::Time expires) {
+  if (expires.is_max())
+    return TimeDelta::Max();
+  return expires - curr;
+}
+
+}  // namespace
+
 namespace chromeos_update_manager {
 
 EvaluationContext::EvaluationContext(ClockInterface* clock,
@@ -80,23 +105,22 @@
     callback->Run();
 }
 
-bool EvaluationContext::IsTimeGreaterThan(base::Time timestamp) {
-  if (evaluation_start_ > timestamp)
-    return true;
-  // We need to keep track of these calls to trigger a reevaluation.
-  if (reevaluation_time_ > timestamp)
-    reevaluation_time_ = timestamp;
-  return false;
+bool EvaluationContext::IsWallclockTimeGreaterThan(base::Time timestamp) {
+  return IsTimeGreaterThanHelper(timestamp, evaluation_start_wallclock_,
+                                 &reevaluation_time_wallclock_);
+}
+
+bool EvaluationContext::IsMonotonicTimeGreaterThan(base::Time timestamp) {
+  return IsTimeGreaterThanHelper(timestamp, evaluation_start_monotonic_,
+                                 &reevaluation_time_monotonic_);
 }
 
 void EvaluationContext::ResetEvaluation() {
-  // It is not important if these two values are not in sync. The first value is
-  // a reference in time when the evaluation started, to device time-based
-  // values for the current evaluation. The second is a deadline for the
-  // evaluation which required a monotonic source of time.
-  evaluation_start_ = clock_->GetWallclockTime();
+  evaluation_start_wallclock_ = clock_->GetWallclockTime();
+  evaluation_start_monotonic_ = clock_->GetMonotonicTime();
+  reevaluation_time_wallclock_ = Time::Max();
+  reevaluation_time_monotonic_ = Time::Max();
   evaluation_monotonic_deadline_ = MonotonicDeadline(evaluation_timeout_);
-  reevaluation_time_ = Time::Max();
 
   // Remove the cached values of non-const variables
   for (auto it = value_cache_.begin(); it != value_cache_.end(); ) {
@@ -121,14 +145,15 @@
     return false;
   }
 
-  TimeDelta timeout(TimeDelta::Max());
-  bool waiting_for_value_change = false;
-
-  // Handle reevaluation due to a IsTimeGreaterThan() call.
-  if (!reevaluation_time_.is_max())
-    timeout = reevaluation_time_ - evaluation_start_;
+  // Handle reevaluation due to a Is{Wallclock,Monotonic}TimeGreaterThan(). We
+  // choose the smaller of the differences between evaluation start time and
+  // reevaluation time among the wallclock and monotonic scales.
+  TimeDelta timeout = std::min(
+      GetTimeout(evaluation_start_wallclock_, reevaluation_time_wallclock_),
+      GetTimeout(evaluation_start_monotonic_, reevaluation_time_monotonic_));
 
   // Handle reevaluation due to async or poll variables.
+  bool waiting_for_value_change = false;
   for (auto& it : value_cache_) {
     switch (it.first->GetMode()) {
       case kVariableModeAsync:
@@ -180,8 +205,12 @@
 
   base::DictionaryValue value;
   value.Set("variables", variables);  // Adopts |variables|.
-  value.SetString("evaluation_start",
-                  chromeos_update_engine::utils::ToString(evaluation_start_));
+  value.SetString(
+      "evaluation_start_wallclock",
+      chromeos_update_engine::utils::ToString(evaluation_start_wallclock_));
+  value.SetString(
+      "evaluation_start_monotonic",
+      chromeos_update_engine::utils::ToString(evaluation_start_monotonic_));
 
   string json_str;
   base::JSONWriter::WriteWithOptions(&value,
diff --git a/update_manager/evaluation_context.h b/update_manager/evaluation_context.h
index 9ed6f26..909201e 100644
--- a/update_manager/evaluation_context.h
+++ b/update_manager/evaluation_context.h
@@ -28,7 +28,8 @@
 // same policy request (an AsyncPolicyRequest might involve several
 // re-evaluations). Each evaluation of the EvaluationContext is run at a given
 // point in time, which is used as a reference for the evaluation timeout and
-// the time based queries of the policy, such as IsTimeGreaterThan().
+// the time based queries of the policy, such as
+// Is{Wallclock,Monotonic}TimeGreaterThan().
 //
 // Example:
 //
@@ -68,10 +69,11 @@
   template<typename T>
   const T* GetValue(Variable<T>* var);
 
-  // Returns whether the passed |timestamp| is less than the evaluation time.
-  // The |timestamp| value should be in the same scale as the values returned by
-  // ClockInterface::GetWallclockTime().
-  bool IsTimeGreaterThan(base::Time timestamp);
+  // Returns whether the evaluation time has surpassed |timestamp|, on either
+  // the ClockInterface::GetWallclockTime() or
+  // ClockInterface::GetMonotonicTime() scales, respectively.
+  bool IsWallclockTimeGreaterThan(base::Time timestamp);
+  bool IsMonotonicTimeGreaterThan(base::Time timestamp);
 
   // Returns whether the evaluation context has expired.
   bool is_expired() const { return is_expired_; }
@@ -150,17 +152,21 @@
   // Pointer to the mockable clock interface;
   chromeos_update_engine::ClockInterface* const clock_;
 
-  // The timestamp when the evaluation of this EvaluationContext started. This
-  // value is reset every time ResetEvaluation() is called. The time source
-  // used is the ClockInterface::GetWallclockTime().
-  base::Time evaluation_start_;
+  // The timestamps when the evaluation of this EvaluationContext started,
+  // corresponding to ClockInterface::GetWallclockTime() and
+  // ClockInterface::GetMonotonicTime(), respectively. These values are reset
+  // every time ResetEvaluation() is called.
+  base::Time evaluation_start_wallclock_;
+  base::Time evaluation_start_monotonic_;
 
-  // The timestamp measured on the GetWallclockTime() scale, when a reevaluation
-  // should be triggered due to IsTimeGreaterThan() calls value changes. This
-  // timestamp is greater or equal to |evaluation_start_| since it is a
-  // timestamp in the future, but it can be lower than the current
-  // GetWallclockTime() at some point of the evaluation.
-  base::Time reevaluation_time_;
+  // The timestamps when a reevaluation should be triggered due to various
+  // expected value changes, corresponding to ClockInterface::GetWallclockTime()
+  // and ClockInterface::GetMonotonicTIme(), respectively. These timestamps are
+  // greater or equal to corresponding |evaluation_start_{wallclock,monotonic}_|
+  // counterparts since they are in the future; however, they may be smaller
+  // than the current corresponding times during the course of evaluation.
+  base::Time reevaluation_time_wallclock_;
+  base::Time reevaluation_time_monotonic_;
 
   // The timeout of an evaluation.
   const base::TimeDelta evaluation_timeout_;
diff --git a/update_manager/evaluation_context_unittest.cc b/update_manager/evaluation_context_unittest.cc
index eafb219..52755fc 100644
--- a/update_manager/evaluation_context_unittest.cc
+++ b/update_manager/evaluation_context_unittest.cc
@@ -69,9 +69,9 @@
 class UmEvaluationContextTest : public ::testing::Test {
  protected:
   virtual void SetUp() {
-    // Set the clock to a fixed values.
-    fake_clock_.SetMonotonicTime(Time::FromInternalValue(12345678L));
-    // Mar 2, 2006 1:23:45 UTC is 1141262625 since the Unix Epoch.
+    // Apr 22, 2009 19:25:00 UTC (this is a random reference point).
+    fake_clock_.SetMonotonicTime(Time::FromTimeT(1240428300));
+    // Mar 2, 2006 1:23:45 UTC.
     fake_clock_.SetWallclockTime(Time::FromTimeT(1141262625));
     eval_ctx_ = new EvaluationContext(&fake_clock_, default_timeout_,
                                       default_timeout_);
@@ -337,47 +337,94 @@
   UMTEST_EXPECT_NULL(eval_ctx_->GetValue(&mock_var_async_));
 }
 
-TEST_F(UmEvaluationContextTest, ResetEvaluationResetsTimes) {
+TEST_F(UmEvaluationContextTest, ResetEvaluationResetsTimesWallclock) {
   base::Time cur_time = fake_clock_.GetWallclockTime();
   // Advance the time on the clock but don't call ResetEvaluation yet.
   fake_clock_.SetWallclockTime(cur_time + TimeDelta::FromSeconds(4));
 
-  EXPECT_TRUE(eval_ctx_->IsTimeGreaterThan(cur_time -
-                                           TimeDelta::FromSeconds(1)));
-  EXPECT_FALSE(eval_ctx_->IsTimeGreaterThan(cur_time));
-  EXPECT_FALSE(eval_ctx_->IsTimeGreaterThan(cur_time +
-                                            TimeDelta::FromSeconds(1)));
+  EXPECT_TRUE(eval_ctx_->IsWallclockTimeGreaterThan(
+          cur_time - TimeDelta::FromSeconds(1)));
+  EXPECT_FALSE(eval_ctx_->IsWallclockTimeGreaterThan(cur_time));
+  EXPECT_FALSE(eval_ctx_->IsWallclockTimeGreaterThan(
+          cur_time + TimeDelta::FromSeconds(1)));
   // Call ResetEvaluation now, which should use the new evaluation time.
   eval_ctx_->ResetEvaluation();
 
   cur_time = fake_clock_.GetWallclockTime();
-  EXPECT_TRUE(eval_ctx_->IsTimeGreaterThan(cur_time -
-                                           TimeDelta::FromSeconds(1)));
-  EXPECT_FALSE(eval_ctx_->IsTimeGreaterThan(cur_time));
-  EXPECT_FALSE(eval_ctx_->IsTimeGreaterThan(cur_time +
-                                            TimeDelta::FromSeconds(1)));
+  EXPECT_TRUE(eval_ctx_->IsWallclockTimeGreaterThan(
+          cur_time - TimeDelta::FromSeconds(1)));
+  EXPECT_FALSE(eval_ctx_->IsWallclockTimeGreaterThan(cur_time));
+  EXPECT_FALSE(eval_ctx_->IsWallclockTimeGreaterThan(
+          cur_time + TimeDelta::FromSeconds(1)));
 }
 
-TEST_F(UmEvaluationContextTest, IsTimeGreaterThanSignalsTriggerReevaluation) {
-  EXPECT_FALSE(eval_ctx_->IsTimeGreaterThan(
+TEST_F(UmEvaluationContextTest, ResetEvaluationResetsTimesMonotonic) {
+  base::Time cur_time = fake_clock_.GetMonotonicTime();
+  // Advance the time on the clock but don't call ResetEvaluation yet.
+  fake_clock_.SetMonotonicTime(cur_time + TimeDelta::FromSeconds(4));
+
+  EXPECT_TRUE(eval_ctx_->IsMonotonicTimeGreaterThan(
+          cur_time - TimeDelta::FromSeconds(1)));
+  EXPECT_FALSE(eval_ctx_->IsMonotonicTimeGreaterThan(cur_time));
+  EXPECT_FALSE(eval_ctx_->IsMonotonicTimeGreaterThan(
+          cur_time + TimeDelta::FromSeconds(1)));
+  // Call ResetEvaluation now, which should use the new evaluation time.
+  eval_ctx_->ResetEvaluation();
+
+  cur_time = fake_clock_.GetMonotonicTime();
+  EXPECT_TRUE(eval_ctx_->IsMonotonicTimeGreaterThan(
+          cur_time - TimeDelta::FromSeconds(1)));
+  EXPECT_FALSE(eval_ctx_->IsMonotonicTimeGreaterThan(cur_time));
+  EXPECT_FALSE(eval_ctx_->IsMonotonicTimeGreaterThan(
+          cur_time + TimeDelta::FromSeconds(1)));
+}
+
+TEST_F(UmEvaluationContextTest,
+       IsWallclockTimeGreaterThanSignalsTriggerReevaluation) {
+  EXPECT_FALSE(eval_ctx_->IsWallclockTimeGreaterThan(
       fake_clock_.GetWallclockTime() + TimeDelta::FromSeconds(1)));
 
-  // The "false" from IsTimeGreaterThan means that's not that timestamp yet, so
-  // this should schedule a callback for when that happens.
+  // The "false" from IsWallclockTimeGreaterThan means that's not that timestamp
+  // yet, so this should schedule a callback for when that happens.
   EXPECT_TRUE(eval_ctx_->RunOnValueChangeOrTimeout(Bind(&DoNothing)));
 }
 
-TEST_F(UmEvaluationContextTest, IsTimeGreaterThanDoesntRecordPastTimestamps) {
-  // IsTimeGreaterThan() should ignore timestamps on the past for reevaluation.
-  EXPECT_TRUE(eval_ctx_->IsTimeGreaterThan(
+TEST_F(UmEvaluationContextTest,
+       IsMonotonicTimeGreaterThanSignalsTriggerReevaluation) {
+  EXPECT_FALSE(eval_ctx_->IsMonotonicTimeGreaterThan(
+      fake_clock_.GetMonotonicTime() + TimeDelta::FromSeconds(1)));
+
+  // The "false" from IsMonotonicTimeGreaterThan means that's not that timestamp
+  // yet, so this should schedule a callback for when that happens.
+  EXPECT_TRUE(eval_ctx_->RunOnValueChangeOrTimeout(Bind(&DoNothing)));
+}
+
+TEST_F(UmEvaluationContextTest,
+       IsWallclockTimeGreaterThanDoesntRecordPastTimestamps) {
+  // IsWallclockTimeGreaterThan() should ignore timestamps on the past for
+  // reevaluation.
+  EXPECT_TRUE(eval_ctx_->IsWallclockTimeGreaterThan(
       fake_clock_.GetWallclockTime() - TimeDelta::FromSeconds(20)));
-  EXPECT_TRUE(eval_ctx_->IsTimeGreaterThan(
+  EXPECT_TRUE(eval_ctx_->IsWallclockTimeGreaterThan(
       fake_clock_.GetWallclockTime() - TimeDelta::FromSeconds(1)));
 
   // Callback should not be scheduled.
   EXPECT_FALSE(eval_ctx_->RunOnValueChangeOrTimeout(Bind(&DoNothing)));
 }
 
+TEST_F(UmEvaluationContextTest,
+       IsMonotonicTimeGreaterThanDoesntRecordPastTimestamps) {
+  // IsMonotonicTimeGreaterThan() should ignore timestamps on the past for
+  // reevaluation.
+  EXPECT_TRUE(eval_ctx_->IsMonotonicTimeGreaterThan(
+      fake_clock_.GetMonotonicTime() - TimeDelta::FromSeconds(20)));
+  EXPECT_TRUE(eval_ctx_->IsMonotonicTimeGreaterThan(
+      fake_clock_.GetMonotonicTime() - TimeDelta::FromSeconds(1)));
+
+  // Callback should not be scheduled.
+  EXPECT_FALSE(eval_ctx_->RunOnValueChangeOrTimeout(Bind(&DoNothing)));
+}
+
 TEST_F(UmEvaluationContextTest, DumpContext) {
   // |fail_var_| yield "(no value)" since it is unset.
   eval_ctx_->GetValue(&fail_var_);
@@ -391,10 +438,11 @@
   eval_ctx_->GetValue(&fake_poll_var_);
 
   // Note that the variables are printed in alphabetical order. Also
-  // see UmEvaluationContextText::SetUp() where the value used for
-  // |evaluation_start| is set.
+  // see UmEvaluationContextText::SetUp() where the values used for
+  // |evaluation_start_{monotonic,wallclock| are set.
   EXPECT_EQ("{\n"
-            "   \"evaluation_start\": \"3/2/2006 1:23:45 GMT\",\n"
+            "   \"evaluation_start_monotonic\": \"4/22/2009 19:25:00 GMT\",\n"
+            "   \"evaluation_start_wallclock\": \"3/2/2006 1:23:45 GMT\",\n"
             "   \"variables\": {\n"
             "      \"fail_var\": \"(no value)\",\n"
             "      \"fake_int\": \"42\",\n"
diff --git a/update_manager/update_manager_unittest.cc b/update_manager/update_manager_unittest.cc
index 8f81be5..048a0d9 100644
--- a/update_manager/update_manager_unittest.cc
+++ b/update_manager/update_manager_unittest.cc
@@ -122,7 +122,7 @@
     // non-constant dependency. The threshold is far enough in the future to
     // ensure that it does not fire immediately.
     if (time_threshold_ < base::Time::Max())
-      ec->IsTimeGreaterThan(time_threshold_);
+      ec->IsWallclockTimeGreaterThan(time_threshold_);
     return EvalStatus::kAskMeAgainLater;
   }