diff --git a/libweave/examples/ubuntu/main.cc b/libweave/examples/ubuntu/main.cc
index a116178..28611f5 100644
--- a/libweave/examples/ubuntu/main.cc
+++ b/libweave/examples/ubuntu/main.cc
@@ -33,12 +33,26 @@
 
 class CommandHandler {
  public:
-  explicit CommandHandler(weave::Device* device) : device_{device} {
+  CommandHandler(weave::Device* device,
+                 weave::provider::TaskRunner* task_runner)
+      : device_{device}, task_runner_(task_runner) {
+    device->AddStateDefinitionsFromJson(R"({
+      "_greeter": {"_greetings_counter":"integer"},
+      "_ledflasher": {"_leds": {"items": "boolean"}}
+    })");
+
+    device->SetStatePropertiesFromJson(R"({
+      "_greeter": {"_greetings_counter": 0},
+      "_ledflasher":{"_leds": [false, false, false]}
+    })",
+                                       nullptr);
+
     device->AddCommandDefinitionsFromJson(R"({
       "_greeter": {
         "_greet": {
           "minimalRole": "user",
-          "parameters": { "_name": "string"},
+          "parameters": { "_name": "string", "_count": "integer"},
+          "progress": { "_todo": "integer"},
           "results": { "_greeting": "string" }
         }
       },
@@ -56,58 +70,76 @@
         }
       }
     })");
-
-    device->AddStateDefinitionsFromJson(R"({
-      "_greeter": {"_greetings_counter":"integer"},
-      "_ledflasher": {"_leds": {"items": "boolean"}}
-    })");
-
-    device->SetStatePropertiesFromJson(R"({
-      "_greeter": {"_greetings_counter": 0},
-      "_ledflasher":{"_leds": [false, false, false]}
-    })",
-                                       nullptr);
-
+    device->AddCommandHandler(
+        "_ledflasher._toggle",
+        base::Bind(&CommandHandler::OnFlasherToggleCommand,
+                   weak_ptr_factory_.GetWeakPtr()));
     device->AddCommandHandler("_greeter._greet",
                               base::Bind(&CommandHandler::OnGreetCommand,
                                          weak_ptr_factory_.GetWeakPtr()));
     device->AddCommandHandler("_ledflasher._set",
                               base::Bind(&CommandHandler::OnFlasherSetCommand,
                                          weak_ptr_factory_.GetWeakPtr()));
-    device->AddCommandHandler(
-        "_ledflasher._toggle",
-        base::Bind(&CommandHandler::OnFlasherToggleCommand,
-                   weak_ptr_factory_.GetWeakPtr()));
     device->AddCommandHandler("",
                               base::Bind(&CommandHandler::OnUnhandledCommand,
                                          weak_ptr_factory_.GetWeakPtr()));
   }
 
  private:
