diff --git a/buffet/buffet.gyp b/buffet/buffet.gyp
index 3758634..f8c0a5a 100644
--- a/buffet/buffet.gyp
+++ b/buffet/buffet.gyp
@@ -179,6 +179,7 @@
             'base_api_handler_unittest.cc',
             'buffet_testrunner.cc',
             'buffet_config_unittest.cc',
+            'commands/cloud_command_proxy_unittest.cc',
             'commands/command_definition_unittest.cc',
             'commands/command_dictionary_unittest.cc',
             'commands/command_instance_unittest.cc',
diff --git a/buffet/commands/cloud_command_proxy.cc b/buffet/commands/cloud_command_proxy.cc
index a87e410..127e63b 100644
--- a/buffet/commands/cloud_command_proxy.cc
+++ b/buffet/commands/cloud_command_proxy.cc
@@ -4,75 +4,120 @@
 
 #include "buffet/commands/cloud_command_proxy.h"
 
-#include <base/message_loop/message_loop.h>
+#include <base/bind.h>
 
 #include "buffet/commands/command_instance.h"
 #include "buffet/commands/prop_constraints.h"
 #include "buffet/commands/prop_types.h"
 #include "buffet/commands/schema_constants.h"
-#include "buffet/device_registration_info.h"
 
 namespace buffet {
 
-namespace {
-// Bits used in CommandUpdateFlags for various command resource parts.
-enum {
-  kFlagResults,
-  kFlagState,
-  kFlagProgress
-};
-
-// Retry timeout for re-sending failed command update request.
-static const int64_t kCommandUpdateRetryTimeoutSeconds = 5;
-
-}  // anonymous namespace
-
 CloudCommandProxy::CloudCommandProxy(
     CommandInstance* command_instance,
-    CloudCommandUpdateInterface* cloud_command_updater)
+    CloudCommandUpdateInterface* cloud_command_updater,
+    StateChangeQueueInterface* state_change_queue,
+    std::unique_ptr<chromeos::BackoffEntry> backoff_entry,
+    const scoped_refptr<base::TaskRunner>& task_runner)
     : command_instance_{command_instance},
