diff --git a/libweave/examples/ubuntu/avahi_client.cc b/libweave/examples/ubuntu/avahi_client.cc
index b14d45c..11f16c7 100644
--- a/libweave/examples/ubuntu/avahi_client.cc
+++ b/libweave/examples/ubuntu/avahi_client.cc
@@ -46,9 +46,9 @@
     avahi_threaded_poll_stop(thread_pool_.get());
 }
 
-void MdnsImpl::PublishService(const std::string& service_name,
+void MdnsImpl::PublishService(const std::string& service_type,
                               uint16_t port,
-                              const std::map<std::string, std::string>& txt) {
+                              const std::vector<std::string>& txt) {
   LOG(INFO) << "Publishing service";
   CHECK(group_);
 
@@ -56,11 +56,8 @@
   std::unique_ptr<AvahiStringList, decltype(&avahi_string_list_free)> txt_list{
       nullptr, &avahi_string_list_free};
   if (!txt.empty()) {
-    std::vector<std::string> txt_vector;
-    for (const auto& i : txt)
-      txt_vector.push_back(i.first + "=" + i.second);
     std::vector<const char*> txt_vector_ptr;
-    for (const auto& i : txt_vector)
+    for (const auto& i : txt)
       txt_vector_ptr.push_back(i.c_str());
     txt_list.reset(avahi_string_list_new_from_array(txt_vector_ptr.data(),
                                                     txt_vector_ptr.size()));
@@ -68,22 +65,21 @@
   }
 
   int ret = 0;
-  if (prev_port_ == port && prev_type_ == service_name) {
+  if (prev_port_ == port && prev_type_ == service_type) {
     ret = avahi_entry_group_update_service_txt_strlst(
         group_.get(), AVAHI_IF_UNSPEC, AVAHI_PROTO_UNSPEC, {}, GetId().c_str(),
-        ("_" + service_name + "._tcp").c_str(), nullptr, txt_list.get());
+        service_type.c_str(), nullptr, txt_list.get());
     CHECK_GE(ret, 0) << avahi_strerror(ret);
   } else {
     prev_port_ = port;
-    prev_type_ = service_name;
+    prev_type_ = service_type;
 
     avahi_entry_group_reset(group_.get());
     CHECK(avahi_entry_group_is_empty(group_.get()));
 
     ret = avahi_entry_group_add_service_strlst(
         group_.get(), AVAHI_IF_UNSPEC, AVAHI_PROTO_UNSPEC, {}, GetId().c_str(),
-        ("_" + service_name + "._tcp").c_str(), nullptr, nullptr, port,
-        txt_list.get());
+        service_type.c_str(), nullptr, nullptr, port, txt_list.get());
     CHECK_GE(ret, 0) << avahi_strerror(ret);
     ret = avahi_entry_group_commit(group_.get());
     CHECK_GE(ret, 0) << avahi_strerror(ret);
@@ -96,7 +92,7 @@
 }
 
 std::string MdnsImpl::GetId() const {
-  return "Weave example " + std::to_string(gethostid());
+  return "WEAVE" + std::to_string(gethostid());
 }
 
 }  // namespace examples
diff --git a/libweave/examples/ubuntu/avahi_client.h b/libweave/examples/ubuntu/avahi_client.h
index 6b5d1b0..90abd76 100644
--- a/libweave/examples/ubuntu/avahi_client.h
+++ b/libweave/examples/ubuntu/avahi_client.h
@@ -23,9 +23,9 @@
   MdnsImpl();
 
   ~MdnsImpl() override;
-  void PublishService(const std::string& service_name,
+  void PublishService(const std::string& service_type,
                       uint16_t port,
-                      const std::map<std::string, std::string>& txt) override;
+                      const std::vector<std::string>& txt) override;
   void StopPublishing(const std::string& service_name) override;
   std::string GetId() const override;
 
diff --git a/libweave/examples/ubuntu/build.sh b/libweave/examples/ubuntu/build.sh
index 96d0ab6..0f02a17 100755
--- a/libweave/examples/ubuntu/build.sh
+++ b/libweave/examples/ubuntu/build.sh
@@ -16,12 +16,13 @@
 
 export BUILD_TARGET=$*
 if [ -z "$BUILD_TARGET" ]; then
-   export BUILD_TARGET="weave libweave_testrunner"
+   export BUILD_TARGET="weave libweave_testrunner libweave_exports_testrunner"
 fi
 
 export CORES=`cat /proc/cpuinfo | grep processor | wc -l`
 ninja -j $CORES -C out/${BUILD_CONFIG} $BUILD_TARGET || exit 1
 
 if [[ $BUILD_TARGET == *"libweave_testrunner"* ]]; then
-  out/${BUILD_CONFIG}/libweave_testrunner
+  out/${BUILD_CONFIG}/libweave_testrunner || exit 1
+  out/${BUILD_CONFIG}/libweave_exports_testrunner || exit 1
 fi
diff --git a/libweave/include/weave/mdns.h b/libweave/include/weave/mdns.h
index 09b42e8..b149277 100644
--- a/libweave/include/weave/mdns.h
+++ b/libweave/include/weave/mdns.h
@@ -5,8 +5,8 @@
 #ifndef LIBWEAVE_INCLUDE_WEAVE_MDNS_H_
 #define LIBWEAVE_INCLUDE_WEAVE_MDNS_H_
 
-#include <map>
 #include <string>
+#include <vector>
 
 #include <base/callback.h>
 