-  void OnGreetCommand(weave::Command* cmd) {
-    LOG(INFO) << "received command: " << cmd->GetName();
+  void DoGreet(const std::weak_ptr<weave::Command>& command, int todo) {
+    auto cmd = command.lock();
+    if (!cmd)
+      return;
+
     std::string name;
     if (!cmd->GetParameters()->GetString("_name", &name))
       name = "anonymous";
 
-    LOG(INFO) << cmd->GetName() << " command in progress";
-    cmd->SetProgress(base::DictionaryValue{}, nullptr);
+    if (todo > 0) {
+      LOG(INFO) << "Hello " << name;
+
+      base::DictionaryValue progress;
+      progress.SetInteger("_todo", todo);
+      cmd->SetProgress(progress, nullptr);
+
+      base::DictionaryValue state;
+      state.SetInteger("_greeter._greetings_counter", ++counter_);
+      device_->SetStateProperties(state, nullptr);
+    }
+
+    if (--todo > 0) {
+      task_runner_->PostDelayedTask(
+          FROM_HERE, base::Bind(&CommandHandler::DoGreet,
+                                weak_ptr_factory_.GetWeakPtr(), command, todo),
+          base::TimeDelta::FromSeconds(1));
+      return;
+    }
 
     base::DictionaryValue result;
     result.SetString("_greeting", "Hello " + name);
     cmd->SetResults(result, nullptr);
     LOG(INFO) << cmd->GetName() << " command finished: " << result;
 
-    base::DictionaryValue state;
-    state.SetInteger("_greeter._greetings_counter", ++counter_);
-    device_->SetStateProperties(state, nullptr);
-
     LOG(INFO) << "New state: " << *device_->GetState();
 
     cmd->Done();
   }
 
-  void OnFlasherSetCommand(weave::Command* cmd) {
+  void OnGreetCommand(const std::weak_ptr<weave::Command>& command) {
+    auto cmd = command.lock();
+    if (!cmd)
+      return;
+    LOG(INFO) << "received command: " << cmd->GetName();
+
+    int todo = 1;
+    cmd->GetParameters()->GetInteger("_count", &todo);
+    DoGreet(command, todo);
+  }
+
+  void OnFlasherSetCommand(const std::weak_ptr<weave::Command>& command) {
+    auto cmd = command.lock();
+    if (!cmd)
+      return;
     LOG(INFO) << "received command: " << cmd->GetName();
     int32_t led_index;
     bool cmd_value;
@@ -130,7 +162,10 @@
     cmd->Abort();
   }
 
-  void OnFlasherToggleCommand(weave::Command* cmd) {
+  void OnFlasherToggleCommand(const std::weak_ptr<weave::Command>& command) {
+    auto cmd = command.lock();
+    if (!cmd)
+      return;
     LOG(INFO) << "received command: " << cmd->GetName();
     int32_t led_index;
     if (cmd->GetParameters()->GetInteger("_led", &led_index)) {
@@ -144,7 +179,10 @@
     cmd->Abort();
   }
 
-  void OnUnhandledCommand(weave::Command* cmd) {
+  void OnUnhandledCommand(const std::weak_ptr<weave::Command>& command) {
+    auto cmd = command.lock();
+    if (!cmd)
+      return;
     LOG(INFO) << cmd->GetName() << " unimplemented command: ignored";
   }
 
@@ -157,6 +195,8 @@
   }
 
   weave::Device* device_{nullptr};
+  weave::provider::TaskRunner* task_runner_{nullptr};
+
   int counter_{0};
 
   // Simulate LED status on this device so client app could explore
@@ -218,7 +258,7 @@
     }
   }
 
-  CommandHandler handler(device.get());
+  CommandHandler handler(device.get(), &task_runner);
   task_runner.Run();
 
   LOG(INFO) << "exit";
diff --git a/libweave/include/weave/command.h b/libweave/include/weave/command.h
index 911da1e..6c399e1 100644
--- a/libweave/include/weave/command.h
+++ b/libweave/include/weave/command.h
@@ -27,25 +27,6 @@
 
 class Command {
  public:
-  // This interface lets the command to notify clients about changes.
-  class Observer {
-   public:
-    virtual void OnResultsChanged() = 0;
-    virtual void OnStatusChanged() = 0;
-    virtual void OnProgressChanged() = 0;
-    virtual void OnCommandDestroyed() = 0;
-
-   protected:
-    virtual ~Observer() = default;
-  };
-
-  // Adds an observer for this command. The observer object is not owned by this
-  // class.
-  virtual void AddObserver(Observer* observer) = 0;
-
-  // Removes an observer for this command.
-  virtual void RemoveObserver(Observer* observer) = 0;
-
   // Returns the full command ID.
   virtual const std::string& GetID() const = 0;
 
diff --git a/libweave/include/weave/device.h b/libweave/include/weave/device.h
index 289cedb..7e49202 100644
--- a/libweave/include/weave/device.h
+++ b/libweave/include/weave/device.h
@@ -52,7 +52,8 @@
   virtual void AddCommandDefinitions(const base::DictionaryValue& dict) = 0;
 
   // Callback type for AddCommandHandler.
-  using CommandHandlerCallback = base::Callback<void(Command*)>;
+  using CommandHandlerCallback =
+      base::Callback<void(const std::weak_ptr<Command>& command)>;
 
   // Sets handler for new commands added to the queue.
   // |command_name| is the full command name of the command to handle. e.g.
diff --git a/libweave/include/weave/test/mock_command.h b/libweave/include/weave/test/mock_command.h
index be1b0c3..b856140 100644
--- a/libweave/include/weave/test/mock_command.h
+++ b/libweave/include/weave/test/mock_command.h
@@ -20,8 +20,6 @@
  public:
   ~MockCommand() override = default;
 
-  MOCK_METHOD1(AddObserver, void(Observer*));
-  MOCK_METHOD1(RemoveObserver, void(Observer*));
   MOCK_CONST_METHOD0(GetID, const std::string&());
   MOCK_CONST_METHOD0(GetName, const std::string&());
   MOCK_CONST_METHOD0(GetCategory, const std::string&());
diff --git a/libweave/src/base_api_handler.cc b/libweave/src/base_api_handler.cc
index 1a0a58d..dad443f 100644
--- a/libweave/src/base_api_handler.cc
+++ b/libweave/src/base_api_handler.cc
@@ -46,7 +46,11 @@
                                         weak_ptr_factory_.GetWeakPtr()));
 }
 