-      cloud_command_updater_{cloud_command_updater} {
+      cloud_command_updater_{cloud_command_updater},
+      state_change_queue_{state_change_queue},
+      task_runner_{task_runner},
+      cloud_backoff_entry_{std::move(backoff_entry)} {
+  callback_token_ = state_change_queue_->AddOnStateUpdatedCallback(
+      base::Bind(&CloudCommandProxy::OnDeviceStateUpdated,
+                  weak_ptr_factory_.GetWeakPtr()));
 }
 
 void CloudCommandProxy::OnResultsChanged() {
-  new_pending_command_updates_.set(kFlagResults);
-  SendCommandUpdate();
+  std::unique_ptr<base::DictionaryValue> patch{new base::DictionaryValue};
+  auto json = TypedValueToJson(command_instance_->GetResults(), nullptr);
+  patch->Set(commands::attributes::kCommand_Results, json.release());
+  QueueCommandUpdate(std::move(patch));
 }
 
 void CloudCommandProxy::OnStatusChanged() {
-  new_pending_command_updates_.set(kFlagState);
-  SendCommandUpdate();
+  std::unique_ptr<base::DictionaryValue> patch{new base::DictionaryValue};
+  patch->SetString(commands::attributes::kCommand_State,
+                   command_instance_->GetStatus());
+  QueueCommandUpdate(std::move(patch));
 }
 
 void CloudCommandProxy::OnProgressChanged() {
-  new_pending_command_updates_.set(kFlagProgress);
+  std::unique_ptr<base::DictionaryValue> patch{new base::DictionaryValue};
+  auto json = TypedValueToJson(command_instance_->GetProgress(), nullptr);
+  patch->Set(commands::attributes::kCommand_Progress, json.release());
+  QueueCommandUpdate(std::move(patch));
+}
+
+void CloudCommandProxy::QueueCommandUpdate(
+    std::unique_ptr<base::DictionaryValue> patch) {
+  UpdateID id = state_change_queue_->GetLastStateChangeId();
+  if (update_queue_.empty() || update_queue_.back().first != id) {
+    // If queue is currently empty or the device state has changed since the
+    // last patch request queued, add a new request to the queue.
+    update_queue_.push_back(std::make_pair(id, std::move(patch)));
+  } else {
+    // Device state hasn't changed since the last time this command update
+    // was queued. We can coalesce the command update patches, unless the
+    // current request is already in flight to the server.
+    if (update_queue_.size() == 1 && command_update_in_progress_) {
+      // Can't update the request which is being sent to the server.
+      // Queue a new update.
+      update_queue_.push_back(std::make_pair(id, std::move(patch)));
+    } else {
+      // Coalesce the patches.
+      update_queue_.back().second->MergeDictionary(patch.get());
+    }
+  }
+  // Send out an update request to the server, if needed.
   SendCommandUpdate();
 }
 
 void CloudCommandProxy::SendCommandUpdate() {
-  if (command_update_in_progress_ || new_pending_command_updates_.none())
+  if (command_update_in_progress_ || update_queue_.empty())
     return;
 
-  base::DictionaryValue patch;
-  if (new_pending_command_updates_.test(kFlagResults)) {
-    auto json = TypedValueToJson(command_instance_->GetResults(), nullptr);
-    patch.Set(commands::attributes::kCommand_Results, json.release());
+  // Check if we have any pending updates ready to be sent to the server.
+  // We can only send updates for which the device state at the time the
+  // requests have been queued were successfully propagated to the server.
+  // That is, if the pending device state updates that we recorded while the
+  // command update was queued haven't been acknowledged by the server, we
+  // will hold the corresponding command updates until the related device state
+  // has been successfully updated on the server.
+  if (update_queue_.front().first > last_state_update_id_)
+    return;
+
+  backoff_weak_ptr_factory_.InvalidateWeakPtrs();
+  if (cloud_backoff_entry_->ShouldRejectRequest()) {
+    VLOG(1) << "Cloud request delayed for "
+            << cloud_backoff_entry_->GetTimeUntilRelease()
+            << " due to backoff policy";
+    task_runner_->PostDelayedTask(
+        FROM_HERE,
+        base::Bind(&CloudCommandProxy::SendCommandUpdate,
+                   backoff_weak_ptr_factory_.GetWeakPtr()),
+        cloud_backoff_entry_->GetTimeUntilRelease());
+    return;
   }
 
-  if (new_pending_command_updates_.test(kFlagState)) {
-    patch.SetString(commands::attributes::kCommand_State,
-                    command_instance_->GetStatus());
+  // Coalesce any pending updates that were queued prior to the current device
+  // state known to be propagated to the server successfully.
+  auto iter = update_queue_.begin();
+  auto start = ++iter;
+  while (iter != update_queue_.end()) {
+    if (iter->first > last_state_update_id_)
+      break;
+    update_queue_.front().first = iter->first;
+    update_queue_.front().second->MergeDictionary(iter->second.get());
+    ++iter;
   }
-
-  if (new_pending_command_updates_.test(kFlagProgress)) {
-    auto json = TypedValueToJson(command_instance_->GetProgress(), nullptr);
-    patch.Set(commands::attributes::kCommand_Progress, json.release());
-  }
+  // Remove all the intermediate items that have been merged into the first
+  // entry.
+  update_queue_.erase(start, iter);
   command_update_in_progress_ = true;
-  in_progress_command_updates_ = new_pending_command_updates_;
-  new_pending_command_updates_.reset();
   cloud_command_updater_->UpdateCommand(
-      command_instance_->GetID(), patch,
+      command_instance_->GetID(), *update_queue_.front().second,
       base::Bind(&CloudCommandProxy::OnUpdateCommandFinished,
                  weak_ptr_factory_.GetWeakPtr(), true),
       base::Bind(&CloudCommandProxy::OnUpdateCommandFinished,
@@ -85,27 +130,22 @@
 }
 
 void CloudCommandProxy::OnUpdateCommandFinished(bool success) {
+  command_update_in_progress_ = false;
+  cloud_backoff_entry_->InformOfRequest(success);
   if (success) {
-    command_update_in_progress_ = false;
-    // If previous update was successful, and we have new pending updates,
-    // send a new request to the server immediately.
-    SendCommandUpdate();
-  } else {
-    // If previous request failed, re-send the old data as well.
-    new_pending_command_updates_ |= in_progress_command_updates_;
-    auto message_loop = base::MessageLoop::current();
-    if (message_loop == nullptr) {
-      // Assume we are in unit tests, resend the request immediately...
-      ResendCommandUpdate();
-    } else {
-      // Resend the request to the server after a pre-set delay...
-      message_loop->PostDelayedTask(
-          FROM_HERE,
-          base::Bind(&CloudCommandProxy::ResendCommandUpdate,
-                     weak_ptr_factory_.GetWeakPtr()),
-          base::TimeDelta::FromSeconds(kCommandUpdateRetryTimeoutSeconds));
-    }
+    // Remove the succeeded update from the queue.
+    update_queue_.pop_front();
   }
+  // If we have more pending updates, send a new request to the server
+  // immediately, if possible.
+  SendCommandUpdate();
+}
+
+void CloudCommandProxy::OnDeviceStateUpdated(UpdateID update_id) {
+  last_state_update_id_ = update_id;
+  // Try to send out any queued command updates that could be performed after
+  // a device state is updated.
+  SendCommandUpdate();
 }
 
 }  // namespace buffet
diff --git a/buffet/commands/cloud_command_proxy.h b/buffet/commands/cloud_command_proxy.h
index 2c607ea..55eb552 100644
--- a/buffet/commands/cloud_command_proxy.h
+++ b/buffet/commands/cloud_command_proxy.h
@@ -5,14 +5,20 @@
 #ifndef BUFFET_COMMANDS_CLOUD_COMMAND_PROXY_H_
 #define BUFFET_COMMANDS_CLOUD_COMMAND_PROXY_H_
 
-#include <bitset>
+#include <deque>
+#include <memory>
 #include <string>
+#include <utility>
 
 #include <base/macros.h>
+#include <base/memory/ref_counted.h>
 #include <base/memory/weak_ptr.h>
+#include <base/task_runner.h>
+#include <chromeos/backoff_entry.h>
 
 #include "buffet/commands/cloud_command_update_interface.h"
 #include "buffet/commands/command_proxy_interface.h"
+#include "buffet/states/state_change_queue_interface.h"
 
 namespace buffet {
 
@@ -22,7 +28,10 @@
 class CloudCommandProxy final : public CommandProxyInterface {
  public:
   CloudCommandProxy(CommandInstance* command_instance,
-                    CloudCommandUpdateInterface* cloud_command_updater);
+                    CloudCommandUpdateInterface* cloud_command_updater,
+                    StateChangeQueueInterface* state_change_queue,
+                    std::unique_ptr<chromeos::BackoffEntry> backoff_entry,
+                    const scoped_refptr<base::TaskRunner>& task_runner);
   ~CloudCommandProxy() override = default;
 
   // CommandProxyInterface implementation/overloads.
@@ -31,14 +40,20 @@
   void OnProgressChanged() override;
 
  private:
-  // Flags used to mark the command resource parts that need to be updated on
-  // the server.
-  using CommandUpdateFlags = std::bitset<3>;
+  using UpdateID = StateChangeQueueInterface::UpdateID;
+  using UpdateQueueEntry =
+      std::pair<UpdateID, std::unique_ptr<base::DictionaryValue>>;
 
-  // Sends an asynchronous request to GCD server to update the command resource.
+  // Puts a command update data into the update queue, and optionally sends an
+  // asynchronous request to GCD server to update the command resource, if there
+  // are no pending device status updates.
+  void QueueCommandUpdate(std::unique_ptr<base::DictionaryValue> patch);
+
+  // Sends an asynchronous request to GCD server to update the command resource,
+  // if there are no pending device status updates.
   void SendCommandUpdate();
 
-  // Retry last failed request.
+  // Retry the last failed command update request to the server.
   void ResendCommandUpdate();
 
   // Callback invoked by the asynchronous PATCH request to the server.
@@ -46,16 +61,35 @@
   // and in case of an error, indicated by the |success| parameter.
   void OnUpdateCommandFinished(bool success);
 
+  // Callback invoked by the device state change queue to notify of the
+  // successful device state update. |update_id| is the ID of the state that
+  // has been updated on the server.
+  void OnDeviceStateUpdated(UpdateID update_id);
+
   CommandInstance* command_instance_;
   CloudCommandUpdateInterface* cloud_command_updater_;
+  StateChangeQueueInterface* state_change_queue_;
+  scoped_refptr<base::TaskRunner> task_runner_;
+
+  // Backoff for SendCommandUpdate() method.
+  std::unique_ptr<chromeos::BackoffEntry> cloud_backoff_entry_;
 
   // Set to true while a pending PATCH request is in flight to the server.
   bool command_update_in_progress_{false};
-  // The flags indicating of new command resource updates since the last req.
-  CommandUpdateFlags new_pending_command_updates_;
-  // The flags indicating of command updates currently in flight.
-  CommandUpdateFlags in_progress_command_updates_;
+  // Update queue with all the command update requests ready to be sent to
+  // the server.
+  std::deque<UpdateQueueEntry> update_queue_;
 
+  // Callback token from the state change queue for OnDeviceStateUpdated()
+  // callback for ask the device state change queue to call when the state
+  // is updated on the server.
+  StateChangeQueueInterface::Token callback_token_;
+
+  // Last device state update ID that has been sent out to the server
+  // successfully.
+  UpdateID last_state_update_id_{0};
+
+  base::WeakPtrFactory<CloudCommandProxy> backoff_weak_ptr_factory_{this};
   base::WeakPtrFactory<CloudCommandProxy> weak_ptr_factory_{this};
   DISALLOW_COPY_AND_ASSIGN(CloudCommandProxy);
 };
diff --git a/buffet/commands/cloud_command_proxy_unittest.cc b/buffet/commands/cloud_command_proxy_unittest.cc
new file mode 100644
index 0000000..0f0d19c
--- /dev/null
+++ b/buffet/commands/cloud_command_proxy_unittest.cc
@@ -0,0 +1,409 @@
+// Copyright 2015 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.
+
+#include "buffet/commands/cloud_command_proxy.h"
+
+#include <memory>
+#include <queue>
+
+#include <base/test/simple_test_clock.h>
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+
+#include "buffet/commands/command_dictionary.h"
+#include "buffet/commands/command_instance.h"
+#include "buffet/commands/unittest_utils.h"
+#include "buffet/states/mock_state_change_queue_interface.h"
+
+using testing::SaveArg;
+using testing::Invoke;
+using testing::Return;
+using testing::ReturnPointee;
+using testing::_;
+
+namespace buffet {
+
+using unittests::CreateDictionaryValue;
+using unittests::CreateValue;
+
+namespace {
+
+const char kCmdID[] = "abcd";
+
+MATCHER_P(MatchJson, str, "") {
+  return arg.Equals(CreateValue(str).get());
+}
+
+class MockCloudCommandUpdateInterface : public CloudCommandUpdateInterface {
+ public:
+  MOCK_METHOD4(UpdateCommand, void(const std::string&,
+                                   const base::DictionaryValue&,
+                                   const base::Closure&,
+                                   const base::Closure&));
+};
+
+// Mock-like task runner that allow the tests to inspect the calls to
+// TaskRunner::PostDelayedTask and verify the delays.
+class TestTaskRunner : public base::TaskRunner {
+ public:
+  MOCK_METHOD3(PostDelayedTask, bool(const tracked_objects::Location&,
+                                     const base::Closure&,
+                                     base::TimeDelta));
+
+  bool RunsTasksOnCurrentThread() const override { return true; }
+};
+
+// Test back-off entry that uses the test clock.
+class TestBackoffEntry : public chromeos::BackoffEntry {
+ public:
+  TestBackoffEntry(const Policy* const policy, base::Clock* clock)
+      : chromeos::BackoffEntry{policy}, clock_{clock} {
+    creation_time_ = clock->Now();
+  }
+
+ private:
+  // Override from chromeos::BackoffEntry to use the custom test clock for
+  // the backoff calculations.
+  base::TimeTicks ImplGetTimeNow() const override {
+    return base::TimeTicks::FromInternalValue(clock_->Now().ToInternalValue());
+  }
+
+  base::Clock* clock_;
+  base::Time creation_time_;
+};
+
+class CloudCommandProxyTest : public ::testing::Test {
+ protected:
+  void SetUp() override {
+    // Set up the test StateChangeQueue.
+    auto callback = [this](
+        const base::Callback<void(StateChangeQueueInterface::UpdateID)>& call) {
+      return callbacks_.Add(call).release();
+    };
+    EXPECT_CALL(state_change_queue_, MockAddOnStateUpdatedCallback(_))
+        .WillRepeatedly(Invoke(callback));
+    EXPECT_CALL(state_change_queue_, GetLastStateChangeId())
+        .WillRepeatedly(testing::ReturnPointee(&current_state_update_id_));
+
+    // Set up the task runner.
+    task_runner_ = new TestTaskRunner();
+
+    auto on_post_task = [this](const tracked_objects::Location& from_here,
+                               const base::Closure& task,
+                               base::TimeDelta delay) -> bool {
+      clock_.Advance(delay);
+      task_queue_.push(task);
+      return true;
+    };
+
+    ON_CALL(*task_runner_, PostDelayedTask(_, _, _))
+        .WillByDefault(testing::Invoke(on_post_task));
+
+    clock_.SetNow(base::Time::Now());
+
+    // Set up the command schema.
+    auto json = CreateDictionaryValue(R"({
+      'calc': {
+        'add': {
+          'parameters': {
+            'value1': 'integer',
+            'value2': 'integer'
+          },
+          'progress': {
+            'status' : 'string'
+          },
+          'results': {
+            'sum' : 'integer'
+          }
+        }
+      }
+    })");
+    CHECK(json.get());
+    CHECK(command_dictionary_.LoadCommands(*json, "calcd", nullptr, nullptr))
+        << "Failed to parse test command dictionary";
+
+    CreateCommandInstance();
+  }
+
+  void CreateCommandInstance() {
+    auto command_json = CreateDictionaryValue(R"({
+      'name': 'calc.add',
+      'id': 'abcd',
+      'parameters': {
+        'value1': 10,
+        'value2': 20
+      }
+    })");
+    CHECK(command_json.get());
+
+    command_instance_ = CommandInstance::FromJson(
+        command_json.get(), "cloud", command_dictionary_, nullptr, nullptr);
+    CHECK(command_instance_.get());
+
+    // Backoff - start at 1s and double with each backoff attempt and no jitter.
+    static const chromeos::BackoffEntry::Policy policy{
+        0, 1000, 2.0, 0.0, 20000, -1, false};
+    std::unique_ptr<TestBackoffEntry> backoff{
+        new TestBackoffEntry{&policy, &clock_}};
+
+    // Finally construct the CloudCommandProxy we are going to test here.
+    std::unique_ptr<CloudCommandProxy> proxy{new CloudCommandProxy{
+        command_instance_.get(), &cloud_updater_, &state_change_queue_,
+        std::move(backoff), task_runner_}};
+    command_instance_->AddProxy(std::move(proxy));
+  }
+
+  StateChangeQueueInterface::UpdateID current_state_update_id_{0};
+  base::CallbackList<void(StateChangeQueueInterface::UpdateID)> callbacks_;
+  testing::StrictMock<MockCloudCommandUpdateInterface> cloud_updater_;
+  testing::StrictMock<MockStateChangeQueueInterface> state_change_queue_;
+  base::SimpleTestClock clock_;
+  scoped_refptr<TestTaskRunner> task_runner_;
+  std::queue<base::Closure> task_queue_;
+  CommandDictionary command_dictionary_;
+  std::unique_ptr<CommandInstance> command_instance_;
+};
+
+}  // anonymous namespace
+
+TEST_F(CloudCommandProxyTest, ImmediateUpdate) {
+  const char expected[] = "{'state':'done'}";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expected), _, _));
+  command_instance_->Done();
+}
+
+TEST_F(CloudCommandProxyTest, DelayedUpdate) {
+  // Simulate that the current device state has changed.
+  current_state_update_id_ = 20;
+  // No command update is expected here.
+  command_instance_->Done();
+  // Still no command update here...
+  callbacks_.Notify(19);
+  // Now we should get the update...
+  const char expected[] = "{'state':'done'}";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expected), _, _));
+  callbacks_.Notify(20);
+}
+
+TEST_F(CloudCommandProxyTest, InFlightRequest) {
+  // SetProgress causes two consecutive updates:
+  //    state=inProgress
+  //    progress={...}
+  // The first state update is sent immediately, the second should be delayed.
+  base::Closure on_success;
+  EXPECT_CALL(cloud_updater_,
+              UpdateCommand(kCmdID, MatchJson("{'state':'inProgress'}"), _, _))
+      .WillOnce(SaveArg<2>(&on_success));
+  command_instance_->SetProgress(
+      {{"status", unittests::make_string_prop_value("ready")}});
+
+  // Now simulate the first request completing.
+  // The second request should be sent now.
+  const char expected[] = "{'progress':{'status':'ready'}}";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expected), _, _));
+  on_success.Run();
+}
+
+TEST_F(CloudCommandProxyTest, CombineMultiple) {
+  // Simulate that the current device state has changed.
+  current_state_update_id_ = 20;
+  // SetProgress causes two consecutive updates:
+  //    state=inProgress
+  //    progress={...}
+  // Both updates will be held until device state is updated.
+  command_instance_->SetProgress(
+      {{"status", unittests::make_string_prop_value("ready")}});
+
+  // Now simulate the device state updated. Both updates should come in one
+  // request.
+  const char expected[] = R"({
+    'progress': {'status':'ready'},
+    'state':'inProgress'
+  })";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expected), _, _));
+  callbacks_.Notify(20);
+}
+
+TEST_F(CloudCommandProxyTest, RetryFailed) {
+  base::Closure on_error;
+  const char expect1[] = "{'state':'inProgress'}";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expect1), _, _))
+      .WillOnce(SaveArg<3>(&on_error));
+  command_instance_->SetProgress(
+      {{"status", unittests::make_string_prop_value("ready")}});
+
+  // Now pretend the first command update request has failed.
+  // We should retry with both state and progress fields updated this time,
+  // after the initial backoff (which should be 1s in our case).
+  base::TimeDelta expected_delay = base::TimeDelta::FromSeconds(1);
+  EXPECT_CALL(*task_runner_, PostDelayedTask(_, _, expected_delay));
+  on_error.Run();
+
+  // Execute the delayed request. But pretend that it failed too.
+  const char expect2[] = R"({
+    'progress': {'status':'ready'},
+    'state':'inProgress'
+  })";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expect2), _, _))
+      .WillOnce(SaveArg<3>(&on_error));
+  task_queue_.back().Run();
+  task_queue_.pop();
+
+  // Now backoff should be 2 seconds.
+  expected_delay = base::TimeDelta::FromSeconds(2);
+  EXPECT_CALL(*task_runner_, PostDelayedTask(_, _, expected_delay));
+  on_error.Run();
+
+  // Retry the task.
+  base::Closure on_success;
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expect2), _, _))
+      .WillOnce(SaveArg<2>(&on_success));
+  task_queue_.back().Run();
+  task_queue_.pop();
+
+  // Pretend it succeeds this time.
+  on_success.Run();
+}
+
+TEST_F(CloudCommandProxyTest, GateOnStateUpdates) {
+  current_state_update_id_ = 20;
+  command_instance_->SetProgress(
+      {{"status", unittests::make_string_prop_value("ready")}});
+  current_state_update_id_ = 21;
+  command_instance_->SetProgress(
+      {{"status", unittests::make_string_prop_value("busy")}});
+  current_state_update_id_ = 22;
+  command_instance_->Done();
+
+  // Device state #20 updated.
+  base::Closure on_success;
+  const char expect1[] = R"({
+    'progress': {'status':'ready'},
+    'state':'inProgress'
+  })";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expect1), _, _))
+      .WillOnce(SaveArg<2>(&on_success));
+  callbacks_.Notify(20);
+  on_success.Run();
+
+  // Device state #21 updated.
+  const char expect2[] = "{'progress': {'status':'busy'}}";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expect2), _, _))
+      .WillOnce(SaveArg<2>(&on_success));
+  callbacks_.Notify(21);
+
+  // Device state #22 updated. Nothing happens here since the previous command
+  // update request hasn't completed yet.
+  callbacks_.Notify(22);
+
+  // Now the command update is complete, send out the patch that happened after
+  // the state #22 was updated.
+  const char expect3[] = "{'state': 'done'}";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expect3), _, _))
+      .WillOnce(SaveArg<2>(&on_success));
+  on_success.Run();
+}
+
+TEST_F(CloudCommandProxyTest, CombineSomeStates) {
+  current_state_update_id_ = 20;
+  command_instance_->SetProgress(
+      {{"status", unittests::make_string_prop_value("ready")}});
+  current_state_update_id_ = 21;
+  command_instance_->SetProgress(
+      {{"status", unittests::make_string_prop_value("busy")}});
+  current_state_update_id_ = 22;
+  command_instance_->Done();
+
+  // Device state 20-21 updated.
+  base::Closure on_success;
+  const char expect1[] = R"({
+    'progress': {'status':'busy'},
+    'state':'inProgress'
+  })";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expect1), _, _))
+      .WillOnce(SaveArg<2>(&on_success));
+  callbacks_.Notify(21);
+  on_success.Run();
+
+  // Device state #22 updated.
+  const char expect2[] = "{'state': 'done'}";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expect2), _, _))
+      .WillOnce(SaveArg<2>(&on_success));
+  callbacks_.Notify(22);
+  on_success.Run();
+}
+
+TEST_F(CloudCommandProxyTest, CombineAllStates) {
+  current_state_update_id_ = 20;
+  command_instance_->SetProgress(
+      {{"status", unittests::make_string_prop_value("ready")}});
+  current_state_update_id_ = 21;
+  command_instance_->SetProgress(
+      {{"status", unittests::make_string_prop_value("busy")}});
+  current_state_update_id_ = 22;
+  command_instance_->Done();
+
+  // Device state 30 updated.
+  const char expected[] = R"({
+    'progress': {'status':'busy'},
+    'state':'done'
+  })";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expected), _, _));
+  callbacks_.Notify(30);
+}
+
+TEST_F(CloudCommandProxyTest, CoalesceUpdates) {
+  current_state_update_id_ = 20;
+  command_instance_->SetProgress(
+      {{"status", unittests::make_string_prop_value("ready")}});
+  command_instance_->SetProgress(
+      {{"status", unittests::make_string_prop_value("busy")}});
+  command_instance_->SetProgress(
+      {{"status", unittests::make_string_prop_value("finished")}});
+  command_instance_->SetResults({{"sum", unittests::make_int_prop_value(30)}});
+  command_instance_->Done();
+
+  const char expected[] = R"({
+    'progress': {'status':'finished'},
+    'results': {'sum':30},
+    'state':'done'
+  })";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expected), _, _));
+  callbacks_.Notify(30);
+}
+
+TEST_F(CloudCommandProxyTest, EmptyStateChangeQueue) {
+  // Assume the device state update queue was empty and was at update ID 20.
+  current_state_update_id_ = 20;
+
+  // Recreate the command instance and proxy with the new state change queue.
+  CreateCommandInstance();
+
+  // Empty queue will immediately call back with the state change notification.
+  callbacks_.Notify(20);
+
+  // As soon as we change the command, the update to the server should be sent.
+  const char expected[] = "{'state':'done'}";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expected), _, _));
+  command_instance_->Done();
+}
+
+TEST_F(CloudCommandProxyTest, NonEmptyStateChangeQueue) {
+  // Assume the device state update queue was NOT empty when the command
+  // instance was created.
+  current_state_update_id_ = 20;
+
+  // Recreate the command instance and proxy with the new state change queue.
+  CreateCommandInstance();
+
+  // No command updates right now.
+  command_instance_->Done();
+
+  // Only when the state #20 is published we should update the command
+  const char expected[] = "{'state':'done'}";
+  EXPECT_CALL(cloud_updater_, UpdateCommand(kCmdID, MatchJson(expected), _, _));
+  callbacks_.Notify(20);
+}
+
+}  // namespace buffet
diff --git a/buffet/device_registration_info.cc b/buffet/device_registration_info.cc
index 74e4433..2de7e52 100644
--- a/buffet/device_registration_info.cc
+++ b/buffet/device_registration_info.cc
@@ -899,8 +899,12 @@
   if (!command_manager_->FindCommand(command_instance->GetID())) {
     LOG(INFO) << "New command '" << command_instance->GetName()
               << "' arrived, ID: " << command_instance->GetID();
+    std::unique_ptr<chromeos::BackoffEntry> backoff_entry{
+        new chromeos::BackoffEntry{cloud_backoff_policy_.get()}};
     std::unique_ptr<CommandProxyInterface> cloud_proxy{
-        new CloudCommandProxy{command_instance.get(), this}};
+        new CloudCommandProxy{command_instance.get(), this,
+                              state_manager_->GetStateChangeQueue(),
+                              std::move(backoff_entry), task_runner_}};
     command_instance->AddProxy(std::move(cloud_proxy));
     command_manager_->AddCommand(std::move(command_instance));
   }