@@ -15,12 +15,9 @@
 class Mdns {
  public:
   // Publishes new service on mDns or updates existing one.
-  // TODO(vitlaybuka): txt -> vector<string>
-  // TODO(vitlaybuka): service_name -> service_type
-  virtual void PublishService(
-      const std::string& service_type,
-      uint16_t port,
-      const std::map<std::string, std::string>& txt) = 0;
+  virtual void PublishService(const std::string& service_type,
+                              uint16_t port,
+                              const std::vector<std::string>& txt) = 0;
 
   // Stops publishing service.
   virtual void StopPublishing(const std::string& service_type) = 0;
diff --git a/libweave/include/weave/test/mock_mdns.h b/libweave/include/weave/test/mock_mdns.h
index 1045ce0..40beeac 100644
--- a/libweave/include/weave/test/mock_mdns.h
+++ b/libweave/include/weave/test/mock_mdns.h
@@ -7,8 +7,8 @@
 
 #include <weave/mdns.h>
 
-#include <map>
 #include <string>
+#include <vector>
 
 #include <gmock/gmock.h>
 
@@ -20,7 +20,7 @@
   MOCK_METHOD3(PublishService,
                void(const std::string&,
                     uint16_t,
-                    const std::map<std::string, std::string>&));
+                    const std::vector<std::string>&));
   MOCK_METHOD1(StopPublishing, void(const std::string&));
   MOCK_CONST_METHOD0(GetId, std::string());
 };
diff --git a/libweave/src/privet/publisher.cc b/libweave/src/privet/publisher.cc
index 85576cf..e4accb1 100644
--- a/libweave/src/privet/publisher.cc
+++ b/libweave/src/privet/publisher.cc
@@ -20,10 +20,8 @@
 
 namespace {
 
-// The name of the service we'll expose via peerd.
-// TODO(rginda): This should become the proper mdns service, "_privet._tcp"
-// if we drop peerd on ChromeOS.
-const char kPrivetServiceType[] = "privet";
+// The service type we'll expose via mdns.
+const char kPrivetServiceType[] = "_privet._tcp";
 
 }  // namespace
 
@@ -69,20 +67,20 @@
     services += "_";
   services += Join(",_", cloud_->GetServices());
 
-  std::map<std::string, std::string> txt_record{
-      {"txtvers", "3"},
-      {"ty", name},
-      {"services", services},
-      {"id", GetId()},
-      {"mmid", model_id},
-      {"flags", WifiSsidGenerator{cloud_, wifi_}.GenerateFlags()},
+  std::vector<std::string> txt_record{
+      {"txtvers=3"},
+      {"ty=" + name},
+      {"services=" + services},
+      {"id=" + GetId()},
+      {"mmid=" + model_id},
+      {"flags=" + WifiSsidGenerator{cloud_, wifi_}.GenerateFlags()},
   };
 
   if (!cloud_->GetCloudId().empty())
-    txt_record.emplace("gcd_id", cloud_->GetCloudId());
+    txt_record.emplace_back("gcd_id=" + cloud_->GetCloudId());
 
   if (!cloud_->GetDescription().empty())
-    txt_record.emplace("note", cloud_->GetDescription());
+    txt_record.emplace_back("note=" + cloud_->GetDescription());
 
   is_publishing_ = true;
   mdns_->PublishService(kPrivetServiceType, port, txt_record);
diff --git a/libweave/src/weave_unittest.cc b/libweave/src/weave_unittest.cc
index fb00b8e..7b3bbdb 100644
--- a/libweave/src/weave_unittest.cc
+++ b/libweave/src/weave_unittest.cc
@@ -153,6 +153,14 @@
 
 const char kStateDefaults[] = R"({"power": {"battery_level":44}})";
 
+MATCHER_P(MatchTxt, txt, "") {
+  std::vector<std::string> txt_copy = txt;
+  std::sort(txt_copy.begin(), txt_copy.end());
+  std::vector<std::string> arg_copy = arg;
+  std::sort(arg_copy.begin(), arg_copy.end());
+  return (arg_copy == txt_copy);
+}
+
 class WeaveTest : public ::testing::Test {
  protected:
   void SetUp() override { device_ = weave::Device::Create(); }
@@ -223,27 +231,28 @@
   void InitMdns() {
     EXPECT_CALL(mdns_, GetId()).WillRepeatedly(Return("TEST_ID"));
     InitMdnsPublishing(false);
-    EXPECT_CALL(mdns_, StopPublishing("privet")).WillOnce(Return());
+    EXPECT_CALL(mdns_, StopPublishing("_privet._tcp")).WillOnce(Return());
   }
 
   void InitMdnsPublishing(bool registered) {
-    std::map<std::string, std::string> txt{
-        {"id", "TEST_ID"},     {"flags", "DB"},  {"mmid", "ABCDE"},
-        {"services", "_base"}, {"txtvers", "3"}, {"ty", "DEVICE_NAME"}};
+    std::vector<std::string> txt{{"id=TEST_ID"}, {"flags=DB"},
+                                 {"mmid=ABCDE"}, {"services=_base"},
+                                 {"txtvers=3"},  {"ty=DEVICE_NAME"}};
     if (registered) {
-      txt["gcd_id"] = "DEVICE_ID";
+      txt.push_back("gcd_id=DEVICE_ID");
 
       // During registration device may announce itself twice:
       // 1. with GCD ID but not connected (DB)
       // 2. with GCD ID and connected (BB)
-      EXPECT_CALL(mdns_, PublishService("privet", 11, txt))
+      EXPECT_CALL(mdns_, PublishService("_privet._tcp", 11, MatchTxt(txt)))
           .Times(AtMost(1))
           .WillOnce(Return());
 
-      txt["flags"] = "BB";
+      txt[1] = "flags=BB";
     }
 
-    EXPECT_CALL(mdns_, PublishService("privet", 11, txt)).WillOnce(Return());
+    EXPECT_CALL(mdns_, PublishService("_privet._tcp", 11, MatchTxt(txt)))
+        .WillOnce(Return());
   }
 
   void InitHttpServer() {