-void BaseApiHandler::UpdateBaseConfiguration(Command* command) {
+void BaseApiHandler::UpdateBaseConfiguration(
+    const std::weak_ptr<Command>& cmd) {
+  auto command = cmd.lock();
+  if (!command)
+    return;
   CHECK(command->GetStatus() == CommandStatus::kQueued)
       << EnumToString(command->GetStatus());
   command->SetProgress(base::DictionaryValue{}, nullptr);
@@ -83,7 +87,10 @@
   device_->SetStateProperties(state, nullptr);
 }
 
-void BaseApiHandler::UpdateDeviceInfo(Command* command) {
+void BaseApiHandler::UpdateDeviceInfo(const std::weak_ptr<Command>& cmd) {
+  auto command = cmd.lock();
+  if (!command)
+    return;
   CHECK(command->GetStatus() == CommandStatus::kQueued)
       << EnumToString(command->GetStatus());
   command->SetProgress(base::DictionaryValue{}, nullptr);
diff --git a/libweave/src/base_api_handler.h b/libweave/src/base_api_handler.h
index 7712de1..c690b03 100644
--- a/libweave/src/base_api_handler.h
+++ b/libweave/src/base_api_handler.h
@@ -28,8 +28,8 @@
   BaseApiHandler(DeviceRegistrationInfo* device_info, Device* device);
 
  private:
-  void UpdateBaseConfiguration(Command* command);
-  void UpdateDeviceInfo(Command* command);
+  void UpdateBaseConfiguration(const std::weak_ptr<Command>& command);
+  void UpdateDeviceInfo(const std::weak_ptr<Command>& command);
   bool UpdateState(const std::string& anonymous_access_role,
                    bool discovery_enabled,
                    bool pairing_enabled);
diff --git a/libweave/src/commands/cloud_command_proxy.h b/libweave/src/commands/cloud_command_proxy.h
index c5be02e..711befa 100644
--- a/libweave/src/commands/cloud_command_proxy.h
+++ b/libweave/src/commands/cloud_command_proxy.h
@@ -17,6 +17,7 @@
 
 #include "src/backoff_entry.h"
 #include "src/commands/cloud_command_update_interface.h"
+#include "src/commands/command_instance.h"
 #include "src/states/state_change_queue_interface.h"
 
 namespace weave {
@@ -28,7 +29,7 @@
 }
 
 // Command proxy which publishes command updates to the cloud.
-class CloudCommandProxy final : public Command::Observer {
+class CloudCommandProxy final : public CommandInstance::Observer {
  public:
   CloudCommandProxy(CommandInstance* command_instance,
                     CloudCommandUpdateInterface* cloud_command_updater,
@@ -93,7 +94,7 @@
   // successfully.
   UpdateID last_state_update_id_{0};
 
-  ScopedObserver<Command, Command::Observer> observer_{this};
+  ScopedObserver<CommandInstance, CommandInstance::Observer> observer_{this};
 
   base::WeakPtrFactory<CloudCommandProxy> backoff_weak_ptr_factory_{this};
   base::WeakPtrFactory<CloudCommandProxy> weak_ptr_factory_{this};
diff --git a/libweave/src/commands/command_instance.cc b/libweave/src/commands/command_instance.cc
index a8891f7..305a255 100644
--- a/libweave/src/commands/command_instance.cc
+++ b/libweave/src/commands/command_instance.cc
@@ -37,6 +37,12 @@
     {CommandOrigin::kCloud, "cloud"},
 };
 
+void ReportDestroyedError(ErrorPtr* error) {
+  Error::AddTo(error, FROM_HERE, errors::commands::kDomain,
+               errors::commands::kCommandDestroyed,
+               "Command has been destroyed");
+}
+
 }  // namespace
 
 template <>
@@ -92,6 +98,10 @@
 
 bool CommandInstance::SetProgress(const base::DictionaryValue& progress,
                                   ErrorPtr* error) {
+  if (!command_definition_) {
+    ReportDestroyedError(error);
+    return false;
+  }
   ObjectPropType obj_prop_type;
   obj_prop_type.SetObjectSchema(command_definition_->GetProgress()->Clone());
 
@@ -110,6 +120,10 @@
 
 bool CommandInstance::SetResults(const base::DictionaryValue& results,
                                  ErrorPtr* error) {
+  if (!command_definition_) {
+    ReportDestroyedError(error);
+    return false;
+  }
   ObjectPropType obj_prop_type;
   obj_prop_type.SetObjectSchema(command_definition_->GetResults()->Clone());
 
diff --git a/libweave/src/commands/command_instance.h b/libweave/src/commands/command_instance.h
index 8a54b05..20e1daa 100644
--- a/libweave/src/commands/command_instance.h
+++ b/libweave/src/commands/command_instance.h
@@ -31,6 +31,17 @@
 
 class CommandInstance final : public Command {
  public:
+  class Observer {
+   public:
+    virtual void OnResultsChanged() = 0;
+    virtual void OnStatusChanged() = 0;
+    virtual void OnProgressChanged() = 0;
+    virtual void OnCommandDestroyed() = 0;
+
+   protected:
+    virtual ~Observer() = default;
+  };
+
   // Construct a command instance given the full command |name| which must
   // be in format "<package_name>.<command_name>", a command |category| and
   // a list of parameters and their values specified in |parameters|.
@@ -42,8 +53,6 @@
 
   // Command overrides.
   std::unique_ptr<base::DictionaryValue> ToJson() const override;
-  void AddObserver(Observer* observer) override;
-  void RemoveObserver(Observer* observer) override;
   const std::string& GetID() const override;
   const std::string& GetName() const override;
   CommandStatus GetStatus() const override;
@@ -82,8 +91,17 @@
   // Sets the command ID (normally done by CommandQueue when the command
   // instance is added to it).
   void SetID(const std::string& id) { id_ = id; }
+
+  void AddObserver(Observer* observer);
+  void RemoveObserver(Observer* observer);
+
   // Sets the pointer to queue this command is part of.
-  void SetCommandQueue(CommandQueue* queue) { queue_ = queue; }
+  void AttachToQueue(CommandQueue* queue) { queue_ = queue; }
+  void DetachFromQueue() {
+    observers_.Clear();
+    queue_ = nullptr;
+    command_definition_ = nullptr;
+  }
 
  private:
   // Helper function to update the command status.
@@ -101,7 +119,7 @@
   // The origin of the command, either "local" or "cloud".
   CommandOrigin origin_ = CommandOrigin::kLocal;
   // Command definition.
-  const CommandDefinition* command_definition_;
+  const CommandDefinition* command_definition_{nullptr};
   // Command parameters and their values.
   ValueMap parameters_;
   // Current command execution progress.
diff --git a/libweave/src/commands/command_manager.cc b/libweave/src/commands/command_manager.cc
index efca5ff..22d00dc 100644
--- a/libweave/src/commands/command_manager.cc
+++ b/libweave/src/commands/command_manager.cc
@@ -182,7 +182,7 @@
 
 void CommandManager::AddCommandHandler(
     const std::string& command_name,
-    const CommandQueue::CommandCallback& callback) {
+    const Device::CommandHandlerCallback& callback) {
   CHECK(command_name.empty() || base_dictionary_.FindCommand(command_name))
       << "Command undefined: " << command_name;
   command_queue_.AddCommandHandler(command_name, callback);
diff --git a/libweave/src/commands/command_manager.h b/libweave/src/commands/command_manager.h
index f34a907..fe3cb71 100644
--- a/libweave/src/commands/command_manager.h
+++ b/libweave/src/commands/command_manager.h
@@ -36,7 +36,7 @@
   void AddCommandAddedCallback(const CommandQueue::CommandCallback& callback);
   void AddCommandRemovedCallback(const CommandQueue::CommandCallback& callback);
   void AddCommandHandler(const std::string& command_name,
-                         const CommandQueue::CommandCallback& callback);
+                         const Device::CommandHandlerCallback& callback);
 
   // Sets callback which is called when command definitions is changed.
   void AddCommandDefChanged(const base::Closure& callback);
diff --git a/libweave/src/commands/command_queue.cc b/libweave/src/commands/command_queue.cc
index df86d77..efdcfdc 100644
--- a/libweave/src/commands/command_queue.cc
+++ b/libweave/src/commands/command_queue.cc
@@ -24,8 +24,9 @@
   on_command_removed_.push_back(callback);
 }
 
-void CommandQueue::AddCommandHandler(const std::string& command_name,
-                                     const CommandCallback& callback) {
+void CommandQueue::AddCommandHandler(
+    const std::string& command_name,
+    const Device::CommandHandlerCallback& callback) {
   if (!command_name.empty()) {
     CHECK(default_command_callback_.is_null())
         << "Commands specific handler are not allowed after default one";
@@ -33,7 +34,7 @@
     for (const auto& command : map_) {
       if (command.second->GetStatus() == CommandStatus::kQueued &&
           command.second->GetName() == command_name) {
-        callback.Run(command.second.get());
+        callback.Run(command.second);
       }
     }
 
@@ -45,7 +46,7 @@
       if (command.second->GetStatus() == CommandStatus::kQueued &&
           command_callbacks_.find(command.second->GetName()) ==
               command_callbacks_.end()) {
-        callback.Run(command.second.get());
+        callback.Run(command.second);
       }
     }
 
@@ -57,7 +58,7 @@
 void CommandQueue::Add(std::unique_ptr<CommandInstance> instance) {
   std::string id = instance->GetID();
   LOG_IF(FATAL, id.empty()) << "Command has no ID";
-  instance->SetCommandQueue(this);
+  instance->AttachToQueue(this);
   auto pair = map_.insert(std::make_pair(id, std::move(instance)));
   LOG_IF(FATAL, !pair.second) << "Command with ID '" << id
                               << "' is already in the queue";
@@ -67,9 +68,9 @@
   auto it_handler = command_callbacks_.find(pair.first->second->GetName());
 
   if (it_handler != command_callbacks_.end())
-    it_handler->second.Run(pair.first->second.get());
+    it_handler->second.Run(pair.first->second);
   else if (!default_command_callback_.is_null())
-    default_command_callback_.Run(pair.first->second.get());
+    default_command_callback_.Run(pair.first->second);
 
   Cleanup();
 }
@@ -88,8 +89,8 @@
   auto p = map_.find(id);
   if (p == map_.end())
     return false;
-  std::unique_ptr<CommandInstance> instance{std::move(p->second)};
-  instance->SetCommandQueue(nullptr);
+  std::shared_ptr<CommandInstance> instance = p->second;
+  instance->DetachFromQueue();
   map_.erase(p);
   for (const auto& cb : on_command_removed_)
     cb.Run(instance.get());
diff --git a/libweave/src/commands/command_queue.h b/libweave/src/commands/command_queue.h
index 888c04f..99da0b2 100644
--- a/libweave/src/commands/command_queue.h
+++ b/libweave/src/commands/command_queue.h
@@ -25,7 +25,8 @@
  public:
   CommandQueue() = default;
 
-  using CommandCallback = Device::CommandHandlerCallback;
+  // TODO: Remove AddCommandAddedCallback and AddCommandRemovedCallback.
+  using CommandCallback = base::Callback<void(Command* command)>;
 
   // Adds notifications callback for a new command is added to the queue.
   void AddCommandAddedCallback(const CommandCallback& callback);
@@ -34,7 +35,7 @@
   void AddCommandRemovedCallback(const CommandCallback& callback);
 
   void AddCommandHandler(const std::string& command_name,
-                         const CommandCallback& callback);
+                         const Device::CommandHandlerCallback& callback);
 
   // Checks if the command queue is empty.
   bool IsEmpty() const { return map_.empty(); }
@@ -75,7 +76,7 @@
   base::Time test_now_;
 
   // ID-to-CommandInstance map.
-  std::map<std::string, std::unique_ptr<CommandInstance>> map_;
+  std::map<std::string, std::shared_ptr<CommandInstance>> map_;
 
   // Queue of commands to be removed.
   std::queue<std::pair<base::Time, std::string>> remove_queue_;
@@ -83,8 +84,8 @@
   using CallbackList = std::vector<CommandCallback>;
   CallbackList on_command_added_;
   CallbackList on_command_removed_;
-  std::map<std::string, CommandCallback> command_callbacks_;
-  CommandCallback default_command_callback_;
+  std::map<std::string, Device::CommandHandlerCallback> command_callbacks_;
+  Device::CommandHandlerCallback default_command_callback_;
 
   DISALLOW_COPY_AND_ASSIGN(CommandQueue);
 };
diff --git a/libweave/src/commands/schema_constants.cc b/libweave/src/commands/schema_constants.cc
index 9affe73..02999f7 100644
--- a/libweave/src/commands/schema_constants.cc
+++ b/libweave/src/commands/schema_constants.cc
@@ -25,6 +25,7 @@
 const char kCommandFailed[] = "command_failed";
 const char kInvalidCommandVisibility[] = "invalid_command_visibility";
 const char kInvalidMinimalRole[] = "invalid_minimal_role";
+const char kCommandDestroyed[] = "command_destroyed";
 }  // namespace commands
 }  // namespace errors
 
diff --git a/libweave/src/commands/schema_constants.h b/libweave/src/commands/schema_constants.h
index 2d4ae07..9eb8051 100644
--- a/libweave/src/commands/schema_constants.h
+++ b/libweave/src/commands/schema_constants.h
@@ -28,6 +28,7 @@
 extern const char kCommandFailed[];
 extern const char kInvalidCommandVisibility[];
 extern const char kInvalidMinimalRole[];
+extern const char kCommandDestroyed[];
 }  // namespace commands
 }  // namespace errors