@@ -911,8 +915,10 @@
   if (device_state_update_pending_)
     return;
 
-  const std::vector<StateChange> state_changes{
-      state_manager_->GetAndClearRecordedStateChanges()};
+  StateChangeQueueInterface::UpdateID update_id = 0;
+  std::vector<StateChange> state_changes;
+  std::tie(update_id, state_changes) =
+    state_manager_->GetAndClearRecordedStateChanges();
   if (state_changes.empty())
     return;
 
@@ -947,13 +953,16 @@
   device_state_update_pending_ = true;
   DoCloudRequest(
       chromeos::http::request_type::kPost, GetDeviceURL("patchState"), &body,
-      base::Bind(&DeviceRegistrationInfo::OnPublishStateSuccess, AsWeakPtr()),
+      base::Bind(&DeviceRegistrationInfo::OnPublishStateSuccess, AsWeakPtr(),
+                 update_id),
       base::Bind(&DeviceRegistrationInfo::OnPublishStateError, AsWeakPtr()));
 }
 
 void DeviceRegistrationInfo::OnPublishStateSuccess(
+    StateChangeQueueInterface::UpdateID update_id,
     const base::DictionaryValue& reply) {
   device_state_update_pending_ = false;
+  state_manager_->NotifyStateUpdatedOnServer(update_id);
   // See if there were more pending state updates since the previous request
   // had been sent out.
   PublishStateUpdates();
diff --git a/buffet/device_registration_info.h b/buffet/device_registration_info.h
index 4f12724..b41b55a 100644
--- a/buffet/device_registration_info.h
+++ b/buffet/device_registration_info.h
@@ -30,6 +30,7 @@
 #include "buffet/notification/notification_delegate.h"
 #include "buffet/notification/pull_channel.h"
 #include "buffet/registration_status.h"
+#include "buffet/states/state_change_queue_interface.h"
 #include "buffet/storage_interface.h"
 
 namespace base {
@@ -254,7 +255,8 @@
   void PublishCommand(const base::DictionaryValue& command);
 
   void PublishStateUpdates();
-  void OnPublishStateSuccess(const base::DictionaryValue& reply);
+  void OnPublishStateSuccess(StateChangeQueueInterface::UpdateID update_id,
+                             const base::DictionaryValue& reply);
   void OnPublishStateError(const chromeos::Error* error);
 
   // If unrecoverable error occurred (e.g. error parsing command instance),
diff --git a/buffet/states/mock_state_change_queue_interface.h b/buffet/states/mock_state_change_queue_interface.h
index c984dbb..127e01d 100644
--- a/buffet/states/mock_state_change_queue_interface.h
+++ b/buffet/states/mock_state_change_queue_interface.h
@@ -20,8 +20,17 @@
                bool(base::Time timestamp,
                     native_types::Object changed_properties));
   MOCK_METHOD0(GetAndClearRecordedStateChanges, std::vector<StateChange>());
-  MOCK_CONST_METHOD0(GetLastStateChangeId,
-                     StateChangeQueueInterface::UpdateID());
+  MOCK_CONST_METHOD0(GetLastStateChangeId, UpdateID());
+  MOCK_METHOD1(MockAddOnStateUpdatedCallback,
+               base::CallbackList<void(UpdateID)>::Subscription*(
+                  const base::Callback<void(UpdateID)>&));
+  MOCK_METHOD1(NotifyStateUpdatedOnServer, void(UpdateID));
+
+ private:
+  Token AddOnStateUpdatedCallback(
+      const base::Callback<void(UpdateID)>& callback) override {
+    return Token{MockAddOnStateUpdatedCallback(callback)};
+  }
 };
 
 }  // namespace buffet
