diff --git a/nsync/src/sync-diff-leaf.cc b/nsync/src/sync-diff-leaf.cc
new file mode 100644
index 0000000..bdbbd1b
--- /dev/null
+++ b/nsync/src/sync-diff-leaf.cc
@@ -0,0 +1,74 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-diff-leaf.h"
+#include <boost/throw_exception.hpp>
+typedef boost::error_info<struct tag_errmsg, std::string> errmsg_info; 
+
+using namespace Sync::Error;
+
+namespace Sync {
+
+DiffLeaf::DiffLeaf (NameInfoConstPtr info, const SeqNo &seq)
+  : Leaf (info, seq)
+  , m_op (UPDATE)
+{
+}
+
+DiffLeaf::DiffLeaf (NameInfoConstPtr info)
+  : Leaf (info, SeqNo (0,0))
+  , m_op (REMOVE)
+{
+}
+
+std::ostream &
+operator << (std::ostream &os, Operation op)
+{
+  switch (op)
+    {
+    case UPDATE:
+      os << "update";
+      break;
+    case REMOVE:
+      os << "remove";
+      break;
+    }
+  return os;
+}
+
+std::istream &
+operator >> (std::istream &is, Operation &op)
+{
+  std::string operation;
+  is >> operation;
+  if (operation == "update")
+    op = UPDATE;
+  else if (operation == "remove")
+    op = REMOVE;
+  else
+    BOOST_THROW_EXCEPTION (SyncDiffLeafOperationParseError () << errmsg_info (operation));
+
+  return is;
+}
+
+
+}
diff --git a/nsync/src/sync-diff-leaf.h b/nsync/src/sync-diff-leaf.h
new file mode 100644
index 0000000..6e09efe
--- /dev/null
+++ b/nsync/src/sync-diff-leaf.h
@@ -0,0 +1,91 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_DIFF_LEAF_H
+#define SYNC_DIFF_LEAF_H
+
+#include "sync-leaf.h"
+#include <boost/exception/all.hpp>
+
+namespace Sync {
+
+/**
+ * @ingroup sync
+ * @brief Annotation for SYNC leaf
+ */
+enum Operation
+  {
+    UPDATE, ///< @brief Leaf was added or updated
+    REMOVE  ///< @brief Leaf was removed
+  };
+
+/**
+ * @ingroup sync
+ * @brief Annotated SYNC leaf 
+ */
+class DiffLeaf : public Leaf
+{
+public:
+  /**
+   * @brief Constructor to create an UPDATE diff leaf
+   * @param info Smart pointer to leaf's name
+   * @param seq  Initial sequence number of the pointer
+   */
+  DiffLeaf (NameInfoConstPtr info, const SeqNo &seq);
+
+  /**
+   * @brief Constructor to create an REMOVE diff leaf
+   * @param info Smart pointer to leaf's name
+   *
+   * This constructor creates a leaf with phony sequence number
+   * with 0 session ID and 0 sequence number
+   */
+  DiffLeaf (NameInfoConstPtr info);
+
+  virtual ~DiffLeaf () { }
+
+  /**
+   * @brief Get diff leaf type
+   */
+  Operation
+  getOperation () const { return m_op; }
+
+private:
+  Operation m_op;
+};
+
+typedef boost::shared_ptr<DiffLeaf> DiffLeafPtr;
+typedef boost::shared_ptr<const DiffLeaf> DiffLeafConstPtr;
+
+std::ostream &
+operator << (std::ostream &os, Operation op);
+
+std::istream &
+operator >> (std::istream &is, Operation &op);
+
+namespace Error {
+struct SyncDiffLeafOperationParseError : virtual boost::exception, virtual std::exception { };
+} // Error
+
+} // Sync
+
+#endif // SYNC_DIFF_LEAF_H
diff --git a/nsync/src/sync-diff-state-container.h b/nsync/src/sync-diff-state-container.h
new file mode 100644
index 0000000..2ae7c59
--- /dev/null
+++ b/nsync/src/sync-diff-state-container.h
@@ -0,0 +1,72 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_DIFF_STATE_CONTAINER_H
+#define SYNC_DIFF_STATE_CONTAINER_H
+
+#include "sync-diff-state.h"
+#include "sync-digest.h"
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/tag.hpp>
+// #include <boost/multi_index/ordered_index.hpp>
+// #include <boost/multi_index/composite_key.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+// #include <boost/multi_index/random_access_index.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+
+namespace mi = boost::multi_index;
+
+namespace Sync {
+
+/// @cond include_hidden 
+struct sequenced { };
+struct timed { };
+/// @endcond
+
+/**
+ * \ingroup sync
+ * @brief Container for differential states
+ */
+struct DiffStateContainer : public mi::multi_index_container<
+  DiffStatePtr,
+  mi::indexed_by<
+    // For fast access to elements using DiffState hashes
+    mi::hashed_unique<
+      mi::tag<hashed>,
+      mi::const_mem_fun<DiffState, DigestConstPtr, &DiffState::getDigest>,
+      DigestPtrHash,
+      DigestPtrEqual
+      >
+    ,        
+    // sequenced index to access older/newer element (like in list)
+    mi::sequenced<mi::tag<sequenced> >
+    >
+  >
+{
+};
+
+} // Sync
+
+#endif // SYNC_DIFF_STATE_CONTAINER_H
diff --git a/nsync/src/sync-diff-state.cc b/nsync/src/sync-diff-state.cc
new file mode 100644
index 0000000..3030940
--- /dev/null
+++ b/nsync/src/sync-diff-state.cc
@@ -0,0 +1,101 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-diff-state.h"
+#include "sync-diff-leaf.h"
+
+#include <boost/make_shared.hpp>
+#include <boost/foreach.hpp>
+#include <boost/assert.hpp>
+
+using namespace boost;
+
+namespace Sync {
+
+DiffState::DiffState ()
+{
+}
+
+DiffState::~DiffState ()
+{
+}
+
+DiffStatePtr
+DiffState::diff () const
+{
+  DiffStatePtr ret = make_shared<DiffState> ();
+  
+  DiffStatePtr state = m_next;
+  while (state != 0)
+    {
+      *ret += *state;
+      state = state->m_next;
+    }
+
+  return ret;
+}
+
+DiffState &
+DiffState::operator += (const DiffState &state)
+{
+  BOOST_FOREACH (LeafConstPtr _leaf, state.getLeaves ())
+    {
+      DiffLeafConstPtr leaf = dynamic_pointer_cast<const DiffLeaf> (_leaf);
+      BOOST_ASSERT (leaf != 0);
+
+      if (leaf->getOperation () == UPDATE)
+        update (leaf->getInfo (), leaf->getSeq ());
+      else if (leaf->getOperation () == REMOVE)
+        remove (leaf->getInfo ());
+      else
+        {
+          BOOST_ASSERT (false);
+        }
+    }
+  
+  return *this;
+}
+  
+// from State
+boost::tuple<bool/*inserted*/, bool/*updated*/, SeqNo/*oldSeqNo*/>
+DiffState::update (NameInfoConstPtr info, const SeqNo &seq)
+{
+  m_leaves.erase (info);
+
+  DiffLeafPtr leaf = make_shared<DiffLeaf> (info, cref (seq));
+  m_leaves.insert (leaf);
+
+  return make_tuple (true, false, SeqNo ());
+}
+
+bool
+DiffState::remove (NameInfoConstPtr info)
+{
+  m_leaves.erase (info);
+
+  DiffLeafPtr leaf = make_shared<DiffLeaf> (info);
+  m_leaves.insert (leaf);
+
+  return true;
+}
+
+} // ns3
diff --git a/nsync/src/sync-diff-state.h b/nsync/src/sync-diff-state.h
new file mode 100644
index 0000000..d944c3e
--- /dev/null
+++ b/nsync/src/sync-diff-state.h
@@ -0,0 +1,102 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_DIFF_STATE_H
+#define SYNC_DIFF_STATE_H
+
+#include "sync-state.h"
+#include <iostream>
+
+namespace Sync {
+
+class DiffState;
+typedef boost::shared_ptr<DiffState> DiffStatePtr;
+typedef boost::shared_ptr<DiffState> DiffStateConstPtr;
+
+/**
+ * @ingroup ccnx
+ * @brief Differential SYNC state
+ */
+class DiffState : public State
+{
+public:
+  /**
+   * @see Default constructor
+   */
+  DiffState ();
+  virtual ~DiffState ();
+
+  /**
+   * @brief Set successor for the diff state
+   * @param next successor state
+   */
+  void
+  setNext (DiffStatePtr next)
+  {
+    m_next = next;
+  }
+
+  /**
+   * @brief Set digest for the diff state (obtained from a corresponding full state)
+   * @param digest A read only smart pointer to a digest object (that should be unmodified anywhere else)
+   */
+  void
+  setDigest (DigestConstPtr digest) { m_digest = digest; }
+
+  /**
+   * @brief Get digest for the diff state
+   */
+  DigestConstPtr
+  getDigest () const { return m_digest; }
+  
+  /**
+   * @brief Accumulate differences from `this' state to the most current state
+   * @returns Accumulated differences from `this' state to the most current state
+   */
+  DiffStatePtr
+  diff () const;
+
+  /**
+   * @brief Combine differences from `this' and `state'
+   * @param state Differential state to combine with
+   * @return Combined differences
+   *
+   * In case of collisions, `this' leaf will be replaced with the leaf of `state'
+   */
+  DiffState&
+  operator += (const DiffState &state);
+  
+  // from State
+  virtual boost::tuple<bool/*inserted*/, bool/*updated*/, SeqNo/*oldSeqNo*/>
+  update (NameInfoConstPtr info, const SeqNo &seq);
+
+  virtual bool
+  remove (NameInfoConstPtr info);
+  
+private:
+  DiffStatePtr m_next;
+  DigestConstPtr m_digest;
+};
+
+} // Sync
+
+#endif // SYNC_DIFF_STATE_H
diff --git a/nsync/src/sync-digest.cc b/nsync/src/sync-digest.cc
new file mode 100644
index 0000000..6f41d3d
--- /dev/null
+++ b/nsync/src/sync-digest.cc
@@ -0,0 +1,265 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-digest.h"
+#include <string.h>
+
+#include <boost/assert.hpp>
+#include <boost/throw_exception.hpp>
+typedef boost::error_info<struct tag_errmsg, std::string> errmsg_info_str; 
+typedef boost::error_info<struct tag_errmsg, int> errmsg_info_int; 
+
+// for printing, may be disabled in optimized build
+
+// #ifdef DIGEST_BASE64
+// #include <boost/archive/iterators/base64_from_binary.hpp>
+// #include <boost/archive/iterators/binary_from_base64.hpp>
+// #endif
+
+#include <boost/archive/iterators/transform_width.hpp>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/archive/iterators/dataflow_exception.hpp>
+
+using namespace boost;
+using namespace boost::archive::iterators;
+using namespace std;
+
+// Other options: VP_md2, EVP_md5, EVP_sha, EVP_sha1, EVP_sha256, EVP_dss, EVP_dss1, EVP_mdc2, EVP_ripemd160
+#define HASH_FUNCTION EVP_sha256
+#define HASH_FUNCTION_LEN 32
+
+
+// #ifndef DIGEST_BASE64
+
+template<class CharType>
+struct hex_from_4_bit
+{
+  typedef CharType result_type;
+  CharType operator () (CharType ch) const
+  {
+    const char *lookup_table = "0123456789abcdef";
+    // cout << "New character: " << (int) ch << " (" << (char) ch << ")" << "\n";
+    BOOST_ASSERT (ch < 16);
+    return lookup_table[static_cast<size_t>(ch)];
+  }
+};
+
+typedef transform_iterator<hex_from_4_bit<std::vector<uint8_t>::const_iterator::value_type>,
+                           transform_width<std::vector<uint8_t>::const_iterator, 4, 8, std::vector<uint8_t>::const_iterator::value_type> > string_from_binary;
+
+
+template<class CharType>
+struct hex_to_4_bit
+{
+  typedef CharType result_type;
+  CharType operator () (CharType ch) const
+  {
+    const signed char lookup_table [] = {
+      -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+      -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+      -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+      0, 1, 2, 3, 4, 5, 6, 7, 8, 9,-1,-1,-1,-1,-1,-1,
+      -1,10,11,12,13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+      -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+      -1,10,11,12,13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1,
+      -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
+    };
+
+    // cout << "New character: " << hex << (int) ch << " (" << (char) ch << ")" << "\n";
+    signed char value = -1;
+    if ((unsigned)ch < 128)
+      value = lookup_table [(unsigned)ch];
+    if (value == -1)
+      BOOST_THROW_EXCEPTION (Sync::Error::DigestCalculationError () << errmsg_info_int ((int)ch));
+    
+    return value;
+  }
+};
+
+typedef transform_width<transform_iterator<hex_to_4_bit<string::const_iterator::value_type>, string::const_iterator>, 8, 4> string_to_binary;
+
+namespace Sync {
+
+Digest::Digest ()
+{
+  m_context = EVP_MD_CTX_create ();
+
+  reset ();
+}
+
+Digest::~Digest ()
+{
+  EVP_MD_CTX_destroy (m_context);
+}
+
+bool
+Digest::empty () const
+{
+  return m_buffer.empty ();
+}
+
+bool
+Digest::isZero () const
+{
+  if (m_buffer.empty ())
+    BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+                           << errmsg_info_str ("Digest has not been yet finalized"));
+
+  return (m_buffer.size () == 1 && m_buffer[0] == 0);
+}
+
+
+void
+Digest::reset ()
+{
+  m_buffer.clear ();
+
+  int ok = EVP_DigestInit_ex (m_context, HASH_FUNCTION (), 0);
+  if (!ok)
+    BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+                           << errmsg_info_str ("EVP_DigestInit_ex returned error")
+                           << errmsg_info_int (ok));
+}
+
+
+void
+Digest::finalize ()
+{
+  if (!m_buffer.empty ()) return;
+
+  m_buffer.resize (HASH_FUNCTION_LEN);
+  
+  unsigned int tmp;
+  int ok = EVP_DigestFinal_ex (m_context,
+			       &m_buffer[0], &tmp);
+  if (!ok)
+    BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+                           << errmsg_info_str ("EVP_DigestFinal_ex returned error")
+                           << errmsg_info_int (ok));
+}
+
+std::size_t
+Digest::getHash () const
+{
+  if (isZero ()) return 0;
+  
+  if (sizeof (std::size_t) > m_buffer.size ())
+    {
+      BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+                             << errmsg_info_str ("Hash is not zero and length is less than size_t")
+                             << errmsg_info_int (m_buffer.size ()));
+    }
+  
+  // just getting first sizeof(std::size_t) bytes
+  // not ideal, but should work pretty well
+  return *(reinterpret_cast<const std::size_t*> (&m_buffer[0]));
+}
+
+bool
+Digest::operator == (const Digest &digest) const
+{
+  if (m_buffer.empty ())
+    BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+                           << errmsg_info_str ("Digest1 is empty"));
+
+  if (digest.m_buffer.empty ())
+    BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+                           << errmsg_info_str ("Digest2 is empty"));
+
+  return m_buffer == digest.m_buffer;
+}
+
+
+void
+Digest::update (const uint8_t *buffer, size_t size)
+{
+  // cout << "Update: " << (void*)buffer << " / size: " << size << "\n";
+  
+  // cannot update Digest when it has been finalized
+  if (!m_buffer.empty ())
+    BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+                           << errmsg_info_str ("Digest has been already finalized"));
+
+  bool ok = EVP_DigestUpdate (m_context, buffer, size);
+  if (!ok)
+    BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+                           << errmsg_info_str ("EVP_DigestUpdate returned error")
+                           << errmsg_info_int (ok));
+}
+
+
+Digest &
+Digest::operator << (const Digest &src)
+{
+  if (src.m_buffer.empty ()) 
+    BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+                           << errmsg_info_str ("Digest has not been yet finalized"));
+
+  update (&src.m_buffer[0], src.m_buffer.size ());
+
+  return *this;
+}
+
+std::ostream &
+operator << (std::ostream &os, const Digest &digest)
+{
+  BOOST_ASSERT (!digest.m_buffer.empty ());
+  
+  ostreambuf_iterator<char> out_it (os); // ostream iterator
+  // need to encode to base64
+  copy (string_from_binary (digest.m_buffer.begin ()),
+        string_from_binary (digest.m_buffer.end ()),
+        out_it);
+
+  return os;
+}
+
+std::istream &
+operator >> (std::istream &is, Digest &digest)
+{
+  string str;
+  is >> str; // read string first
+
+  if (str.size () == 0)
+    BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+                           << errmsg_info_str ("Input is empty"));
+  
+  // uint8_t padding = (3 - str.size () % 3) % 3;
+  // for (uint8_t i = 0; i < padding; i++) str.push_back ('=');
+
+  // only empty digest object can be used for reading
+  if (!digest.m_buffer.empty ())
+    BOOST_THROW_EXCEPTION (Error::DigestCalculationError ()
+                           << errmsg_info_str ("Digest has been already finalized"));
+
+  digest.m_buffer.clear ();
+  
+  copy (string_to_binary (str.begin ()),
+        string_to_binary (str.end ()),
+        std::back_inserter (digest.m_buffer));
+
+  return is;
+}
+
+
+} // Sync
+
diff --git a/nsync/src/sync-digest.h b/nsync/src/sync-digest.h
new file mode 100644
index 0000000..ecc8522
--- /dev/null
+++ b/nsync/src/sync-digest.h
@@ -0,0 +1,199 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_DIGEST_H
+#define SYNC_DIGEST_H
+
+#include <boost/exception/all.hpp>
+#include <openssl/evp.h>
+#include <boost/cstdint.hpp>
+#include <vector>
+
+namespace Sync {
+
+/**
+ * @ingroup sync
+ * @brief A simple wrapper for libcrypto hash functions
+ */
+class Digest
+{
+public:
+  /**
+   * @brief Default constructor.  Will initialize internal libssl structures
+   */
+  Digest ();
+
+  /**
+   * @brief Check if digest is empty
+   */
+  bool
+  empty () const;
+  
+  /**
+   * @brief Reset digest to the initial state
+   */
+  void
+  reset ();
+
+  /**
+   * @brief Destructor
+   */
+  ~Digest ();
+
+  /**
+   * @brief Obtain a short version of the hash (just first sizeof(size_t) bytes
+   *
+   * Side effect: finalize() will be called on `this'
+   */
+  std::size_t
+  getHash () const;
+
+  /**
+   * @brief Finalize digest. All subsequent calls to "operator <<" will fire an exception
+   */
+  void
+  finalize ();
+
+  /**
+   * @brief Compare two full digests
+   *
+   * Side effect: Finalize will be called on `this' and `digest'
+   */
+  bool
+  operator == (const Digest &digest) const;
+
+  bool
+  operator != (const Digest &digest) const
+  { return ! (*this == digest); }
+  
+
+  /**
+   * @brief Add existing digest to digest calculation
+   * @param src digest to combine with
+   *
+   * The result of this combination is  hash (hash (...))
+   */
+  Digest &
+  operator << (const Digest &src);
+
+  /**
+   * @brief Add string to digest calculation
+   * @param str string to put into digest
+   */
+  inline Digest &
+  operator << (const std::string &str);
+
+  /**
+   * @brief Add uint64_t value to digest calculation
+   * @param value uint64_t value to put into digest
+   */
+  inline Digest &
+  operator << (uint64_t value);
+
+  /**
+   * @brief Checks if the stored hash is zero-root hash
+   *
+   * Zero-root hash is a valid hash that optimally represents an empty state
+   */
+  bool
+  isZero () const;
+  
+private:
+  Digest &
+  operator = (Digest &digest) { (void)digest; return *this; }
+  
+  /**
+   * @brief Add size bytes of buffer to the hash
+   */
+  void
+  update (const uint8_t *buffer, size_t size);
+
+  friend std::ostream &
+  operator << (std::ostream &os, const Digest &digest);
+
+  friend std::istream &
+  operator >> (std::istream &is, Digest &digest);
+  
+private:
+  EVP_MD_CTX *m_context;
+  std::vector<uint8_t> m_buffer;
+};
+
+namespace Error {
+struct DigestCalculationError : virtual boost::exception, virtual std::exception { };
+}
+
+typedef boost::shared_ptr<Digest> DigestPtr;
+typedef boost::shared_ptr<const Digest> DigestConstPtr;
+
+Digest &
+Digest::operator << (const std::string &str)
+{
+  update (reinterpret_cast<const uint8_t*> (str.c_str ()), str.size ());
+  return *this;
+}
+
+inline Digest &
+Digest::operator << (uint64_t value)
+{
+  update (reinterpret_cast<const uint8_t*> (&value), sizeof (uint64_t));
+  return *this;
+}
+
+std::ostream &
+operator << (std::ostream &os, const Digest &digest);
+
+std::istream &
+operator >> (std::istream &is, Digest &digest);
+
+// template<class INT>
+// Digest &
+// Digest::operator << (INT value)
+// {
+//   update (&value, sizeof (INT));
+//   return *this;
+// }
+
+struct DigestPtrHash : public std::unary_function<Digest, std::size_t>
+{
+  std::size_t
+  operator() (DigestConstPtr digest) const
+  {
+    // std::cout << "digest->getHash: " << digest->getHash () << " (" << *digest << ")" << std::endl;
+    return digest->getHash ();
+  }
+};
+
+struct DigestPtrEqual : public std::unary_function<Digest, std::size_t>
+{
+  bool
+  operator() (DigestConstPtr digest1, DigestConstPtr digest2) const
+  {
+    // std::cout << boost::cref(*digest1) << " == " << boost::cref(*digest2) << " : " << (*digest1 == *digest2) << std::endl;
+    return *digest1 == *digest2;
+  }
+};
+
+
+} // Sync
+
+#endif // SYNC_DIGEST_H
diff --git a/nsync/src/sync-event.h b/nsync/src/sync-event.h
new file mode 100644
index 0000000..7808947
--- /dev/null
+++ b/nsync/src/sync-event.h
@@ -0,0 +1,35 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_EVENT_H
+#define SYNC_EVENT_H
+
+#include <boost/function.hpp>
+
+namespace Sync
+{
+
+typedef boost::function< void ( ) > Event;
+
+} // Sync
+
+#endif // SYNC_EVENT_H
diff --git a/nsync/src/sync-full-leaf.cc b/nsync/src/sync-full-leaf.cc
new file mode 100644
index 0000000..84f96e3
--- /dev/null
+++ b/nsync/src/sync-full-leaf.cc
@@ -0,0 +1,52 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-full-leaf.h"
+#include <boost/ref.hpp>
+
+using namespace boost;
+
+namespace Sync {
+
+FullLeaf::FullLeaf (NameInfoConstPtr info, const SeqNo &seq)
+  : Leaf (info, seq)
+{
+  updateDigest ();
+}
+
+void
+FullLeaf::updateDigest ()
+{
+  m_digest.reset ();
+  m_digest << getInfo ()->getDigest () << *getSeq ().getDigest ();
+  m_digest.finalize ();
+}
+
+// from Leaf
+void
+FullLeaf::setSeq (const SeqNo &seq)
+{
+  Leaf::setSeq (seq);
+  updateDigest ();
+}
+
+} // Sync
diff --git a/nsync/src/sync-full-leaf.h b/nsync/src/sync-full-leaf.h
new file mode 100644
index 0000000..08142a6
--- /dev/null
+++ b/nsync/src/sync-full-leaf.h
@@ -0,0 +1,71 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_FULL_LEAF_H
+#define SYNC_FULL_LEAF_H
+
+#include "sync-leaf.h"
+
+namespace Sync {
+
+/**
+ * @ingroup sync
+ * @brief SYNC leaf for the full state (with support of Digest calculation) 
+ */
+class FullLeaf : public Leaf
+{
+public:
+  /**
+   * @brief Constructor to create an UPDATE diff leaf
+   * @param info Smart pointer to leaf's name
+   * @param seq  Initial sequence number of the pointer
+   */
+  FullLeaf (NameInfoConstPtr info, const SeqNo &seq);
+  virtual ~FullLeaf () { }
+
+  /**
+   * @brief Get hash digest of the leaf
+   *
+   * The underlying Digest object is recalculated on every update or removal
+   * (including updates of child classes)
+   */
+  const Digest &
+  getDigest () const { return m_digest; }  
+
+  // from Leaf
+  virtual void
+  setSeq (const SeqNo &seq);
+  
+private:
+  void
+  updateDigest ();
+
+private:
+  Digest m_digest;
+};
+
+typedef boost::shared_ptr<FullLeaf> FullLeafPtr;
+typedef boost::shared_ptr<const FullLeaf> FullLeafConstPtr;
+
+} // Sync
+
+#endif // SYNC_FULL_LEAF_H
diff --git a/nsync/src/sync-full-state.cc b/nsync/src/sync-full-state.cc
new file mode 100644
index 0000000..eb9ca4c
--- /dev/null
+++ b/nsync/src/sync-full-state.cc
@@ -0,0 +1,126 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-full-state.h"
+
+#include <boost/make_shared.hpp>
+#include <boost/lambda/lambda.hpp>
+#include <boost/lambda/bind.hpp>
+#include <boost/foreach.hpp>
+#include <boost/assert.hpp>
+
+#include "sync-full-leaf.h"
+
+using namespace boost;
+namespace ll = boost::lambda;
+
+namespace Sync {
+
+
+FullState::FullState ()
+// m_lastUpdated is initialized to "not_a_date_time" in normal lib mode and to "0" time in NS-3 mode
+{
+}
+
+FullState::~FullState ()
+{
+}
+
+ndn::time::Duration
+FullState::getTimeFromLastUpdate () const
+{
+  return ndn::time::now() - m_lastUpdated;
+}
+
+DigestConstPtr
+FullState::getDigest ()
+{
+  if (!m_digest)
+    {
+      m_digest = make_shared<Digest> ();
+      if (m_leaves.get<ordered> ().size () > 0)
+        {
+          BOOST_FOREACH (LeafConstPtr leaf, m_leaves.get<ordered> ())
+            {
+              FullLeafConstPtr fullLeaf = dynamic_pointer_cast<const FullLeaf> (leaf);
+              BOOST_ASSERT (fullLeaf != 0);
+              *m_digest << fullLeaf->getDigest ();
+            }
+          m_digest->finalize ();
+        }
+      else
+        {
+          std::istringstream is ("00"); //zero state
+          is >> *m_digest;
+        }
+    }
+
+  return m_digest;
+}
+
+// from State
+boost::tuple<bool/*inserted*/, bool/*updated*/, SeqNo/*oldSeqNo*/>
+FullState::update (NameInfoConstPtr info, const SeqNo &seq)
+{
+  m_lastUpdated = ndn::time::now();
+
+
+  m_digest.reset ();
+
+  LeafContainer::iterator item = m_leaves.find (info);
+  if (item == m_leaves.end ())
+    {
+      m_leaves.insert (make_shared<FullLeaf> (info, cref (seq)));
+      return make_tuple (true, false, SeqNo ());
+    }
+  else
+    {
+      if ((*item)->getSeq () == seq || seq < (*item)->getSeq ())
+        {
+          return make_tuple (false, false, SeqNo ());
+        }
+
+      SeqNo old = (*item)->getSeq ();
+      m_leaves.modify (item,
+                       ll::bind (&Leaf::setSeq, *ll::_1, seq));
+      return make_tuple (false, true, old);
+    }
+}
+
+bool
+FullState::remove (NameInfoConstPtr info)
+{
+  m_lastUpdated = ndn::time::now();
+
+  m_digest.reset ();
+
+  LeafContainer::iterator item = m_leaves.find (info);
+  if (item != m_leaves.end ())
+    {
+      m_leaves.erase (item);
+      return true;
+    }
+  else
+    return false;
+}
+
+} // Sync
diff --git a/nsync/src/sync-full-state.h b/nsync/src/sync-full-state.h
new file mode 100644
index 0000000..28e0078
--- /dev/null
+++ b/nsync/src/sync-full-state.h
@@ -0,0 +1,79 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_FULL_STATE_H
+#define SYNC_FULL_STATE_H
+
+#include <ndn-cpp-dev/util/time.hpp>
+#include "sync-state.h"
+
+namespace Sync {
+
+class FullState;
+typedef boost::shared_ptr<FullState> FullStatePtr;
+typedef boost::shared_ptr<FullState> FullStateConstPtr;
+
+
+/**
+ * \ingroup sync
+ * @brief Cumulative SYNC state
+ */
+class FullState : public State
+{
+public:
+  /**
+   * @brief Default constructor
+   */
+  FullState ();
+  virtual ~FullState ();
+
+  /**
+   * @brief Get time period since last state update
+   *
+   * This value can be used to randomize reconciliation waiting time in SyncApp
+   */
+  ndn::time::Duration
+  getTimeFromLastUpdate () const;
+
+  /**
+   * @brief Obtain a read-only copy of the digest
+   *
+   * If m_digest is 0, then it is automatically created.  On every update and removal, m_digest is reset to 0
+   */
+  DigestConstPtr
+  getDigest ();
+  
+  // from State
+  virtual boost::tuple<bool/*inserted*/, bool/*updated*/, SeqNo/*oldSeqNo*/>
+  update (NameInfoConstPtr info, const SeqNo &seq);
+
+  virtual bool
+  remove (NameInfoConstPtr info);
+  
+private:
+  ndn::time::Point m_lastUpdated; ///< @brief Time when state was updated last time
+  DigestPtr m_digest;
+};
+
+} // Sync
+
+#endif // SYNC_STATE_H
diff --git a/nsync/src/sync-interest-container.h b/nsync/src/sync-interest-container.h
new file mode 100644
index 0000000..742f053
--- /dev/null
+++ b/nsync/src/sync-interest-container.h
@@ -0,0 +1,99 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_INTEREST_CONTAINER_H
+#define SYNC_INTEREST_CONTAINER_H
+
+#include <ndn-cpp-dev/util/time.hpp>
+
+#include "sync-digest.h"
+
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/tag.hpp>
+// #include <boost/multi_index/ordered_index.hpp>
+// #include <boost/multi_index/composite_key.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/sequenced_index.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+// #include <boost/multi_index/random_access_index.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+
+namespace mi = boost::multi_index;
+
+namespace Sync {
+
+struct Interest
+{
+  Interest (DigestConstPtr digest, const std::string &name, bool unknown=false)
+  : m_digest (digest)
+  , m_name (name)
+  , m_time (ndn::time::now())
+  , m_unknown (unknown)
+  {
+  }
+  
+  DigestConstPtr   m_digest;
+  std::string      m_name;
+  ndn::time::Point m_time;
+  bool             m_unknown;
+};
+
+/// @cond include_hidden 
+struct named { };
+struct hashed;
+struct timed;
+/// @endcond
+
+/**
+ * \ingroup sync
+ * @brief Container for interests (application PIT)
+ */
+struct InterestContainer : public mi::multi_index_container<
+  Interest,
+  mi::indexed_by<
+    mi::hashed_unique<
+      mi::tag<named>,
+      BOOST_MULTI_INDEX_MEMBER(Interest, std::string, m_name)
+    >
+    ,
+    
+    mi::hashed_non_unique<
+      mi::tag<hashed>,
+      BOOST_MULTI_INDEX_MEMBER(Interest, DigestConstPtr, m_digest),
+      DigestPtrHash,
+      DigestPtrEqual
+      >
+    ,
+    
+    mi::ordered_non_unique<
+      mi::tag<timed>,
+      BOOST_MULTI_INDEX_MEMBER(Interest, ndn::time::Point, m_time)
+      >
+    >
+  >
+{
+};
+
+} // Sync
+
+#endif // SYNC_INTEREST_CONTAINER_H
diff --git a/nsync/src/sync-interest-table.cc b/nsync/src/sync-interest-table.cc
new file mode 100644
index 0000000..a378950
--- /dev/null
+++ b/nsync/src/sync-interest-table.cc
@@ -0,0 +1,123 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-interest-table.h"
+#include "sync-logging.h"
+using namespace std;
+
+INIT_LOGGER ("SyncInterestTable");
+
+namespace Sync
+{
+
+SyncInterestTable::SyncInterestTable (boost::asio::io_service& io, ndn::time::Duration lifetime)
+  : m_entryLifetime (lifetime)
+  , m_scheduler(io)
+{
+  m_scheduler.schedulePeriodicEvent (ndn::time::seconds (4), ndn::time::seconds (4),
+                                     ndn::bind(&SyncInterestTable::expireInterests, this));
+}
+
+SyncInterestTable::~SyncInterestTable ()
+{
+}
+
+Interest
+SyncInterestTable::pop ()
+{
+  if (m_table.size () == 0)
+    BOOST_THROW_EXCEPTION (Error::InterestTableIsEmpty ());
+
+  Interest ret = *m_table.begin ();
+  m_table.erase (m_table.begin ());
+
+  return ret;
+}
+
+bool
+SyncInterestTable::insert (DigestConstPtr digest, const string &name, bool unknownState/*=false*/)
+{
+  bool existent = false;
+  
+  InterestContainer::index<named>::type::iterator it = m_table.get<named> ().find (name);
+  if (it != m_table.end())
+    {
+      existent = true;
+      m_table.erase (it);
+    }
+  m_table.insert (Interest (digest, name, unknownState));
+
+  return existent;
+}
+
+uint32_t
+SyncInterestTable::size () const
+{
+  return m_table.size ();
+}
+
+bool
+SyncInterestTable::remove (const string &name)
+{
+  InterestContainer::index<named>::type::iterator item = m_table.get<named> ().find (name);
+  if (item != m_table.get<named> ().end ())
+    {
+      m_table.get<named> ().erase (name);
+      return true;
+    }
+
+  return false;
+}
+
+bool
+SyncInterestTable::remove (DigestConstPtr digest)
+{
+  InterestContainer::index<hashed>::type::iterator item = m_table.get<hashed> ().find (digest);
+  if (item != m_table.get<hashed> ().end ())
+    {
+      m_table.get<hashed> ().erase (digest); // erase all records associated with the digest
+      return true;
+    }
+  return false;
+}
+
+void SyncInterestTable::expireInterests ()
+{ 
+  uint32_t count = 0;
+  ndn::time::Point expireTime = ndn::time::now() - m_entryLifetime;
+  
+  while (m_table.size () > 0)
+    {
+      InterestContainer::index<timed>::type::iterator item = m_table.get<timed> ().begin ();
+      
+      if (item->m_time <= expireTime)
+        {
+          m_table.get<timed> ().erase (item);
+          count ++;
+        }
+      else
+        break;
+  }
+}
+
+
+}
diff --git a/nsync/src/sync-interest-table.h b/nsync/src/sync-interest-table.h
new file mode 100644
index 0000000..9b7c46b
--- /dev/null
+++ b/nsync/src/sync-interest-table.h
@@ -0,0 +1,96 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_INTEREST_TABLE_H
+#define SYNC_INTEREST_TABLE_H
+
+#include <ndn-cpp-dev/util/scheduler.hpp>
+
+#include <string>
+#include <vector>
+
+#include "sync-digest.h"
+#include "sync-interest-container.h"
+
+namespace Sync {
+
+/**
+ * \ingroup sync
+ * @brief A table to keep unanswered Sync Interest
+ * all access operation to the table should grab the 
+ * mutex first
+ */
+class SyncInterestTable
+{
+public:
+  SyncInterestTable (boost::asio::io_service& io, ndn::time::Duration lifetime);
+  ~SyncInterestTable ();
+
+  /**
+   * @brief Insert an interest, if interest already exists, update the
+   * timestamp
+   */
+  bool
+  insert (DigestConstPtr interest, const std::string &name, bool unknownState=false);
+
+  /**
+   * @brief Remove interest by digest (e.g., when it was satisfied)
+   */
+  bool
+  remove (DigestConstPtr interest);
+
+  /**
+   * @brief Remove interest by name (e.g., when it was satisfied)
+   */
+  bool
+  remove (const std::string &name);
+  
+  /**
+   * @brief pop a non-expired Interest from PIT
+   */
+  Interest
+  pop ();
+
+  uint32_t
+  size () const;
+
+private:
+  /**
+   * @brief periodically called to expire Interest
+   */
+  void
+  expireInterests ();
+
+private:
+  ndn::time::Duration m_entryLifetime;
+  InterestContainer m_table;
+
+  ndn::Scheduler m_scheduler;
+};
+
+namespace Error {
+struct InterestTableIsEmpty : virtual boost::exception, virtual std::exception { };
+}
+
+} // Sync
+
+#endif // SYNC_INTEREST_TABLE_H
diff --git a/nsync/src/sync-leaf.cc b/nsync/src/sync-leaf.cc
new file mode 100644
index 0000000..03e2217
--- /dev/null
+++ b/nsync/src/sync-leaf.cc
@@ -0,0 +1,43 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-leaf.h"
+
+namespace Sync {
+
+Leaf::Leaf (NameInfoConstPtr info, const SeqNo &seq)
+  : m_info (info)
+  , m_seq (seq)
+{
+}
+
+Leaf::~Leaf ()
+{
+}
+
+void
+Leaf::setSeq (const SeqNo &seq)
+{
+  m_seq = std::max (m_seq, seq);
+}
+
+} // Sync
diff --git a/nsync/src/sync-leaf.h b/nsync/src/sync-leaf.h
new file mode 100644
index 0000000..345be46
--- /dev/null
+++ b/nsync/src/sync-leaf.h
@@ -0,0 +1,84 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_LEAF_H
+#define SYNC_LEAF_H
+
+#include "sync-seq-no.h"
+#include "sync-name-info.h"
+
+namespace Sync {
+
+/**
+ * \ingroup sync
+ * @brief Sync tree leaf
+ */
+class Leaf
+{
+public:
+  /**
+   * @brief Constructor
+   * @param info Smart pointer to leaf's name
+   * @param seq  Initial sequence number of the pointer
+   */
+  Leaf (NameInfoConstPtr info, const SeqNo &seq);
+  virtual ~Leaf ();
+  
+  /**
+   * @brief Get name of the leaf
+   */
+  NameInfoConstPtr
+  getInfo () const { return m_info; }
+
+  /**
+   * @brief Get sequence number of the leaf
+   */
+  const SeqNo&
+  getSeq () const { return m_seq; }
+
+  /**
+   * @brief Update sequence number of the leaf
+   * @param seq Sequence number
+   *
+   * Sequence number is updated to the largest value among this->m_seq and seq
+   */
+  virtual void
+  setSeq (const SeqNo &seq);
+  
+private:
+  NameInfoConstPtr m_info;
+  SeqNo m_seq;
+};
+
+typedef boost::shared_ptr<Leaf> LeafPtr;
+typedef boost::shared_ptr<const Leaf> LeafConstPtr;
+
+inline std::ostream &
+operator << (std::ostream &os, const Leaf &leaf)
+{
+  os << *leaf.getInfo () << "(" << leaf.getSeq () << ")";
+  return os;
+}
+
+} // Sync
+
+#endif // SYNC_LEAF_H
diff --git a/nsync/src/sync-logging.cc b/nsync/src/sync-logging.cc
new file mode 100644
index 0000000..9048964
--- /dev/null
+++ b/nsync/src/sync-logging.cc
@@ -0,0 +1,61 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-logging.h"
+
+#ifdef HAVE_LOG4CXX
+
+#include <log4cxx/logger.h>
+#include <log4cxx/basicconfigurator.h>
+#include <log4cxx/consoleappender.h>
+#include <log4cxx/patternlayout.h>
+#include <log4cxx/level.h>
+#include <log4cxx/propertyconfigurator.h>
+#include <log4cxx/defaultconfigurator.h>
+#include <log4cxx/helpers/exception.h>
+using namespace log4cxx;
+using namespace log4cxx::helpers;
+
+#include <unistd.h>
+
+void
+INIT_LOGGERS ()
+{
+  static bool configured = false;
+
+  if (configured) return;
+  
+  if (access ("log4cxx.properties", R_OK)==0)
+    PropertyConfigurator::configureAndWatch ("log4cxx.properties");
+  else
+    {
+      PatternLayoutPtr   layout   (new PatternLayout ("%d{HH:mm:ss} %p %c{1} - %m%n"));
+      ConsoleAppenderPtr appender (new ConsoleAppender (layout));
+
+      BasicConfigurator::configure( appender );
+      Logger::getRootLogger()->setLevel (log4cxx::Level::getInfo ());
+    }
+
+  configured = true;
+}
+
+#endif
diff --git a/nsync/src/sync-logging.h b/nsync/src/sync-logging.h
new file mode 100644
index 0000000..865204a
--- /dev/null
+++ b/nsync/src/sync-logging.h
@@ -0,0 +1,74 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_LOG_H
+#define SYNC_LOG_H
+
+#ifdef HAVE_LOG4CXX
+
+#include <log4cxx/logger.h>
+
+#define INIT_LOGGER(name) \
+  static log4cxx::LoggerPtr staticModuleLogger = log4cxx::Logger::getLogger (name);
+
+#define _LOG_DEBUG(x) \
+  LOG4CXX_DEBUG(staticModuleLogger, x);
+
+#define _LOG_TRACE(x) \
+  LOG4CXX_TRACE(staticModuleLogger, x);
+
+#define _LOG_FUNCTION(x) \
+  LOG4CXX_TRACE(staticModuleLogger, __FUNCTION__ << "(" << x << ")");
+
+#define _LOG_FUNCTION_NOARGS \
+  LOG4CXX_TRACE(staticModuleLogger, __FUNCTION__ << "()");
+
+#define _LOG_ERROR(x) \
+  LOG4CXX_ERROR(staticModuleLogger, x);
+
+void
+INIT_LOGGERS ();
+
+#else
+
+#define INIT_LOGGER(name)
+#define _LOG_FUNCTION(x)
+#define _LOG_FUNCTION_NOARGS
+#define _LOG_TRACE(x)
+#define INIT_LOGGERS(x)
+#define _LOG_ERROR(x)
+
+#ifdef _DEBUG
+
+#include <boost/date_time/posix_time/posix_time.hpp>
+#include <iostream>
+
+#define _LOG_DEBUG(x) \
+  std::clog << boost::get_system_time () << " " << boost::this_thread::get_id () << " " << x << endl;
+
+#else
+#define _LOG_DEBUG(x)
+#endif
+
+#endif // HAVE_LOG4CXX
+
+#endif // SYNC_LOG_H
diff --git a/nsync/src/sync-logic-event-container.h b/nsync/src/sync-logic-event-container.h
new file mode 100644
index 0000000..ebab72a
--- /dev/null
+++ b/nsync/src/sync-logic-event-container.h
@@ -0,0 +1,85 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_LOGIC_EVENT_CONTAINER_H
+#define SYNC_LOGIC_EVENT_CONTAINER_H
+
+#include "sync-event.h"
+
+#include <boost/function.hpp>
+#include <boost/date_time/posix_time/posix_time_types.hpp>
+
+#include <boost/multi_index_container.hpp>
+// #include <boost/multi_index/tag.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+// #include <boost/multi_index/composite_key.hpp>
+// #include <boost/multi_index/hashed_index.hpp>
+// #include <boost/multi_index/random_access_index.hpp>
+#include <boost/multi_index/member.hpp>
+// #include <boost/multi_index/mem_fun.hpp>
+
+namespace mi = boost::multi_index;
+
+namespace Sync
+{
+
+struct LogicEvent
+{
+  LogicEvent (const boost::system_time &_time, Event _event, uint32_t _label)
+    : time (_time)
+    , event (_event)
+    , lbl (_label)
+  { }
+  
+  boost::system_time time;
+  Event event;
+  uint32_t lbl;
+};
+
+/// @cond include_hidden
+struct byLabel { } ;
+/// @endcond
+
+/**
+ * \ingroup sync
+ * @brief ???
+ */
+struct EventsContainer : public mi::multi_index_container<
+  LogicEvent,
+  mi::indexed_by<
+
+    mi::ordered_non_unique<
+      mi::member<LogicEvent, boost::system_time, &LogicEvent::time>
+      >,
+
+    mi::ordered_non_unique<
+      mi::tag<byLabel>,
+      mi::member<LogicEvent, uint32_t, &LogicEvent::lbl>
+      >
+    >
+  >
+{
+};
+
+} // Sync
+
+#endif // SYNC_LOGIC_EVENT_CONTAINER_H
diff --git a/nsync/src/sync-logic.cc b/nsync/src/sync-logic.cc
new file mode 100644
index 0000000..ec4d63e
--- /dev/null
+++ b/nsync/src/sync-logic.cc
@@ -0,0 +1,705 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ *         Yingdi Yu <yingdi@cs.ucla.edu>
+ */
+
+#include "sync-logic.h"
+#include "sync-diff-leaf.h"
+#include "sync-full-leaf.h"
+#include "sync-logging.h"
+#include "sync-state.h"
+
+#include <boost/foreach.hpp>
+#include <boost/lexical_cast.hpp>
+#include <vector>
+
+using namespace std;
+using namespace ndn;
+
+INIT_LOGGER ("SyncLogic");
+
+
+#ifdef _DEBUG
+#define _LOG_DEBUG_ID(v) _LOG_DEBUG(m_instanceId << " " << v)
+#else
+#define _LOG_DEBUG_ID(v) _LOG_DEBUG(v)
+#endif
+
+#define GET_RANDOM(var) var ()
+
+#define TIME_SECONDS_WITH_JITTER(sec) \
+  (time::seconds(sec) + time::milliseconds(GET_RANDOM (m_reexpressionJitter)))
+
+#define TIME_MILLISECONDS_WITH_JITTER(ms) \
+  (time::seconds(ms) + time::milliseconds(GET_RANDOM (m_reexpressionJitter)))
+
+namespace Sync {
+
+using ndn::shared_ptr;
+
+int SyncLogic::m_instanceCounter = 0;
+
+SyncLogic::SyncLogic (const Name& syncPrefix,
+                      shared_ptr<Validator> validator, 
+                      shared_ptr<Face> face,
+                      LogicUpdateCallback onUpdate,
+                      LogicRemoveCallback onRemove)
+  : m_state (new FullState)
+  , m_syncInterestTable (*face->ioService(), time::seconds(m_syncInterestReexpress))
+  , m_syncPrefix (syncPrefix)
+  , m_onUpdate (onUpdate)
+  , m_onRemove (onRemove)
+  , m_perBranch (false)
+  , m_validator(validator)
+  , m_keyChain(new KeyChain())
+  , m_face(face)
+  , m_scheduler(*face->ioService())
+  , m_randomGenerator (static_cast<unsigned int> (std::time (0)))
+  , m_rangeUniformRandom (m_randomGenerator, boost::uniform_int<> (200,1000))
+  , m_reexpressionJitter (m_randomGenerator, boost::uniform_int<> (100,500))
+  , m_recoveryRetransmissionInterval (m_defaultRecoveryRetransmitInterval)
+{ 
+  m_syncRegisteredPrefixId = m_face->setInterestFilter (m_syncPrefix, 
+                                                        bind(&SyncLogic::onSyncInterest, this, _1, _2), 
+                                                        bind(&SyncLogic::onSyncRegisterFailed, this, _1, _2));
+  
+
+  m_reexpressingInterestId = m_scheduler.scheduleEvent (time::seconds (0), // no need to add jitter
+                                                        bind (&SyncLogic::sendSyncInterest, this));
+
+  m_instanceId = string("Instance " + boost::lexical_cast<string>(m_instanceCounter++) + " ");
+}
+
+SyncLogic::SyncLogic (const Name& syncPrefix,
+                      shared_ptr<Validator> validator,
+                      shared_ptr<Face> face,
+                      LogicPerBranchCallback onUpdateBranch)
+  : m_state (new FullState)
+  , m_syncInterestTable (*face->ioService(), time::seconds (m_syncInterestReexpress))
+  , m_syncPrefix (syncPrefix)
+  , m_onUpdateBranch (onUpdateBranch)
+  , m_perBranch(true)
+  , m_validator(validator)
+  , m_keyChain(new KeyChain())
+  , m_face(face)
+  , m_scheduler(*face->ioService())
+  , m_randomGenerator (static_cast<unsigned int> (std::time (0)))
+  , m_rangeUniformRandom (m_randomGenerator, boost::uniform_int<> (200,1000))
+  , m_reexpressionJitter (m_randomGenerator, boost::uniform_int<> (100,500))
+  , m_recoveryRetransmissionInterval (m_defaultRecoveryRetransmitInterval)
+{ 
+  m_syncRegisteredPrefixId = m_face->setInterestFilter (m_syncPrefix, 
+                                                        bind(&SyncLogic::onSyncInterest, this, _1, _2), 
+                                                        bind(&SyncLogic::onSyncRegisterFailed, this, _1, _2));
+
+  m_reexpressingInterestId = m_scheduler.scheduleEvent (time::seconds (0), // no need to add jitter
+                                                        bind (&SyncLogic::sendSyncInterest, this));
+}
+
+SyncLogic::~SyncLogic ()
+{ 
+  m_face->unsetInterestFilter(m_syncRegisteredPrefixId); 
+  m_scheduler.cancelEvent (m_reexpressingInterestId);
+  m_scheduler.cancelEvent (m_delayedInterestProcessingId);
+}
+
+/**
+ * Two types of intersts
+ *
+ * Normal name:    .../<hash>  
+ * Recovery name:  .../recovery/<hash>
+ */
+boost::tuple<DigestConstPtr, std::string>
+SyncLogic::convertNameToDigestAndType (const Name &name)
+{
+  BOOST_ASSERT (m_syncPrefix.isPrefixOf(name));
+
+  int nameLengthDiff = name.size() - m_syncPrefix.size();
+  BOOST_ASSERT (nameLengthDiff > 0);
+  BOOST_ASSERT (nameLengthDiff < 3);
+  
+  string hash = name.get(-1).toEscapedString();
+  string interestType;
+  
+  if(nameLengthDiff == 1)
+    interestType = "normal";
+  else
+    interestType = name.get(-2).toEscapedString();
+
+  _LOG_DEBUG_ID (hash << ", " << interestType);
+
+  DigestPtr digest = boost::make_shared<Digest> ();
+  istringstream is (hash);
+  is >> *digest;
+
+  return make_tuple (digest, interestType);
+}
+
+void
+SyncLogic::onSyncInterest (const Name& prefix, const ndn::Interest& interest)
+{
+  Name name = interest.getName();
+
+  _LOG_DEBUG_ID("respondSyncInterest: " << name);
+
+  try
+    {
+      _LOG_DEBUG_ID ("<< I " << name);
+
+      DigestConstPtr digest;
+      string type;
+      tie (digest, type) = convertNameToDigestAndType (name);
+
+      if (type == "normal") // kind of ineffective...
+        {
+          processSyncInterest (name, digest);
+        }
+      else if (type == "recovery") 
+        {
+          processSyncRecoveryInterest (name, digest);
+        }
+    }
+  catch (Error::DigestCalculationError &e)
+    {
+      _LOG_DEBUG_ID ("Something fishy happened...");
+      // log error. ignoring it for now, later we should log it
+      return ;
+    }
+}
+
+void
+SyncLogic::onSyncRegisterFailed(const Name& prefix, const string& msg)
+{
+  _LOG_DEBUG_ID("Sync prefix registration failed! " << msg);
+}
+
+void
+SyncLogic::onSyncData(const ndn::Interest& interest, Data& data)
+{
+  OnDataValidated onValidated = bind(&SyncLogic::onSyncDataValidated, this, _1);
+  OnDataValidationFailed onValidationFailed = bind(&SyncLogic::onSyncDataValidationFailed, this, _1);
+  m_validator->validate(data, onValidated, onValidationFailed); 
+}
+
+void
+SyncLogic::onSyncTimeout(const ndn::Interest& interest)
+{ 
+  // It is OK. Others will handle the time out situation. 
+}
+
+void
+SyncLogic::onSyncDataValidationFailed(const shared_ptr<const Data>& data)
+{
+  _LOG_DEBUG_ID("Sync data cannot be verified!");
+}
+
+void
+SyncLogic::onSyncDataValidated(const shared_ptr<const Data>& data)
+{
+  Name name = data->getName();
+  const char* wireData = (const char*)data->getContent().value();
+  size_t len = data->getContent().value_size();
+
+  try
+    {
+      _LOG_DEBUG_ID ("<< D " << name);
+  
+      DigestConstPtr digest;
+      string type;
+      tie (digest, type) = convertNameToDigestAndType (name);
+
+      if (type == "normal")
+        {
+          processSyncData (name, digest, wireData, len);
+        }
+      else
+        {
+          // timer is always restarted when we schedule recovery
+          m_scheduler.cancelEvent (m_reexpressingRecoveryInterestId);
+          processSyncData (name, digest, wireData, len);
+        }
+    }
+  catch (Error::DigestCalculationError &e)
+    {
+      _LOG_DEBUG_ID ("Something fishy happened...");
+      // log error. ignoring it for now, later we should log it
+      return;
+    }
+}
+
+void
+SyncLogic::processSyncInterest (const Name &name, DigestConstPtr digest, bool timedProcessing/*=false*/)
+{
+  _LOG_DEBUG_ID("processSyncInterest");
+  DigestConstPtr rootDigest;
+  {
+    rootDigest = m_state->getDigest();
+  }
+
+  // Special case when state is not empty and we have received request with zero-root digest
+  if (digest->isZero () && !rootDigest->isZero ())
+    {
+      
+      SyncStateMsg ssm;
+      {
+        ssm << (*m_state);
+      }
+      sendSyncData (name, digest, ssm);
+      return;
+    }
+
+  if (*rootDigest == *digest)
+    {
+      _LOG_DEBUG_ID ("processSyncInterest (): Same state. Adding to PIT");
+      m_syncInterestTable.insert (digest, name.toUri(), false);
+      return;
+    }
+  
+  DiffStateContainer::iterator stateInDiffLog = m_log.find (digest);
+
+  if (stateInDiffLog != m_log.end ())
+  {
+    DiffStateConstPtr stateDiff = (*stateInDiffLog)->diff ();
+
+    sendSyncData (name, digest, stateDiff);
+    return;
+  }
+
+  if (!timedProcessing)
+    {
+      bool exists = m_syncInterestTable.insert (digest, name.toUri(), true);
+      if (exists) // somebody else replied, so restart random-game timer
+        {
+          _LOG_DEBUG_ID ("Unknown digest, but somebody may have already replied, so restart our timer");
+          m_scheduler.cancelEvent (m_delayedInterestProcessingId);
+        }
+
+      uint32_t waitDelay = GET_RANDOM (m_rangeUniformRandom);      
+      _LOG_DEBUG_ID ("Digest is not in the log. Schedule processing after small delay: " << time::milliseconds (waitDelay));
+
+      m_delayedInterestProcessingId = m_scheduler.scheduleEvent (time::milliseconds (waitDelay),
+                                                                 bind (&SyncLogic::processSyncInterest, this, name, digest, true));
+    }
+  else
+    {
+      _LOG_DEBUG_ID ("                                                      (timed processing)");
+      
+      m_recoveryRetransmissionInterval = m_defaultRecoveryRetransmitInterval;
+      sendSyncRecoveryInterests (digest);
+    }
+}
+
+void
+SyncLogic::processSyncData (const Name &name, DigestConstPtr digest, const char *wireData, size_t len)
+{
+  DiffStatePtr diffLog = boost::make_shared<DiffState> ();
+  bool ownInterestSatisfied = false;
+  
+  try
+    {
+
+      m_syncInterestTable.remove (name.toUri()); // Remove satisfied interest from PIT
+
+      ownInterestSatisfied = (name == m_outstandingInterestName);
+
+      DiffState diff;
+      SyncStateMsg msg;
+      if (!msg.ParseFromArray(wireData, len) || !msg.IsInitialized()) 
+      {
+        //Throw
+        BOOST_THROW_EXCEPTION (Error::SyncStateMsgDecodingFailure () );
+      }
+      msg >> diff;
+
+      vector<MissingDataInfo> v;
+      BOOST_FOREACH (LeafConstPtr leaf, diff.getLeaves().get<ordered>())
+        {
+          DiffLeafConstPtr diffLeaf = boost::dynamic_pointer_cast<const DiffLeaf> (leaf);
+          BOOST_ASSERT (diffLeaf != 0);
+
+          NameInfoConstPtr info = diffLeaf->getInfo();
+          if (diffLeaf->getOperation() == UPDATE)
+            {
+              SeqNo seq = diffLeaf->getSeq();
+
+              bool inserted = false;
+              bool updated = false;
+              SeqNo oldSeq;
+              {
+                boost::tie (inserted, updated, oldSeq) = m_state->update (info, seq);
+              }
+
+              if (inserted || updated)
+                {
+                  diffLog->update (info, seq);
+                  if (!oldSeq.isValid())
+                  {
+                    oldSeq = SeqNo(seq.getSession(), 0);
+                  }
+                  else
+                  {
+                    ++oldSeq;
+                  }
+                  // there is no need for application to process update on forwarder node
+                  if (info->toString() != forwarderPrefix)
+                  {
+                    MissingDataInfo mdi = {info->toString(), oldSeq, seq};
+                    {
+                      ostringstream interestName;
+                      interestName << mdi.prefix << "/" << mdi.high.getSession() << "/" << mdi.high.getSeq();
+                      _LOG_DEBUG_ID("+++++++++++++++ " + interestName.str());
+                    }
+                    if (m_perBranch)
+                    {
+                       ostringstream interestName;
+                       interestName << mdi.prefix << "/" << mdi.high.getSession() << "/" << mdi.high.getSeq();
+                       m_onUpdateBranch(interestName.str());
+                    }
+                    else
+                    {
+                      v.push_back(mdi);
+                    }
+                  }
+                }
+            }
+          else if (diffLeaf->getOperation() == REMOVE)
+            {
+              if (m_state->remove (info))
+                {
+                  diffLog->remove (info);
+                  if (!m_perBranch)
+                  {
+                    m_onRemove (info->toString ());
+                  }
+                }
+            }
+          else
+            {
+            }
+        }
+
+      if (!v.empty()) 
+      {
+        if (!m_perBranch)
+        {
+           m_onUpdate(v);
+        }
+      }
+
+      insertToDiffLog (diffLog);
+    }
+  catch (Error::SyncStateMsgDecodingFailure &e)
+    {
+      _LOG_DEBUG_ID ("Something really fishy happened during state decoding " <<
+                  diagnostic_information (e));
+      diffLog.reset ();
+      // don't do anything
+    }
+
+  if ((diffLog != 0 && diffLog->getLeaves ().size () > 0) ||
+      ownInterestSatisfied)
+    {
+      _LOG_DEBUG_ID(" +++++++++++++++ state changed!!!");
+      // Do it only if everything went fine and state changed
+
+      // this is kind of wrong
+      // satisfyPendingSyncInterests (diffLog); // if there are interests in PIT, there is a point to satisfy them using new state
+  
+      // if state has changed, then it is safe to express a new interest
+      time::Duration after = time::milliseconds(GET_RANDOM (m_reexpressionJitter));
+      // cout << "------------ reexpress interest after: " << after << endl;
+      EventId eventId = m_scheduler.scheduleEvent (after,
+                                                   bind (&SyncLogic::sendSyncInterest, this));
+
+      m_scheduler.cancelEvent (m_reexpressingInterestId);
+      m_reexpressingInterestId = eventId;
+    }
+}
+
+void
+SyncLogic::processSyncRecoveryInterest (const Name &name, DigestConstPtr digest)
+{
+  _LOG_DEBUG_ID("processSyncRecoveryInterest");
+  DiffStateContainer::iterator stateInDiffLog = m_log.find (digest);
+
+  if (stateInDiffLog == m_log.end ())
+    {
+      _LOG_DEBUG_ID ("Could not find " << *digest << " in digest log");
+      return;
+    }
+
+  SyncStateMsg ssm;
+  {
+    ssm << (*m_state);
+  }
+  sendSyncData (name, digest, ssm);
+}
+
+void
+SyncLogic::satisfyPendingSyncInterests (DiffStateConstPtr diffLog)
+{
+  DiffStatePtr fullStateLog = boost::make_shared<DiffState> ();
+  {
+    BOOST_FOREACH (LeafConstPtr leaf, m_state->getLeaves ()/*.get<timed> ()*/)
+      {
+        fullStateLog->update (leaf->getInfo (), leaf->getSeq ());
+        /// @todo Impose limit on how many state info should be send out
+      }
+  }
+  
+  try
+    {
+      uint32_t counter = 0;
+      while (m_syncInterestTable.size () > 0)
+        {
+          Sync::Interest interest = m_syncInterestTable.pop ();
+
+          if (!interest.m_unknown)
+            {
+              _LOG_DEBUG_ID (">> D " << interest.m_name);
+              sendSyncData (interest.m_name, interest.m_digest, diffLog);
+            }
+          else
+            {
+              _LOG_DEBUG_ID (">> D (unknown)" << interest.m_name);
+              sendSyncData (interest.m_name, interest.m_digest, fullStateLog);
+            }
+          counter ++;
+        }
+      _LOG_DEBUG_ID ("Satisfied " << counter << " pending interests");
+    }
+  catch (Error::InterestTableIsEmpty &e)
+    {
+      // ok. not really an error
+    }
+}
+
+void
+SyncLogic::insertToDiffLog (DiffStatePtr diffLog) 
+{
+  diffLog->setDigest (m_state->getDigest());  
+  if (m_log.size () > 0)
+    {
+      m_log.get<sequenced> ().front ()->setNext (diffLog);
+    }
+  m_log.erase (m_state->getDigest()); // remove diff state with the same digest.  next pointers are still valid
+  /// @todo Optimization
+  m_log.get<sequenced> ().push_front (diffLog);
+}
+
+void
+SyncLogic::addLocalNames (const Name &prefix, uint64_t session, uint64_t seq)
+{
+  DiffStatePtr diff;
+  {
+    //cout << "Add local names" <<endl;
+    NameInfoConstPtr info = StdNameInfo::FindOrCreate(prefix.toUri());
+
+    _LOG_DEBUG_ID ("addLocalNames (): old state " << *m_state->getDigest ());
+
+    SeqNo seqN (session, seq);
+    m_state->update(info, seqN);
+
+    _LOG_DEBUG_ID ("addLocalNames (): new state " << *m_state->getDigest ());
+    
+    diff = boost::make_shared<DiffState>();
+    diff->update(info, seqN);
+    insertToDiffLog (diff);
+  }
+
+  // _LOG_DEBUG_ID ("PIT size: " << m_syncInterestTable.size ());
+  satisfyPendingSyncInterests (diff);  
+}
+
+void
+SyncLogic::remove(const Name &prefix) 
+{
+  DiffStatePtr diff;
+  {
+    NameInfoConstPtr info = StdNameInfo::FindOrCreate(prefix.toUri());
+    m_state->remove(info);	
+
+    // increment the sequence number for the forwarder node
+    NameInfoConstPtr forwarderInfo = StdNameInfo::FindOrCreate(forwarderPrefix);
+
+    LeafContainer::iterator item = m_state->getLeaves ().find (forwarderInfo);
+    SeqNo seqNo (0);
+    if (item != m_state->getLeaves ().end ())
+      {
+        seqNo = (*item)->getSeq ();
+        ++seqNo;
+      }
+    m_state->update (forwarderInfo, seqNo);
+
+    diff = boost::make_shared<DiffState>();
+    diff->remove(info);
+    diff->update(forwarderInfo, seqNo);
+
+    insertToDiffLog (diff);
+  }
+
+  satisfyPendingSyncInterests (diff);  
+}
+
+void
+SyncLogic::sendSyncInterest ()
+{
+  _LOG_DEBUG_ID("sendSyncInterest");
+
+  {
+    m_outstandingInterestName = m_syncPrefix;
+    ostringstream os;
+    os << *m_state->getDigest();
+    m_outstandingInterestName.append(os.str());
+    _LOG_DEBUG_ID (">> I " << m_outstandingInterestName);
+  }
+
+  _LOG_DEBUG_ID("sendSyncInterest: " << m_outstandingInterestName);
+
+  EventId eventId = m_scheduler.scheduleEvent (time::seconds(m_syncInterestReexpress) + time::milliseconds(GET_RANDOM (m_reexpressionJitter)),
+                                               bind (&SyncLogic::sendSyncInterest, this));
+  m_scheduler.cancelEvent (m_reexpressingInterestId);
+  m_reexpressingInterestId = eventId;
+
+  ndn::Interest interest(m_outstandingInterestName);
+  interest.setMustBeFresh(true);
+
+  m_face->expressInterest(interest,
+                          bind(&SyncLogic::onSyncData, this, _1, _2),
+                          bind(&SyncLogic::onSyncTimeout, this, _1));
+}
+
+void
+SyncLogic::sendSyncRecoveryInterests (DigestConstPtr digest)
+{
+  ostringstream os;
+  os << *digest;
+  
+  Name interestName = m_syncPrefix;
+  interestName.append("recovery").append(os.str());
+
+  time::Duration nextRetransmission = time::milliseconds (m_recoveryRetransmissionInterval + GET_RANDOM (m_reexpressionJitter));
+
+  m_recoveryRetransmissionInterval <<= 1;
+    
+  m_scheduler.cancelEvent (m_reexpressingRecoveryInterestId);
+  if (m_recoveryRetransmissionInterval < 100*1000) // <100 seconds
+    m_reexpressingRecoveryInterestId = m_scheduler.scheduleEvent (nextRetransmission,
+                                                                  bind (&SyncLogic::sendSyncRecoveryInterests, this, digest));
+
+  ndn::Interest interest(interestName);
+  interest.setMustBeFresh(true);
+
+  m_face->expressInterest(interest,
+                          bind(&SyncLogic::onSyncData, this, _1, _2),
+                          bind(&SyncLogic::onSyncTimeout, this, _1));
+}
+
+
+void
+SyncLogic::sendSyncData (const Name &name, DigestConstPtr digest, StateConstPtr state)
+{
+  SyncStateMsg msg;
+  msg << (*state);
+  sendSyncData(name, digest, msg);
+}
+
+// pass in state msg instead of state, so that there is no need to lock the state until
+// this function returns
+void
+SyncLogic::sendSyncData (const Name &name, DigestConstPtr digest, SyncStateMsg &ssm)
+{
+  _LOG_DEBUG_ID (">> D " << name);
+  int size = ssm.ByteSize();
+  char *wireData = new char[size];
+  ssm.SerializeToArray(wireData, size);
+
+  Data syncData(name);
+  syncData.setContent(reinterpret_cast<const uint8_t*>(wireData), size);
+  syncData.setFreshnessPeriod(m_syncResponseFreshness);
+  
+  m_keyChain->sign(syncData);
+  
+  m_face->put(syncData);
+  
+  delete []wireData;
+
+  // checking if our own interest got satisfied
+  bool satisfiedOwnInterest = false;
+  {
+    satisfiedOwnInterest = (m_outstandingInterestName == name);
+  }
+  
+  if (satisfiedOwnInterest)
+    {
+      _LOG_DEBUG_ID ("Satisfied our own Interest. Re-expressing (hopefully with a new digest)");
+      
+      time::Duration after = time::milliseconds(GET_RANDOM (m_reexpressionJitter));
+      // cout << "------------ reexpress interest after: " << after << endl;
+      EventId eventId = m_scheduler.scheduleEvent (after,
+                                                   bind (&SyncLogic::sendSyncInterest, this));
+      m_scheduler.cancelEvent (m_reexpressingInterestId);
+      m_reexpressingInterestId = eventId;
+    }
+}
+
+string
+SyncLogic::getRootDigest() 
+{
+  ostringstream os;
+  os << *m_state->getDigest();
+  return os.str();
+}
+
+size_t
+SyncLogic::getNumberOfBranches () const
+{
+  return m_state->getLeaves ().size ();
+}
+
+void
+SyncLogic::printState () const
+{
+  BOOST_FOREACH (const boost::shared_ptr<Sync::Leaf> leaf, m_state->getLeaves ())
+    {
+      std::cout << *leaf << std::endl;
+    }
+}
+
+std::map<std::string, bool>
+SyncLogic::getBranchPrefixes() const
+{
+  std::map<std::string, bool> m;
+
+  BOOST_FOREACH (const boost::shared_ptr<Sync::Leaf> leaf, m_state->getLeaves ())
+    {
+      std::string prefix = leaf->getInfo()->toString();
+      // do not return forwarder prefix
+      if (prefix != forwarderPrefix)
+      {
+        m.insert(pair<std::string, bool>(prefix, false));
+      }
+    }
+
+  return m;
+}
+
+}
diff --git a/nsync/src/sync-logic.h b/nsync/src/sync-logic.h
new file mode 100644
index 0000000..fc63fca
--- /dev/null
+++ b/nsync/src/sync-logic.h
@@ -0,0 +1,218 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *         Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ *         Yingdi Yu <yingdi@cs.ucla.edu>
+ */
+
+#ifndef SYNC_LOGIC_H
+#define SYNC_LOGIC_H
+
+#include <boost/random.hpp>
+#include <memory>
+#include <map>
+
+#include <ndn-cpp-dev/face.hpp>
+#include <ndn-cpp-dev/security/validator.hpp>
+#include <ndn-cpp-dev/security/key-chain.hpp>
+#include <ndn-cpp-dev/util/scheduler.hpp>
+
+#include "sync-interest-table.h"
+#include "sync-diff-state.h"
+#include "sync-full-state.h"
+#include "sync-std-name-info.h"
+
+#include "sync-diff-state-container.h"
+
+#ifdef _DEBUG
+#ifdef HAVE_LOG4CXX
+#include <log4cxx/logger.h>
+#endif
+#endif
+
+namespace Sync {
+
+struct MissingDataInfo {
+  std::string prefix;
+  SeqNo low;
+  SeqNo high;
+};
+
+/**
+ * \ingroup sync
+ * @brief A wrapper for SyncApp, which handles ccnx related things (process
+ * interests and data)
+ */
+
+class SyncLogic
+{
+public:
+  //typedef boost::function< void ( const std::string &/*prefix*/, const SeqNo &/*newSeq*/, const SeqNo &/*oldSeq*/ ) > LogicUpdateCallback;
+  typedef boost::function< void (const std::vector<MissingDataInfo> & ) > LogicUpdateCallback;
+  typedef boost::function< void (const std::string &/*prefix*/ ) > LogicRemoveCallback;
+  typedef boost::function< void (const std::string &)> LogicPerBranchCallback;
+
+  /**
+   * @brief Constructor
+   * @param syncPrefix the name prefix to use for the Sync Interest
+   * @param onUpdate function that will be called when new state is detected
+   * @param onRemove function that will be called when state is removed
+   * @param ccnxHandle ccnx handle
+   * the app data when new remote names are learned
+   */
+  SyncLogic (const ndn::Name& syncPrefix,
+             ndn::shared_ptr<ndn::Validator> validator,
+             ndn::shared_ptr<ndn::Face> face,
+             LogicUpdateCallback onUpdate,
+             LogicRemoveCallback onRemove);
+
+  SyncLogic (const ndn::Name& syncPrefix,
+             ndn::shared_ptr<ndn::Validator> validator,
+             ndn::shared_ptr<ndn::Face> face,
+             LogicPerBranchCallback onUpdateBranch);
+
+  ~SyncLogic ();
+
+  /**
+   * a wrapper for the same func in SyncApp
+   */
+  void addLocalNames (const ndn::Name &prefix, uint64_t session, uint64_t seq);
+
+  /**
+   * @brief remove a participant's subtree from the sync tree
+   * @param prefix the name prefix for the participant
+   */
+  void remove (const ndn::Name &prefix);
+
+  std::string
+  getRootDigest();
+
+#ifdef _DEBUG
+  ndn::Scheduler &
+  getScheduler () { return m_scheduler; }
+#endif
+
+  void
+  printState () const;
+
+  std::map<std::string, bool>
+  getBranchPrefixes() const;
+
+private: 
+  void
+  delayedChecksLoop ();
+
+  void
+  onSyncInterest (const ndn::Name& prefix, const ndn::Interest& interest);
+
+  void
+  onSyncRegisterFailed(const ndn::Name& prefix, const std::string& msg);
+
+  void
+  onSyncData(const ndn::Interest& interest, ndn::Data& data);
+
+  void
+  onSyncTimeout(const ndn::Interest& interest);
+
+  void
+  onSyncDataValidationFailed(const ndn::shared_ptr<const ndn::Data>& data);
+
+  void
+  onSyncDataValidated(const ndn::shared_ptr<const ndn::Data>& data);
+
+  void
+  processSyncInterest (const ndn::Name &name,
+                       DigestConstPtr digest, bool timedProcessing=false);
+
+  void
+  processSyncData (const ndn::Name &name,
+                   DigestConstPtr digest, const char *wireData, size_t len);
+  
+  void
+  processSyncRecoveryInterest (const ndn::Name &name,
+                               DigestConstPtr digest);
+  
+  void 
+  insertToDiffLog (DiffStatePtr diff);
+
+  void
+  satisfyPendingSyncInterests (DiffStateConstPtr diff);
+
+  boost::tuple<DigestConstPtr, std::string>
+  convertNameToDigestAndType (const ndn::Name &name);
+
+  void
+  sendSyncInterest ();
+
+  void
+  sendSyncRecoveryInterests (DigestConstPtr digest);
+
+  void
+  sendSyncData (const ndn::Name &name,
+                DigestConstPtr digest, StateConstPtr state);
+
+  void
+  sendSyncData (const ndn::Name &name,
+                DigestConstPtr digest, SyncStateMsg &msg);
+
+  size_t
+  getNumberOfBranches () const;
+  
+private:
+  FullStatePtr m_state;
+  DiffStateContainer m_log;
+
+  ndn::Name m_outstandingInterestName;
+  SyncInterestTable m_syncInterestTable;
+
+  ndn::Name m_syncPrefix;
+  LogicUpdateCallback m_onUpdate;
+  LogicRemoveCallback m_onRemove;
+  LogicPerBranchCallback m_onUpdateBranch;
+  bool m_perBranch;
+  ndn::ptr_lib::shared_ptr<ndn::Validator> m_validator;
+  ndn::ptr_lib::shared_ptr<ndn::KeyChain> m_keyChain;
+  ndn::ptr_lib::shared_ptr<ndn::Face> m_face;
+  const ndn::RegisteredPrefixId* m_syncRegisteredPrefixId;
+
+  ndn::Scheduler m_scheduler;
+
+  boost::mt19937 m_randomGenerator;
+  boost::variate_generator<boost::mt19937&, boost::uniform_int<> > m_rangeUniformRandom;
+  boost::variate_generator<boost::mt19937&, boost::uniform_int<> > m_reexpressionJitter;
+
+  static const int m_unknownDigestStoreTime = 10; // seconds
+  static const int m_syncResponseFreshness = 1000; // MUST BE dividable by 1000!!!
+  static const int m_syncInterestReexpress = 4; // seconds
+
+  static const int m_defaultRecoveryRetransmitInterval = 200; // milliseconds
+  uint32_t m_recoveryRetransmissionInterval; // milliseconds
+  
+  ndn::EventId m_delayedInterestProcessingId;
+  ndn::EventId m_reexpressingInterestId;
+  ndn::EventId m_reexpressingRecoveryInterestId;
+  
+  std::string m_instanceId;
+  static int m_instanceCounter;
+};
+
+
+} // Sync
+
+#endif // SYNC_APP_WRAPPER_H
diff --git a/nsync/src/sync-name-info.cc b/nsync/src/sync-name-info.cc
new file mode 100644
index 0000000..30986cd
--- /dev/null
+++ b/nsync/src/sync-name-info.cc
@@ -0,0 +1,32 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-name-info.h"
+
+// #include <boost/lexical_cast.hpp>
+
+namespace Sync {
+
+NameInfo::NameMap NameInfo::m_names;
+size_t  NameInfo::m_ids = 0;
+
+} // Sync
diff --git a/nsync/src/sync-name-info.h b/nsync/src/sync-name-info.h
new file mode 100644
index 0000000..2f7c165
--- /dev/null
+++ b/nsync/src/sync-name-info.h
@@ -0,0 +1,102 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_NAME_INFO_H
+#define SYNC_NAME_INFO_H
+
+#include <boost/shared_ptr.hpp>
+#include <boost/weak_ptr.hpp>
+#include <map>
+#include <string>
+#include "sync-digest.h"
+
+namespace Sync {
+
+/**
+ * @ingroup sync
+ * @brief Templated class for the leaf name
+ */
+class NameInfo
+{
+private:
+  typedef boost::weak_ptr<const NameInfo> const_weak_ptr;
+  
+public:
+  virtual ~NameInfo () { };
+
+  /**
+   * @brief Get ID of the record (should be locally-unique, but not really necessary---this is be used for hashing purposes)
+   */
+  size_t
+  getHashId () const { return m_id; }
+
+  /**
+   * @brief Check if two names are equal
+   * @param info name to check with
+   */
+  virtual bool
+  operator == (const NameInfo &info) const = 0;
+
+  /**
+   * @brief Check if two names are in order
+   * @param info name to check with
+   */
+  virtual bool
+  operator < (const NameInfo &info) const = 0;
+
+  /**
+   * @brief Calculates digest of the name
+   */
+  const Digest &
+  getDigest () const { return m_digest; }
+
+  /**
+   * @brief Convert prefix to string
+   * @returns string representation of prefix
+   */
+  virtual std::string
+  toString () const = 0;
+  
+protected:
+  // actual stuff
+  size_t m_id; ///< @brief Identifies NameInfo throughout the library (for hash container, doesn't need to be strictly unique)
+  Digest m_digest;
+
+  // static stuff
+  typedef std::map<std::string, const_weak_ptr> NameMap;
+  static size_t  m_ids;
+  static NameMap m_names;
+};
+
+typedef boost::shared_ptr<NameInfo> NameInfoPtr;
+typedef boost::shared_ptr<const NameInfo> NameInfoConstPtr;
+
+inline std::ostream &
+operator << (std::ostream &os, const NameInfo &info)
+{
+  os << info.toString ();
+  return os;
+}
+
+} // Sync
+
+#endif // SYNC_NAME_INFO_H
diff --git a/nsync/src/sync-seq-no.cc b/nsync/src/sync-seq-no.cc
new file mode 100644
index 0000000..fbbc53f
--- /dev/null
+++ b/nsync/src/sync-seq-no.cc
@@ -0,0 +1,39 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-seq-no.h"
+#include <boost/make_shared.hpp>
+
+using namespace boost;
+
+namespace Sync {
+
+DigestConstPtr
+SeqNo::getDigest () const
+{
+  DigestPtr digest = make_shared<Digest> ();
+  *digest << m_session << m_seq;
+  digest->finalize ();
+  return digest;
+}
+
+} // Sync
diff --git a/nsync/src/sync-seq-no.h b/nsync/src/sync-seq-no.h
new file mode 100644
index 0000000..bf21704
--- /dev/null
+++ b/nsync/src/sync-seq-no.h
@@ -0,0 +1,198 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ *         Yingdi Yu <yingdi@cs.ucla.edu>
+ */
+
+#ifndef SYNC_SEQ_NO_H
+#define SYNC_SEQ_NO_H
+
+#include <boost/cstdint.hpp>
+#include "sync-digest.h"
+
+namespace Sync {
+
+/**
+ * @ingroup sync
+ * @brief Sequence number abstraction
+ */
+class SeqNo
+{
+public:
+  /**
+   * @brief Default constructor.  Creates an zero sequence number with zero session ID (basically is an invalid object)
+   */
+  SeqNo ()
+    : m_valid (false)
+    , m_session (0)
+    , m_seq (0)
+  {
+  }
+  
+  /**
+   * @brief Copy constructor
+   * @param seq sequence number object to copy from
+   */
+  SeqNo (const SeqNo &seq)
+  {
+    *this = seq;
+  }
+
+  /**
+   * @brief Assignment operator
+   * @param seq sequence number object to copy from
+   */
+  SeqNo &
+  operator = (const SeqNo &seq)
+  {
+    m_valid = seq.m_valid;
+    m_session = seq.m_session;
+    m_seq = seq.m_seq;
+
+    return *this;
+  }
+
+  /**
+   * @brief Constructor with just sequence number. Session assumed to be zero
+   * @param seq Sequence number
+   */
+  SeqNo (uint64_t seq)
+    : m_valid (true)
+    , m_session (0)
+    , m_seq (seq)
+  { }
+
+  /**
+   * @brief Constructor with session and sequence id
+   * @param session Session ID
+   * @param seq Sequence number
+   */
+  SeqNo (uint64_t session, uint64_t seq)
+    : m_valid (true)
+    , m_session (session)
+    , m_seq (seq)
+  { }
+
+  /**
+   * @brief Get sequence number digest
+   *
+   * Digest will be calculated every time it is requested
+   */
+  DigestConstPtr
+  getDigest () const;
+
+  /**
+   * @brief Compare if one sequence number is lower
+   * @param seq Another sequence number to compare with
+   *
+   * tuple (session1, seq1) is less than (session2, seq2) in two cases:
+   * 1. session1 < session2
+   * 2. session1 == session2 and seq1 < seq2
+   */
+  bool
+  operator < (const SeqNo &seq) const
+  {
+    return m_session < seq.m_session || (m_session == seq.m_session && m_seq < seq.m_seq);
+  }
+
+  /**
+   * @brief Compare if two sequence numbers are equal
+   * @param seq Another sequence number to compare with
+   */
+  bool
+  operator == (const SeqNo &seq) const
+  {
+    return m_session == seq.m_session && m_seq == seq.m_seq;
+  }
+
+  bool
+  operator <= (const SeqNo &seq) const
+  {
+    return m_session == seq.m_session && m_seq <= seq.m_seq;
+  }
+
+  SeqNo &
+  operator ++ ()
+  {
+    if (m_valid) {
+      m_seq ++;
+    }
+    else {
+      m_valid = true;
+    }
+    return *this;
+  }
+
+  bool
+  isValid () const
+  {
+    return m_valid;
+  }
+  
+  /**
+   * @brief Get session id
+   */
+  uint64_t getSession () const
+  { return m_session; }
+
+  /**
+   * @brief Get sequence number
+   */
+  uint64_t getSeq () const
+  { return m_seq; }
+
+  /**
+   * @brief Set sequence number
+   */
+   void
+   setSeq(uint64_t seq)
+   { m_seq = seq; }
+  
+private:
+  bool m_valid;
+  
+  /**
+   * @brief Session ID (e.g., after crash, application will choose new session ID.
+   *
+   * Note that session IDs for the same name should always increase. So, the good choice
+   * for the session ID is client's timestamp
+   */
+  uint64_t m_session;
+
+  /**
+   * @brief Sequence number
+   *
+   * Sequence number for a session always starts with 0 and goes to max value.
+   *
+   * For now, wrapping sequence number after max to zero is not supported
+   */
+  uint64_t m_seq;
+};
+
+inline std::ostream &
+operator << (std::ostream &os, const SeqNo &seqno)
+{
+  os << "<session>" << seqno.getSession () << "</session><seqno>" << seqno.getSeq () << "</seqno>";
+  return os;
+}
+
+} // Sync
+
+#endif // SYNC_SEQ_NO_H
diff --git a/nsync/src/sync-socket.cc b/nsync/src/sync-socket.cc
new file mode 100644
index 0000000..db51ce2
--- /dev/null
+++ b/nsync/src/sync-socket.cc
@@ -0,0 +1,155 @@
+/* -*- Mode: C32++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Yingdi Yu <yingdi@cs.ucla.edu>
+ */
+
+#include "sync-socket.h"
+#include "sync-logging.h"
+
+using namespace std;
+using namespace ndn;
+
+INIT_LOGGER ("SyncSocket");
+
+namespace Sync {
+
+using ndn::shared_ptr;
+
+SyncSocket::SyncSocket (const Name &syncPrefix, 
+                        shared_ptr<Validator> validator,
+                        shared_ptr<Face> face,
+                        NewDataCallback dataCallback, 
+                        RemoveCallback rmCallback )
+  : m_newDataCallback(dataCallback)
+  , m_validator(validator)
+  , m_keyChain(new KeyChain())
+  , m_face(face)
+  , m_ioService(face->ioService())
+  , m_syncLogic (syncPrefix,
+                 validator,
+                 face,
+                 bind(&SyncSocket::passCallback, this, _1),
+                 rmCallback)
+{}
+
+SyncSocket::~SyncSocket()
+{
+}
+
+bool 
+SyncSocket::publishData(const Name &prefix, uint64_t session, const char *buf, size_t len, int freshness,uint64_t seq)
+{
+  shared_ptr<Data> data = make_shared<Data>();
+  data->setContent(reinterpret_cast<const uint8_t*>(buf), len);
+  data->setFreshnessPeriod(1000*freshness);
+
+  m_ioService->post(bind(&SyncSocket::publishDataInternal, this, data, prefix, session,seq));
+
+  return true;  
+}
+
+void
+SyncSocket::publishDataInternal(shared_ptr<Data> data, const Name &prefix, uint64_t session,uint64_t seq)
+{
+  uint64_t sequence = seq;
+  Name dataName = prefix;
+  dataName.append(boost::lexical_cast<string>(session)).append(boost::lexical_cast<string>(sequence));
+  data->setName(dataName);
+
+  m_keyChain->sign(*data);  
+  m_face->put(*data);
+
+  SeqNo s(session, sequence + 1);
+
+  m_sequenceLog[prefix] = s;
+  m_syncLogic.addLocalNames (prefix, session, sequence);
+}
+
+void 
+SyncSocket::fetchData(const Name &prefix, const SeqNo &seq, const OnDataValidated& onValidated, int retry)
+{
+  Name interestName = prefix;
+  interestName.append(boost::lexical_cast<string>(seq.getSession())).append(boost::lexical_cast<string>(seq.getSeq()));
+
+  const OnDataValidationFailed& onValidationFailed = bind(&SyncSocket::onDataValidationFailed, this, _1);
+  
+  ndn::Interest interest(interestName);
+  interest.setMustBeFresh(true);
+  m_face->expressInterest(interest, 
+                          bind(&SyncSocket::onData, this, _1, _2, onValidated, onValidationFailed), 
+                          bind(&SyncSocket::onDataTimeout, this, _1, retry, onValidated, onValidationFailed));
+
+}
+
+void
+SyncSocket::onData(const ndn::Interest& interest, Data& data,
+                   const OnDataValidated& onValidated,
+                   const OnDataValidationFailed& onValidationFailed)
+{
+  m_validator->validate(data, onValidated, onValidationFailed);
+}
+
+void
+SyncSocket::onDataTimeout(const ndn::Interest& interest, 
+                          int retry,
+                          const OnDataValidated& onValidated,
+                          const OnDataValidationFailed& onValidationFailed)
+{
+  if(retry > 0)
+    {
+      m_face->expressInterest(interest,
+                              bind(&SyncSocket::onData,
+                                   this,
+                                   _1,
+                                   _2,
+                                   onValidated,
+                                   onValidationFailed),
+                              bind(&SyncSocket::onDataTimeout, 
+                                   this,
+                                   _1,
+                                   retry - 1,
+                                   onValidated,
+                                   onValidationFailed));
+                              
+    }
+  else
+    _LOG_DEBUG("interest eventually time out!");
+}
+
+void
+SyncSocket::onDataValidationFailed(const shared_ptr<const Data>& data)
+{
+  _LOG_DEBUG("data cannot be verified!");
+}
+
+
+uint64_t
+SyncSocket::getNextSeq (const Name &prefix, uint64_t session)
+{
+  SequenceLog::iterator i = m_sequenceLog.find (prefix);
+
+  if (i != m_sequenceLog.end ())
+    {
+      SeqNo s = i->second;
+      if (s.getSession() == session)
+        return s.getSeq();
+    }
+  return 0;
+}
+
+}//Sync
diff --git a/nsync/src/sync-socket.h b/nsync/src/sync-socket.h
new file mode 100644
index 0000000..e4eec37
--- /dev/null
+++ b/nsync/src/sync-socket.h
@@ -0,0 +1,128 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Yingdi Yu <yingdi@cs.ucla.edu>
+ */
+
+#ifndef _SYNC_SOCKET_H
+#define _SYNC_SOCKET_H
+
+#include <ndn-cpp-dev/face.hpp>
+#include <ndn-cpp-dev/security/validator.hpp>
+#include <ndn-cpp-dev/security/key-chain.hpp>
+
+#include "sync-logic.h"
+#include "sync-seq-no.h"
+
+#include <utility>
+#include <map>
+#include <vector>
+#include <sstream>
+
+namespace Sync {
+
+/**
+ * \ingroup sync
+ * @brief A simple interface to interact with client code
+ */
+class SyncSocket
+{
+public:
+  typedef ndn::function< void (const std::vector<MissingDataInfo> &, SyncSocket * ) > NewDataCallback;
+  typedef ndn::function< void (const std::string &/*prefix*/ ) > RemoveCallback;
+
+  /**
+   * @brief the constructor for SyncAppSocket; the parameter syncPrefix
+   * should be passed to the constructor of m_syncAppWrapper; the other
+   * parameter should be passed to the constructor of m_fetcher; furthermore,
+   * the fetch function of m_fetcher should be a second paramter passed to
+   * the constructor of m_syncAppWrapper, so that m_syncAppWrapper can tell
+   * m_fetcher to fetch the actual app data after it learns the names
+   *
+   * @param syncPrefix the name prefix for Sync Interest
+   * @param dataCallback the callback to process data
+   */
+  SyncSocket (const ndn::Name &syncPrefix, 
+              ndn::shared_ptr<ndn::Validator> validator,
+              ndn::shared_ptr<ndn::Face> face,
+              NewDataCallback dataCallback, 
+              RemoveCallback rmCallback);
+
+  ~SyncSocket ();
+
+  bool 
+  publishData(const ndn::Name &prefix, uint64_t session, const char *buf, size_t len, int freshness,uint64_t seq);
+
+  void 
+  remove (const ndn::Name &prefix) 
+  { m_syncLogic.remove(prefix); }
+
+  void 
+  fetchData(const ndn::Name &prefix, const SeqNo &seq, const ndn::OnDataValidated& onValidated, int retry = 0);
+
+  std::string 
+  getRootDigest() 
+  { return m_syncLogic.getRootDigest(); }
+
+  uint64_t
+  getNextSeq (const ndn::Name &prefix, uint64_t session);
+
+  SyncLogic &
+  getLogic () 
+  { return m_syncLogic; }
+
+  // make this a static function so we don't have to create socket instance without
+  // knowing the local prefix. it's a wrong place for this function anyway
+  static std::string
+  GetLocalPrefix (); 
+  
+private:
+  void
+  publishDataInternal(ndn::shared_ptr<ndn::Data> data, const ndn::Name &prefix, uint64_t session,uint64_t seq);
+
+  void 
+  passCallback(const std::vector<MissingDataInfo> &v) 
+  { m_newDataCallback(v, this); }
+
+  void
+  onData(const ndn::Interest& interest, ndn::Data& data,
+         const ndn::OnDataValidated& onValidated,
+         const ndn::OnDataValidationFailed& onValidationFailed);
+
+  void
+  onDataTimeout(const ndn::Interest& interest, 
+                int retry,
+                const ndn::OnDataValidated& onValidated,
+                const ndn::OnDataValidationFailed& onValidationFailed);
+
+  void
+  onDataValidationFailed(const ndn::shared_ptr<const ndn::Data>& data);
+
+private:
+  typedef std::map<ndn::Name, SeqNo> SequenceLog;
+  NewDataCallback m_newDataCallback;
+  SequenceLog m_sequenceLog;
+  ndn::shared_ptr<ndn::Validator> m_validator;
+  ndn::shared_ptr<ndn::KeyChain> m_keyChain;
+  ndn::shared_ptr<ndn::Face> m_face;
+  ndn::shared_ptr<boost::asio::io_service> m_ioService;
+  SyncLogic      m_syncLogic;
+};
+
+} // Sync
+
+#endif // SYNC_SOCKET_H
diff --git a/nsync/src/sync-state-leaf-container.h b/nsync/src/sync-state-leaf-container.h
new file mode 100644
index 0000000..48819aa
--- /dev/null
+++ b/nsync/src/sync-state-leaf-container.h
@@ -0,0 +1,101 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_STATE_LEAF_CONTAINER
+#define SYNC_STATE_LEAF_CONTAINER
+
+#include "sync-leaf.h"
+#include "sync-name-info.h"
+
+#include <boost/multi_index_container.hpp>
+// #include <boost/multi_index/tag.hpp>
+#include <boost/multi_index/ordered_index.hpp>
+// #include <boost/multi_index/composite_key.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+// #include <boost/multi_index/random_access_index.hpp>
+// #include <boost/multi_index/member.hpp>
+#include <boost/multi_index/mem_fun.hpp>
+
+namespace mi = boost::multi_index;
+
+namespace Sync {
+
+struct NameInfoHash : public std::unary_function<NameInfo, std::size_t>
+{
+  std::size_t
+  operator() (NameInfoConstPtr prefix) const
+  {
+    return prefix->getHashId ();
+  }
+};
+
+struct NameInfoEqual : public std::unary_function<NameInfo, std::size_t>
+{
+  bool
+  operator() (NameInfoConstPtr prefix1, NameInfoConstPtr prefix2) const
+  {
+    return *prefix1 == *prefix2;
+  }
+};
+
+struct NameInfoCompare : public std::unary_function<NameInfo, std::size_t>
+{
+  bool
+  operator() (NameInfoConstPtr prefix1, NameInfoConstPtr prefix2) const
+  {
+    return *prefix1 < *prefix2;
+  }
+};
+
+/// @cond include_hidden 
+struct hashed { };
+struct ordered { };
+/// @endcond
+
+/**
+ * \ingroup sync
+ * @brief Container for SYNC leaves
+ */
+struct LeafContainer : public mi::multi_index_container<
+  LeafPtr,
+  mi::indexed_by<
+    // For fast access to elements using NameInfo
+    mi::hashed_unique<
+      mi::tag<hashed>,
+      mi::const_mem_fun<Leaf, NameInfoConstPtr, &Leaf::getInfo>,
+      NameInfoHash,
+      NameInfoEqual
+      >,
+        
+    mi::ordered_unique<
+      mi::tag<ordered>,
+      mi::const_mem_fun<Leaf, NameInfoConstPtr, &Leaf::getInfo>,
+      NameInfoCompare
+      >
+    >
+  >
+{
+};
+
+} // Sync
+
+#endif // SYNC_STATE_LEAF_CONTAINER
diff --git a/nsync/src/sync-state.cc b/nsync/src/sync-state.cc
new file mode 100644
index 0000000..6c374a4
--- /dev/null
+++ b/nsync/src/sync-state.cc
@@ -0,0 +1,172 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-state.h"
+#include "sync-diff-leaf.h"
+#include "sync-std-name-info.h"
+
+#include <boost/assert.hpp>
+#include <boost/foreach.hpp>
+#include <boost/shared_ptr.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/lexical_cast.hpp>
+
+// using namespace std;
+using namespace boost;
+
+typedef error_info<struct tag_errmsg, std::string> info_str; 
+
+using namespace Sync::Error;
+
+namespace Sync {
+
+/*
+std::ostream &
+operator << (std::ostream &os, const State &state)
+{
+  os << "<state>"; DEBUG_ENDL;
+  
+  BOOST_FOREACH (shared_ptr<const Leaf> leaf, state.getLeaves ().get<ordered> ())
+    {
+      shared_ptr<const DiffLeaf> diffLeaf = dynamic_pointer_cast<const DiffLeaf> (leaf);
+      if (diffLeaf != 0)
+        {
+          os << "<item action=\"" << diffLeaf->getOperation () << "\">"; DEBUG_ENDL;
+        }
+      else
+        {
+          os << "<item>"; DEBUG_ENDL;
+        }
+      os << "<name>" << *leaf->getInfo () << "</name>"; DEBUG_ENDL;
+      if (diffLeaf == 0 || (diffLeaf != 0 && diffLeaf->getOperation () == UPDATE))
+        {
+          os << "<seq>" << leaf->getSeq () << "</seq>"; DEBUG_ENDL;
+        }
+      os << "</item>"; DEBUG_ENDL;
+    }
+  os << "</state>";
+}
+*/
+
+SyncStateMsg &
+operator << (SyncStateMsg &ossm, const State &state)
+{
+  BOOST_FOREACH (shared_ptr<const Leaf> leaf, state.getLeaves ().get<ordered> ())
+  {
+    SyncState *oss = ossm.add_ss();
+    shared_ptr<const DiffLeaf> diffLeaf = dynamic_pointer_cast<const DiffLeaf> (leaf);
+    if (diffLeaf != 0 && diffLeaf->getOperation() != UPDATE)
+    {
+      oss->set_type(SyncState::DELETE);
+    }
+    else
+    {
+      oss->set_type(SyncState::UPDATE);
+    }
+
+    std::ostringstream os;
+    os << *leaf->getInfo();
+    oss->set_name(os.str());
+
+    if (diffLeaf == 0 || (diffLeaf != 0 && diffLeaf->getOperation () == UPDATE))
+    {
+      SyncState::SeqNo *seqNo = oss->mutable_seqno();
+      seqNo->set_session(leaf->getSeq().getSession());
+      seqNo->set_seq(leaf->getSeq().getSeq());
+    }
+  }
+  return ossm;
+}
+
+/*
+std::istream &
+operator >> (std::istream &in, State &state)
+{
+  TiXmlDocument doc;
+  in >> doc;
+
+  if (doc.RootElement() == 0)
+        BOOST_THROW_EXCEPTION (SyncXmlDecodingFailure () << info_str ("Empty XML"));
+  
+  for (TiXmlElement *iterator = doc.RootElement()->FirstChildElement ("item");
+       iterator != 0;
+       iterator = iterator->NextSiblingElement("item"))
+    {
+      TiXmlElement *name = iterator->FirstChildElement ("name");
+      if (name == 0 || name->GetText() == 0)
+        BOOST_THROW_EXCEPTION (SyncXmlDecodingFailure () << info_str ("<name> element is missing"));
+        
+      NameInfoConstPtr info = StdNameInfo::FindOrCreate (name->GetText());
+      
+      if (iterator->Attribute("action") == 0 || strcmp(iterator->Attribute("action"), "update") == 0)
+        {
+          TiXmlElement *seq = iterator->FirstChildElement ("seq");
+          if (seq == 0)
+            BOOST_THROW_EXCEPTION (SyncXmlDecodingFailure () << info_str ("<seq> element is missing"));
+          
+          TiXmlElement *session = seq->FirstChildElement ("session");
+          TiXmlElement *seqno = seq->FirstChildElement ("seqno");
+
+          if (session == 0 || session->GetText() == 0)
+            BOOST_THROW_EXCEPTION (SyncXmlDecodingFailure () << info_str ("<session> element is missing"));
+          if (seqno == 0 || seqno->GetText() == 0)
+            BOOST_THROW_EXCEPTION (SyncXmlDecodingFailure () << info_str ("<seqno> element is missing"));
+
+          state.update (info, SeqNo (
+                                     lexical_cast<uint32_t> (session->GetText()),
+                                     lexical_cast<uint32_t> (seqno->GetText())
+                                     ));
+        }
+      else
+        {
+          state.remove (info);
+        }
+    }
+
+  return in;
+}
+*/
+
+SyncStateMsg &
+operator >> (SyncStateMsg &issm, State &state)
+{
+  int n = issm.ss_size();
+  for (int i = 0; i < n; i++)
+  {
+    const SyncState &ss = issm.ss(i);
+    NameInfoConstPtr info = StdNameInfo::FindOrCreate (ss.name());
+    if (ss.type() == SyncState::UPDATE)
+    {
+      uint64_t session = lexical_cast<uint64_t>(ss.seqno().session());
+      uint64_t seq = lexical_cast<uint64_t>(ss.seqno().seq());
+      SeqNo seqNo(session, seq);
+      state.update(info, seqNo);
+    }
+    else
+    {
+      state.remove(info);
+    }
+  }
+  return issm;
+}
+
+}
diff --git a/nsync/src/sync-state.h b/nsync/src/sync-state.h
new file mode 100644
index 0000000..54ac9d9
--- /dev/null
+++ b/nsync/src/sync-state.h
@@ -0,0 +1,117 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_STATE_H
+#define SYNC_STATE_H
+
+#include "sync-state-leaf-container.h"
+#include <boost/exception/all.hpp>
+#include "boost/tuple/tuple.hpp"
+#include "sync-state.pb.h"
+
+/**
+ * \defgroup sync SYNC protocol
+ *
+ * Implementation of SYNC protocol
+ */
+namespace Sync {
+
+/**
+ * \ingroup sync
+ * @brief this prefix will be used for the dummy node which increases its sequence number whenever
+ * a remove operation happens; this is to prevent the reversion of root digest when we prune 
+ * a branch, i.e. help the root digest to be forward only
+ * No corresponding data msg would be published and no attempt would be made to retrieve the 
+ * data msg
+ */
+const std::string forwarderPrefix = "/d0n0t18ak/t0ps8cr8t";
+
+class State;
+typedef boost::shared_ptr<State> StatePtr;
+typedef boost::shared_ptr<State> StateConstPtr;
+
+/**
+ * \ingroup sync
+ * @brief Container for state leaves and definition of the abstract interface to work with State objects
+ */
+class State
+{
+public:
+  virtual ~State () { };
+  
+  /**
+   * @brief Add or update leaf to the state tree
+   *
+   * @param info name of the leaf
+   * @param seq  sequence number of the leaf
+   */
+  virtual boost::tuple<bool/*inserted*/, bool/*updated*/, SeqNo/*oldSeqNo*/>
+  update (NameInfoConstPtr info, const SeqNo &seq) = 0;
+
+  /**
+   * @brief Remove leaf from the state tree
+   * @param info name of the leaf
+   */
+  virtual bool
+  remove (NameInfoConstPtr info) = 0;
+
+  /**
+   * @brief Get state leaves
+   */
+  const LeafContainer &
+  getLeaves () const 
+  { return m_leaves; }
+  
+protected:
+  LeafContainer m_leaves;
+};
+
+
+/**
+ * @brief Formats a protobuf SyncStateMsg msg
+ * @param oss output SyncStateMsg msg
+ * @param state state
+ * @returns output SyncStateMsg msg
+ */
+SyncStateMsg &
+operator << (SyncStateMsg &ossm, const State &state);
+
+
+/**
+ * @brief Parse a protobuf SyncStateMsg msg
+ * @param iss input SyncStateMsg msg
+ * @param state state
+ * @returns SyncStateMsg msg
+ */
+SyncStateMsg &
+operator >> (SyncStateMsg &issm, State &state);
+
+namespace Error {
+/**
+ * @brief Will be thrown when data cannot be properly decoded to SyncStateMsg
+ */
+struct SyncStateMsgDecodingFailure : virtual boost::exception, virtual std::exception { };
+}
+
+} // Sync
+
+#endif // SYNC_STATE_H
diff --git a/nsync/src/sync-state.proto b/nsync/src/sync-state.proto
new file mode 100644
index 0000000..7cc6b18
--- /dev/null
+++ b/nsync/src/sync-state.proto
@@ -0,0 +1,24 @@
+package Sync;
+
+message SyncState
+{
+  required string name = 1;
+  enum ActionType
+  {
+    UPDATE = 0;
+    DELETE = 1;
+    OTHER = 2;
+  }
+  required ActionType type = 2;
+  message SeqNo
+  {
+    required uint64 seq = 1;
+    required uint64 session = 2;
+  }
+  optional SeqNo seqno = 3;
+}
+
+message SyncStateMsg
+{
+  repeated SyncState ss = 1;
+}
diff --git a/nsync/src/sync-std-name-info.cc b/nsync/src/sync-std-name-info.cc
new file mode 100644
index 0000000..2c0313d
--- /dev/null
+++ b/nsync/src/sync-std-name-info.cc
@@ -0,0 +1,92 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#include "sync-std-name-info.h"
+
+// using namespace std;
+using namespace boost;
+
+namespace Sync {
+
+
+NameInfoConstPtr
+StdNameInfo::FindOrCreate (const std::string &key)
+{
+  // std::cout << "FindOrCreate: " << m_names.size () << "\n";
+  
+  NameInfoConstPtr ret;
+  
+  NameMap::iterator item = m_names.find (key);
+  if (item != m_names.end ())
+    {
+      ret = item->second.lock ();
+      BOOST_ASSERT (ret != 0);
+    }
+  else
+    {
+      ret = NameInfoPtr (new StdNameInfo (key));
+      weak_ptr<const NameInfo> value (ret);
+      std::pair<NameMap::iterator,bool> inserted =
+        m_names.insert (make_pair (key, value));
+      
+      BOOST_ASSERT (inserted.second); // previous call has to insert value
+      item = inserted.first;
+    }
+
+  return ret;
+}
+
+StdNameInfo::StdNameInfo (const std::string &name)
+  : m_name (name)
+{
+  m_id = m_ids ++; // set ID for a newly inserted element
+  m_digest << name;
+  m_digest.finalize ();
+
+  // std::cout << "StdNameInfo: " << name << " = " << m_id << "\n";
+}
+
+StdNameInfo::~StdNameInfo ()
+{
+  // cout << "Destructor for " << m_name << "\n";
+  m_names.erase (toString ());
+}
+
+std::string
+StdNameInfo::toString () const
+{
+  return m_name;
+}
+
+bool
+StdNameInfo::operator == (const NameInfo &info) const
+{
+  return m_name == dynamic_cast<const StdNameInfo&> (info).m_name;
+}
+
+bool
+StdNameInfo::operator < (const NameInfo &info) const
+{
+  return m_name < dynamic_cast<const StdNameInfo&> (info).m_name;
+}
+
+} // Sync
diff --git a/nsync/src/sync-std-name-info.h b/nsync/src/sync-std-name-info.h
new file mode 100644
index 0000000..83bbebb
--- /dev/null
+++ b/nsync/src/sync-std-name-info.h
@@ -0,0 +1,74 @@
+/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
+/*
+ * Copyright (c) 2012 University of California, Los Angeles
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation;
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ *
+ * Author: Zhenkai Zhu <zhenkai@cs.ucla.edu>
+ *         Chaoyi Bian <bcy@pku.edu.cn>
+ *	   Alexander Afanasyev <alexander.afanasyev@ucla.edu>
+ */
+
+#ifndef SYNC_STD_NAME_INFO_H
+#define SYNC_STD_NAME_INFO_H
+
+#include "sync-name-info.h"
+#include <string>
+
+namespace Sync {
+
+class StdNameInfo : public NameInfo
+{
+public:
+  /**
+   * @brief Lookup existing or create new NameInfo object
+   * @param name routable prefix
+   */
+  static NameInfoConstPtr
+  FindOrCreate (const std::string &name);
+
+  /**
+   * @brief Destructor which will clean up m_names structure
+   */
+  virtual ~StdNameInfo ();
+  
+  // from NameInfo
+  virtual bool
+  operator == (const NameInfo &info) const;
+
+  virtual bool
+  operator < (const NameInfo &info) const;
+
+  virtual std::string
+  toString () const;
+
+private:
+  // implementing a singleton pattern. 
+  /**
+   * @brief Disabled default constructor. NameInfo object should be created through FindOrCreate static call.
+   */
+
+  /**
+   * @brief Disabled default
+   */
+  StdNameInfo () {}
+  StdNameInfo& operator = (const StdNameInfo &info) { (void)info; return *this; }
+  StdNameInfo (const std::string &name);
+  
+  std::string m_name;
+};
+
+} // Sync
+
+#endif // SYNC_CCNX_NAME_INFO_H