diff --git a/buffet/states/state_change_queue.cc b/buffet/states/state_change_queue.cc
index a6e1a72..00ec41a 100644
--- a/buffet/states/state_change_queue.cc
+++ b/buffet/states/state_change_queue.cc
@@ -57,4 +57,15 @@
   return changes;
 }
 
+StateChangeQueueInterface::Token StateChangeQueue::AddOnStateUpdatedCallback(
+    const base::Callback<void(UpdateID)>& callback) {
+  if (state_changes_.empty())
+    callback.Run(last_change_id_);
+  return Token{callbacks_.Add(callback).release()};
+}
+
+void StateChangeQueue::NotifyStateUpdatedOnServer(UpdateID update_id) {
+  callbacks_.Notify(update_id);
+}
+
 }  // namespace buffet
diff --git a/buffet/states/state_change_queue.h b/buffet/states/state_change_queue.h
index 83161fe..26ea9cd 100644
--- a/buffet/states/state_change_queue.h
+++ b/buffet/states/state_change_queue.h
@@ -27,6 +27,9 @@
       native_types::Object changed_properties) override;
   std::vector<StateChange> GetAndClearRecordedStateChanges() override;
   UpdateID GetLastStateChangeId() const override { return last_change_id_; }
+  Token AddOnStateUpdatedCallback(
+      const base::Callback<void(UpdateID)>& callback) override;
+  void NotifyStateUpdatedOnServer(UpdateID update_id) override;
 
  private:
   // To make sure we do not call NotifyPropertiesUpdated() and
@@ -45,6 +48,9 @@
   // invocation increments this value by 1.
   UpdateID last_change_id_{0};
 
+  // Callback list for state change queue even sinks.
+  base::CallbackList<void(UpdateID)> callbacks_;
+
   DISALLOW_COPY_AND_ASSIGN(StateChangeQueue);
 };
 
diff --git a/buffet/states/state_change_queue_interface.h b/buffet/states/state_change_queue_interface.h
index 7c67829..2f11e6b 100644
--- a/buffet/states/state_change_queue_interface.h
+++ b/buffet/states/state_change_queue_interface.h
@@ -7,6 +7,7 @@
 
 #include <vector>
 
+#include <base/callback_list.h>
 #include <base/time/time.h>
 #include <chromeos/variant_dictionary.h>
 
@@ -30,6 +31,8 @@
 class StateChangeQueueInterface {
  public:
   using UpdateID = uint64_t;
+  using Token =
+      std::unique_ptr<base::CallbackList<void(UpdateID)>::Subscription>;
 
   // Returns true if the state change notification queue is empty.
   virtual bool IsEmpty() const = 0;
@@ -46,6 +49,16 @@
   // invocation increments this value by 1.
   virtual UpdateID GetLastStateChangeId() const = 0;
 
+  // Subscribes for device state update notifications from cloud server.
+  // The |callback| will be called every time a state patch with given ID is
+  // successfully received and processed by GCD server.
+  // Returns a subscription token. As soon as this token is destroyed, the
+  // respective callback is removed from the callback list.
+  virtual Token AddOnStateUpdatedCallback(
+      const base::Callback<void(UpdateID)>& callback) WARN_UNUSED_RESULT = 0;
+
+  virtual void NotifyStateUpdatedOnServer(UpdateID update_id) = 0;
+
  protected:
   // No one should attempt do destroy the queue through the interface.
   virtual ~StateChangeQueueInterface() {}
diff --git a/buffet/states/state_change_queue_unittest.cc b/buffet/states/state_change_queue_unittest.cc
index 1a30f97..091e5c3 100644
--- a/buffet/states/state_change_queue_unittest.cc
+++ b/buffet/states/state_change_queue_unittest.cc
@@ -5,6 +5,7 @@
 
 #include "buffet/states/state_change_queue.h"
 
+#include <chromeos/bind_lambda.h>
 #include <gtest/gtest.h>
 
 #include "buffet/commands/unittest_utils.h"
@@ -161,4 +162,29 @@
   EXPECT_EQ(expected2, changes[1].changed_properties);
 }
 
+TEST_F(StateChangeQueueTest, ImmediateStateChangeNotification) {
+  // When queue is empty, registering a new callback will trigger it.
+  bool called = false;
+  auto callback = [&called](StateChangeQueueInterface::UpdateID id) {
+    called = true;
+  };
+  queue_->AddOnStateUpdatedCallback(base::Bind(callback));
+  EXPECT_TRUE(called);
+}
+
+TEST_F(StateChangeQueueTest, DelayedStateChangeNotification) {
+  // When queue is not empty, registering a new callback will not trigger it.
+  ASSERT_TRUE(queue_->NotifyPropertiesUpdated(
+      base::Time::Now(),
+      native_types::Object{
+        {"prop.name1", unittests::make_int_prop_value(1)},
+        {"prop.name2", unittests::make_int_prop_value(2)},
+      }));
+
+  auto callback = [](StateChangeQueueInterface::UpdateID id) {
+    FAIL() << "This should not be called";
+  };
+  queue_->AddOnStateUpdatedCallback(base::Bind(callback));
+}
+
 }  // namespace buffet
diff --git a/buffet/states/state_manager.cc b/buffet/states/state_manager.cc
index 57330f4..2ce78c1 100644
--- a/buffet/states/state_manager.cc
+++ b/buffet/states/state_manager.cc
@@ -166,8 +166,15 @@
   return true;
 }
 
-std::vector<StateChange> StateManager::GetAndClearRecordedStateChanges() {
-  return state_change_queue_->GetAndClearRecordedStateChanges();
+std::pair<StateChangeQueueInterface::UpdateID, std::vector<StateChange>>
+StateManager::GetAndClearRecordedStateChanges() {
+  return std::make_pair(state_change_queue_->GetLastStateChangeId(),
+                        state_change_queue_->GetAndClearRecordedStateChanges());
+}
+
+void StateManager::NotifyStateUpdatedOnServer(
+    StateChangeQueueInterface::UpdateID id) {
+  state_change_queue_->NotifyStateUpdatedOnServer(id);
 }
 
 bool StateManager::LoadStateDefinition(const base::DictionaryValue& json,
diff --git a/buffet/states/state_manager.h b/buffet/states/state_manager.h
index a34f7c1..914daeb 100644
--- a/buffet/states/state_manager.h
+++ b/buffet/states/state_manager.h
@@ -9,6 +9,7 @@
 #include <memory>
 #include <set>
 #include <string>
+#include <utility>
 #include <vector>
 
 #include <base/callback.h>
@@ -58,7 +59,16 @@
 
   // Returns the recorded state changes since last time this method has been
   // called.
-  std::vector<StateChange> GetAndClearRecordedStateChanges();
+  std::pair<StateChangeQueueInterface::UpdateID, std::vector<StateChange>>
+  GetAndClearRecordedStateChanges();
+
+  // Called to notify that the state patch with |id| has been successfully sent
+  // to the server and processed.
+  void NotifyStateUpdatedOnServer(StateChangeQueueInterface::UpdateID id);
+
+  StateChangeQueueInterface* GetStateChangeQueue() const {
+    return state_change_queue_;
+  }
 
  private:
   friend class BaseApiHandlerTest;
diff --git a/buffet/states/state_manager_unittest.cc b/buffet/states/state_manager_unittest.cc
index 50e6a5f..4437a18 100644
--- a/buffet/states/state_manager_unittest.cc
+++ b/buffet/states/state_manager_unittest.cc
@@ -198,10 +198,10 @@
   EXPECT_CALL(mock_state_change_queue_, GetAndClearRecordedStateChanges())
       .WillOnce(Return(expected_val));
   auto changes = mgr_->GetAndClearRecordedStateChanges();
-  ASSERT_EQ(1, changes.size());
-  EXPECT_EQ(expected_val.back().timestamp, changes.back().timestamp);
+  ASSERT_EQ(1, changes.second.size());
+  EXPECT_EQ(expected_val.back().timestamp, changes.second.back().timestamp);
   EXPECT_EQ(expected_val.back().changed_properties,
-            changes.back().changed_properties);
+            changes.second.back().changed_properties);
 }
 
 TEST_F(StateManagerTest, SetProperties) {