diff --git a/runtimes/google/vsync/dag.go b/runtimes/google/vsync/dag.go
index 7f97c99..9e860d9 100644
--- a/runtimes/google/vsync/dag.go
+++ b/runtimes/google/vsync/dag.go
@@ -72,8 +72,9 @@
 // and three in-memory (ephemeral) maps (graft, txSet, txGC):
 //   * nodes: one entry per (object, version) with references to the
 //            parent node(s) it is derived from, a reference to the
-//            log record identifying that change, and a reference to
-//            its transaction set (or NoTxID if none)
+//            log record identifying that change, a reference to its
+//            transaction set (or NoTxID if none), and a boolean to
+//            indicate whether this change was a deletion of the object.
 //   * heads: one entry per object pointing to its most recent version
 //            in the nodes table
 //   * trans: one entry per transaction ID containing the set of objects
@@ -137,6 +138,7 @@
 	Parents []storage.Version // references to parent versions
 	Logrec  string            // reference to log record change
 	TxID    TxID              // ID of a transaction set
+	Deleted bool              // true if the change was a delete
 }
 
 type graftInfo struct {
@@ -314,7 +316,7 @@
 //
 // If the transaction ID is set to NoTxID, this node is not part of a transaction.
 // Otherwise, track its membership in the given transaction ID.
-func (d *dag) addNode(oid storage.ID, version storage.Version, remote bool,
+func (d *dag) addNode(oid storage.ID, version storage.Version, remote, deleted bool,
 	parents []storage.Version, logrec string, tid TxID) error {
 	if d.store == nil {
 		return errors.New("invalid DAG")
@@ -413,7 +415,7 @@
 	}
 
 	// Insert the new node in the kvdb.
-	node := &dagNode{Level: level, Parents: parents, Logrec: logrec, TxID: tid}
+	node := &dagNode{Level: level, Parents: parents, Logrec: logrec, TxID: tid, Deleted: deleted}
 	return d.setNode(oid, version, node)
 }
 
@@ -426,6 +428,83 @@
 	return d.nodes.hasKey(key)
 }
 
+// childOf returns true if the node is a child of the parent version.
+// It means that the parent version is found in the node's Parents array.
+func childOf(node *dagNode, parent storage.Version) bool {
+	if node == nil || parent == storage.NoVersion {
+		return false
+	}
+	for _, pver := range node.Parents {
+		if pver == parent {
+			return true
+		}
+	}
+	return false
+}
+
+// hasParent returns true if the node (oid, version) exists in the DAG DB
+// and has (oid, parent) as a parent node. Either "version" or "parent"
+// could be NoVersion (zero).  Thus the 4 cases:
+// 1- "version" and "parent" are _not_ NoVersion: return true if both nodes
+//    exist and have a parent/child relationship.
+// 2- Only "parent" is NoVersion: return true if (oid, version) exists and
+//    either it has no parents (root of the DAG) or at least one of its
+//    parent nodes is a deleted node (i.e. has its "Deleted" flag set true).
+// 3- Only "version" is NoVersion: return true if (oid, parent) exists and
+//    at least one of its children is a deleted node.
+// 4- Both "version" and "parent" are NoVersion: return false
+func (d *dag) hasParent(oid storage.ID, version, parent storage.Version) bool {
+	if d.store == nil {
+		return false
+	}
+
+	switch {
+	case version != storage.NoVersion && parent != storage.NoVersion:
+		if !d.hasNode(oid, parent) {
+			return false
+		}
+		node, err := d.getNode(oid, version)
+		if err != nil {
+			return false
+		}
+		return childOf(node, parent)
+
+	case version != storage.NoVersion && parent == storage.NoVersion:
+		node, err := d.getNode(oid, version)
+		if err != nil {
+			return false
+		}
+		if node.Parents == nil {
+			return true
+		}
+		for _, pver := range node.Parents {
+			if pnode, err := d.getNode(oid, pver); err == nil && pnode.Deleted {
+				return true
+			}
+		}
+		return false
+
+	case version == storage.NoVersion && parent != storage.NoVersion:
+		if !d.hasNode(oid, parent) {
+			return false
+		}
+		head, err := d.getHead(oid)
+		if err != nil {
+			return false
+		}
+		found := false
+		d.ancestorIter(oid, []storage.Version{head}, func(oid storage.ID, v storage.Version, node *dagNode) error {
+			if node.Deleted && childOf(node, parent) {
+				found = true
+				return errors.New("found it -- stop the iteration")
+			}
+			return nil
+		})
+		return found
+	}
+	return false
+}
+
 // addParent adds to the DAG node (oid, version) linkage to this parent node.
 // If the parent linkage is due to a local change (from conflict resolution
 // by blessing an existing version), no need to update the grafting structure.
diff --git a/runtimes/google/vsync/dag_test.go b/runtimes/google/vsync/dag_test.go
index a36bc4c..0a50cdf 100644
--- a/runtimes/google/vsync/dag_test.go
+++ b/runtimes/google/vsync/dag_test.go
@@ -99,7 +99,7 @@
 		t.Error(err)
 	}
 
-	err = dag.addNode(oid, 4, false, []storage.Version{2, 3}, "foobar", NoTxID)
+	err = dag.addNode(oid, 4, false, false, []storage.Version{2, 3}, "foobar", NoTxID)
 	if err == nil || err.Error() != "invalid DAG" {
 		t.Errorf("addNode() did not fail on a closed DAG: %v", err)
 	}
@@ -199,6 +199,9 @@
 	if dag.hasNode(oid, 4) {
 		t.Errorf("hasNode() found an object on a closed DAG")
 	}
+	if dag.hasParent(oid, 3, 2) {
+		t.Errorf("hasParent() found an parent/child relationship on a closed DAG")
+	}
 	if pmap := dag.getParentMap(oid); len(pmap) != 0 {
 		t.Errorf("getParentMap() found data on a closed DAG: %v", pmap)
 	}
@@ -506,26 +509,26 @@
 	}
 
 	// Make sure an existing node cannot be added again.
-	if err = dag.addNode(oid, 1, false, []storage.Version{0, 2}, "foobar", NoTxID); err == nil {
+	if err = dag.addNode(oid, 1, false, false, []storage.Version{0, 2}, "foobar", NoTxID); err == nil {
 		t.Errorf("addNode() did not fail when given an existing node")
 	}
 
 	// Make sure a new node cannot have more than 2 parents.
-	if err = dag.addNode(oid, 3, false, []storage.Version{0, 1, 2}, "foobar", NoTxID); err == nil {
+	if err = dag.addNode(oid, 3, false, false, []storage.Version{0, 1, 2}, "foobar", NoTxID); err == nil {
 		t.Errorf("addNode() did not fail when given 3 parents")
 	}
 
 	// Make sure a new node cannot have an invalid parent.
-	if err = dag.addNode(oid, 3, false, []storage.Version{0, 555}, "foobar", NoTxID); err == nil {
+	if err = dag.addNode(oid, 3, false, false, []storage.Version{0, 555}, "foobar", NoTxID); err == nil {
 		t.Errorf("addNode() did not fail when using an invalid parent")
 	}
 
 	// Make sure a new root node (no parents) cannot be added once a root exists.
 	// For the parents array, check both the "nil" and the empty array as input.
-	if err = dag.addNode(oid, 6789, false, nil, "foobar", NoTxID); err == nil {
+	if err = dag.addNode(oid, 6789, false, false, nil, "foobar", NoTxID); err == nil {
 		t.Errorf("Adding a 2nd root node (nil parents) for object %d in DAG file %s did not fail", oid, dagfile)
 	}
-	if err = dag.addNode(oid, 6789, false, []storage.Version{}, "foobar", NoTxID); err == nil {
+	if err = dag.addNode(oid, 6789, false, false, []storage.Version{}, "foobar", NoTxID); err == nil {
 		t.Errorf("Adding a 2nd root node (empty parents) for object %d in DAG file %s did not fail", oid, dagfile)
 	}
 
@@ -1599,10 +1602,10 @@
 		t.Errorf("Transactions map for Tx ID %v has length %d instead of 0 in DAG file %s", tid_1, n, dagfile)
 	}
 
-	if err := dag.addNode(oid_a, 3, false, []storage.Version{2}, "logrec-a-03", tid_1); err != nil {
+	if err := dag.addNode(oid_a, 3, false, false, []storage.Version{2}, "logrec-a-03", tid_1); err != nil {
 		t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_a, tid_1, dagfile, err)
 	}
-	if err := dag.addNode(oid_b, 3, false, []storage.Version{2}, "logrec-b-03", tid_1); err != nil {
+	if err := dag.addNode(oid_b, 3, false, false, []storage.Version{2}, "logrec-b-03", tid_1); err != nil {
 		t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_b, tid_1, dagfile, err)
 	}
 
@@ -1620,7 +1623,7 @@
 		t.Errorf("Transactions map for Tx ID %v has length %d instead of 0 in DAG file %s", tid_2, n, dagfile)
 	}
 
-	if err := dag.addNode(oid_c, 2, false, []storage.Version{1}, "logrec-c-02", tid_2); err != nil {
+	if err := dag.addNode(oid_c, 2, false, false, []storage.Version{1}, "logrec-c-02", tid_2); err != nil {
 		t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_c, tid_2, dagfile, err)
 	}
 
@@ -1651,7 +1654,7 @@
 		bad_tid++
 	}
 
-	if err := dag.addNode(oid_c, 3, false, []storage.Version{2}, "logrec-c-03", bad_tid); err == nil {
+	if err := dag.addNode(oid_c, 3, false, false, []storage.Version{2}, "logrec-c-03", bad_tid); err == nil {
 		t.Errorf("addNode() did not fail on object %d for a bad Tx ID %v in DAG file %s", oid_c, bad_tid, dagfile)
 	}
 	if err := dag.addNodeTxEnd(bad_tid); err == nil {
@@ -1783,10 +1786,10 @@
 	if tid_1 == NoTxID {
 		t.Fatal("Cannot start 1st DAG addNode() transaction")
 	}
-	if err := dag.addNode(oid_a, 3, false, []storage.Version{2}, "logrec-a-03", tid_1); err != nil {
+	if err := dag.addNode(oid_a, 3, false, false, []storage.Version{2}, "logrec-a-03", tid_1); err != nil {
 		t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_a, tid_1, dagfile, err)
 	}
-	if err := dag.addNode(oid_b, 3, false, []storage.Version{2}, "logrec-b-03", tid_1); err != nil {
+	if err := dag.addNode(oid_b, 3, false, false, []storage.Version{2}, "logrec-b-03", tid_1); err != nil {
 		t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_b, tid_1, dagfile, err)
 	}
 	if err := dag.addNodeTxEnd(tid_1); err != nil {
@@ -1797,20 +1800,20 @@
 	if tid_2 == NoTxID {
 		t.Fatal("Cannot start 2nd DAG addNode() transaction")
 	}
-	if err := dag.addNode(oid_b, 4, false, []storage.Version{3}, "logrec-b-04", tid_2); err != nil {
+	if err := dag.addNode(oid_b, 4, false, false, []storage.Version{3}, "logrec-b-04", tid_2); err != nil {
 		t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_b, tid_2, dagfile, err)
 	}
-	if err := dag.addNode(oid_c, 2, false, []storage.Version{1}, "logrec-c-02", tid_2); err != nil {
+	if err := dag.addNode(oid_c, 2, false, false, []storage.Version{1}, "logrec-c-02", tid_2); err != nil {
 		t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_c, tid_2, dagfile, err)
 	}
 	if err := dag.addNodeTxEnd(tid_2); err != nil {
 		t.Errorf("Cannot addNodeTxEnd() for Tx ID %v in DAG file %s: %v", tid_2, dagfile, err)
 	}
 
-	if err := dag.addNode(oid_a, 4, false, []storage.Version{3}, "logrec-a-04", NoTxID); err != nil {
+	if err := dag.addNode(oid_a, 4, false, false, []storage.Version{3}, "logrec-a-04", NoTxID); err != nil {
 		t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_a, tid_1, dagfile, err)
 	}
-	if err := dag.addNode(oid_b, 5, false, []storage.Version{4}, "logrec-b-05", NoTxID); err != nil {
+	if err := dag.addNode(oid_b, 5, false, false, []storage.Version{4}, "logrec-b-05", NoTxID); err != nil {
 		t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_b, tid_2, dagfile, err)
 	}
 
@@ -1885,7 +1888,7 @@
 	}
 
 	// Add c3 as a new head and prune at that point.  This should GC Tx-2.
-	if err := dag.addNode(oid_c, 3, false, []storage.Version{2}, "logrec-c-03", NoTxID); err != nil {
+	if err := dag.addNode(oid_c, 3, false, false, []storage.Version{2}, "logrec-c-03", NoTxID); err != nil {
 		t.Errorf("Cannot addNode() on object %d in DAG file %s: %v", oid_c, dagfile, err)
 	}
 	if err = dag.moveHead(oid_c, 3); err != nil {
@@ -1916,3 +1919,65 @@
 		}
 	}
 }
+
+// TestHasParent tests lookup of DAG parent/child relationship (i.e. hasParent()).
+func TestHasParent(t *testing.T) {
+	dagfile := dagFilename()
+	defer os.Remove(dagfile)
+
+	dag, err := openDAG(dagfile)
+	if err != nil {
+		t.Fatalf("Cannot open new DAG file %s", dagfile)
+	}
+
+	if err = dagReplayCommands(dag, "local-init-03.sync"); err != nil {
+		t.Fatal(err)
+	}
+
+	oid, err := strToObjID("12345")
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	// The object mutations are: v1 -> v2 (deleted) -> v3 with v3 as head node.
+
+	type hasParentTest struct {
+		parent storage.Version
+		child  storage.Version
+		result bool
+	}
+	tests := []hasParentTest{
+		{storage.NoVersion, storage.NoVersion, false},
+		{1, 2, true},
+		{2, 3, true},
+		{1, 999, false},
+		{999, 1, false},
+		{1, 3, false},
+		{1, storage.NoVersion, true},
+		{2, storage.NoVersion, false},
+		{3, storage.NoVersion, false},
+		{999, storage.NoVersion, false},
+		{storage.NoVersion, 1, true},
+		{storage.NoVersion, 2, false},
+		{storage.NoVersion, 3, true},
+		{storage.NoVersion, 999, false},
+	}
+
+	for _, test := range tests {
+		result := dag.hasParent(oid, test.child, test.parent)
+		if result != test.result {
+			t.Errorf("hasParent() for parent/child (%d/%d) in DAG file %s: %v instead of %v",
+				test.parent, test.child, dagfile, result, test.result)
+		}
+	}
+
+	// Increase coverage of internal helper function.
+	if childOf(nil, 3) {
+		t.Errorf("childOf() returned true on a nil node")
+	}
+	if childOf(&dagNode{}, storage.NoVersion) {
+		t.Errorf("childOf() returned true on a NoVersion parent")
+	}
+
+	dag.close()
+}
diff --git a/runtimes/google/vsync/ilog.go b/runtimes/google/vsync/ilog.go
index a40606b..f7c46f2 100644
--- a/runtimes/google/vsync/ilog.go
+++ b/runtimes/google/vsync/ilog.go
@@ -410,7 +410,7 @@
 	}
 
 	// Insert the new log record into dag.
-	if err = l.s.dag.addNode(rec.ObjID, rec.CurVers, false, rec.Parents, logKey, txID); err != nil {
+	if err = l.s.dag.addNode(rec.ObjID, rec.CurVers, false, val.Delete, rec.Parents, logKey, txID); err != nil {
 		return err
 	}
 
diff --git a/runtimes/google/vsync/initiator.go b/runtimes/google/vsync/initiator.go
index e885359..d6c786e 100644
--- a/runtimes/google/vsync/initiator.go
+++ b/runtimes/google/vsync/initiator.go
@@ -330,7 +330,7 @@
 	vlog.VI(2).Infof("insertRecInLogAndDag:: Adding log record %v, Tx %v", rec, txID)
 	switch rec.RecType {
 	case NodeRec:
-		return i.syncd.dag.addNode(rec.ObjID, rec.CurVers, true, rec.Parents, logKey, txID)
+		return i.syncd.dag.addNode(rec.ObjID, rec.CurVers, true, rec.Value.Delete, rec.Parents, logKey, txID)
 	case LinkRec:
 		return i.syncd.dag.addParent(rec.ObjID, rec.CurVers, rec.Parents[0], true)
 	default:
@@ -642,7 +642,7 @@
 				// TODO(hpucha): addNode operations arising out of conflict resolution
 				// may need to be part of a transaction when app-driven resolution
 				// is introduced.
-				err = i.syncd.dag.addNode(obj, rec.CurVers, false, rec.Parents, logKey, NoTxID)
+				err = i.syncd.dag.addNode(obj, rec.CurVers, false, rec.Value.Delete, rec.Parents, logKey, NoTxID)
 			case LinkRec:
 				err = i.syncd.dag.addParent(obj, rec.CurVers, rec.Parents[0], false)
 			default:
diff --git a/runtimes/google/vsync/initiator_test.go b/runtimes/google/vsync/initiator_test.go
index 4755fc8..987d4d7 100644
--- a/runtimes/google/vsync/initiator_test.go
+++ b/runtimes/google/vsync/initiator_test.go
@@ -49,7 +49,7 @@
 	if _, err := s.hdlInitiator.getLogRec(objID, expRec.CurVers); err == nil {
 		t.Errorf("GetLogRec didn't fail")
 	}
-	if err = s.dag.addNode(objID, expRec.CurVers, false, expRec.Parents, logKey, NoTxID); err != nil {
+	if err = s.dag.addNode(objID, expRec.CurVers, false, false, expRec.Parents, logKey, NoTxID); err != nil {
 		t.Errorf("AddNode failed with err %v", err)
 	}
 	curRec, err := s.hdlInitiator.getLogRec(objID, expRec.CurVers)
@@ -98,7 +98,7 @@
 		if err != nil {
 			t.Errorf("PutLogRec failed with err %v", err)
 		}
-		if err = s.dag.addNode(objID, expRec.CurVers, false, expRec.Parents, logKey, NoTxID); err != nil {
+		if err = s.dag.addNode(objID, expRec.CurVers, false, false, expRec.Parents, logKey, NoTxID); err != nil {
 			t.Errorf("AddNode failed with err %v", err)
 		}
 	}
diff --git a/runtimes/google/vsync/replay_test.go b/runtimes/google/vsync/replay_test.go
index 1f43a28..26df5fa 100644
--- a/runtimes/google/vsync/replay_test.go
+++ b/runtimes/google/vsync/replay_test.go
@@ -35,6 +35,7 @@
 	devID     DeviceID
 	genVec    GenVector
 	continued bool
+	deleted   bool
 }
 
 func strToObjID(objStr string) (storage.ID, error) {
@@ -91,7 +92,7 @@
 
 		switch args[0] {
 		case "addl", "addr":
-			expNargs := 7
+			expNargs := 8
 			if nargs != expNargs {
 				return nil, fmt.Errorf("%s:%d: need %d args instead of %d", file, lineno, expNargs, nargs)
 			}
@@ -114,7 +115,11 @@
 			if err != nil {
 				return nil, fmt.Errorf("%s:%d: invalid continued bit: %s", file, lineno, args[6])
 			}
-			cmd := syncCommand{version: version, parents: parents, logrec: args[5], continued: continued}
+			del, err := strconv.ParseBool(args[7])
+			if err != nil {
+				return nil, fmt.Errorf("%s:%d: invalid deleted bit: %s", file, lineno, args[7])
+			}
+			cmd := syncCommand{version: version, parents: parents, logrec: args[5], continued: continued, deleted: del}
 			if args[0] == "addl" {
 				cmd.cmd = addLocal
 			} else {
@@ -197,7 +202,8 @@
 	for _, cmd := range cmds {
 		switch cmd.cmd {
 		case addLocal:
-			if err = dag.addNode(cmd.objID, cmd.version, false, cmd.parents, cmd.logrec, NoTxID); err != nil {
+			err = dag.addNode(cmd.objID, cmd.version, false, cmd.deleted, cmd.parents, cmd.logrec, NoTxID)
+			if err != nil {
 				return fmt.Errorf("cannot add local node %d:%d to DAG: %v", cmd.objID, cmd.version, err)
 			}
 			if err := dag.moveHead(cmd.objID, cmd.version); err != nil {
@@ -206,7 +212,8 @@
 			dag.flush()
 
 		case addRemote:
-			if err = dag.addNode(cmd.objID, cmd.version, true, cmd.parents, cmd.logrec, NoTxID); err != nil {
+			err = dag.addNode(cmd.objID, cmd.version, true, cmd.deleted, cmd.parents, cmd.logrec, NoTxID)
+			if err != nil {
 				return fmt.Errorf("cannot add remote node %d:%d to DAG: %v", cmd.objID, cmd.version, err)
 			}
 			dag.flush()
diff --git a/runtimes/google/vsync/testdata/local-init-00.sync b/runtimes/google/vsync/testdata/local-init-00.sync
index 047b2de..d1dace2 100644
--- a/runtimes/google/vsync/testdata/local-init-00.sync
+++ b/runtimes/google/vsync/testdata/local-init-00.sync
@@ -1,6 +1,6 @@
 # Create an object locally and update it twice (linked-list).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addl|12345|0|||logrec-00|false
-addl|12345|1|0||logrec-01|false
-addl|12345|2|1||logrec-02|false
+addl|12345|0|||logrec-00|false|false
+addl|12345|1|0||logrec-01|false|false
+addl|12345|2|1||logrec-02|false|false
diff --git a/runtimes/google/vsync/testdata/local-init-01.sync b/runtimes/google/vsync/testdata/local-init-01.sync
index 93f0b55..525dd09 100644
--- a/runtimes/google/vsync/testdata/local-init-01.sync
+++ b/runtimes/google/vsync/testdata/local-init-01.sync
@@ -1,12 +1,12 @@
 # Create an object DAG locally with branches and resolved conflicts.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addl|12345|0|||logrec-00|false
-addl|12345|1|0||logrec-01|false
-addl|12345|2|1||logrec-02|false
-addl|12345|3|1||logrec-03|false
-addl|12345|4|2|3|logrec-04|false
-addl|12345|5|4||logrec-05|false
-addl|12345|6|1||logrec-06|false
-addl|12345|7|5|6|logrec-07|false
-addl|12345|8|7||logrec-08|false
+addl|12345|0|||logrec-00|false|false
+addl|12345|1|0||logrec-01|false|false
+addl|12345|2|1||logrec-02|false|false
+addl|12345|3|1||logrec-03|false|false
+addl|12345|4|2|3|logrec-04|false|false
+addl|12345|5|4||logrec-05|false|false
+addl|12345|6|1||logrec-06|false|false
+addl|12345|7|5|6|logrec-07|false|false
+addl|12345|8|7||logrec-08|false|false
diff --git a/runtimes/google/vsync/testdata/local-init-02.sync b/runtimes/google/vsync/testdata/local-init-02.sync
index 118e3f8..70b1319 100644
--- a/runtimes/google/vsync/testdata/local-init-02.sync
+++ b/runtimes/google/vsync/testdata/local-init-02.sync
@@ -1,10 +1,10 @@
 # Create DAGs for 3 objects locally.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addl|12345|1|||logrec-a-01|false
-addl|12345|2|1||logrec-a-02|false
+addl|12345|1|||logrec-a-01|false|false
+addl|12345|2|1||logrec-a-02|false|false
 
-addl|67890|1|||logrec-b-01|false
-addl|67890|2|1||logrec-b-02|false
+addl|67890|1|||logrec-b-01|false|false
+addl|67890|2|1||logrec-b-02|false|false
 
-addl|222|1|||logrec-c-01|false
+addl|222|1|||logrec-c-01|false|false
diff --git a/runtimes/google/vsync/testdata/local-init-03.sync b/runtimes/google/vsync/testdata/local-init-03.sync
new file mode 100644
index 0000000..63f4fc6
--- /dev/null
+++ b/runtimes/google/vsync/testdata/local-init-03.sync
@@ -0,0 +1,5 @@
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
+
+addl|12345|1|||logrec-01|false|false
+addl|12345|2|1||logrec-02|false|true
+addl|12345|3|2||logrec-03|false|false
diff --git a/runtimes/google/vsync/testdata/local-resolve-00.sync b/runtimes/google/vsync/testdata/local-resolve-00.sync
index b4f1518..02e1c88 100644
--- a/runtimes/google/vsync/testdata/local-resolve-00.sync
+++ b/runtimes/google/vsync/testdata/local-resolve-00.sync
@@ -1,4 +1,4 @@
 # Create an object locally and update it twice (linked-list).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addl|12345|6|2|5|logrec-06|false
+addl|12345|6|2|5|logrec-06|false|false
diff --git a/runtimes/google/vsync/testdata/remote-conf-00.log.sync b/runtimes/google/vsync/testdata/remote-conf-00.log.sync
index 23beca6..994a66f 100644
--- a/runtimes/google/vsync/testdata/remote-conf-00.log.sync
+++ b/runtimes/google/vsync/testdata/remote-conf-00.log.sync
@@ -1,8 +1,8 @@
 # Update an object remotely three times triggering one conflict after
 # it was created locally up to v2 (i.e. assume the remote sync received
 # it from the local sync at v1, then updated separately).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|12345|3|1||VeyronPhone:1:0|false
-addr|12345|4|3||VeyronPhone:1:1|false
-addr|12345|5|4||VeyronPhone:1:2|false
+addr|12345|3|1||VeyronPhone:1:0|false|false
+addr|12345|4|3||VeyronPhone:1:1|false|false
+addr|12345|5|4||VeyronPhone:1:2|false|false
diff --git a/runtimes/google/vsync/testdata/remote-conf-00.sync b/runtimes/google/vsync/testdata/remote-conf-00.sync
index ea6ab3f..7e555a6 100644
--- a/runtimes/google/vsync/testdata/remote-conf-00.sync
+++ b/runtimes/google/vsync/testdata/remote-conf-00.sync
@@ -1,8 +1,8 @@
 # Update an object remotely three times triggering one conflict after
 # it was created locally up to v2 (i.e. assume the remote sync received
 # it from the local sync at v1, then updated separately).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|12345|3|1||logrec-03|false
-addr|12345|4|3||logrec-04|false
-addr|12345|5|4||logrec-05|false
+addr|12345|3|1||logrec-03|false|false
+addr|12345|4|3||logrec-04|false|false
+addr|12345|5|4||logrec-05|false|false
diff --git a/runtimes/google/vsync/testdata/remote-conf-01.log.sync b/runtimes/google/vsync/testdata/remote-conf-01.log.sync
index 1bcc3c9..4fabf55 100644
--- a/runtimes/google/vsync/testdata/remote-conf-01.log.sync
+++ b/runtimes/google/vsync/testdata/remote-conf-01.log.sync
@@ -3,8 +3,8 @@
 # v0, made its own conflicting v3 that it resolved into v4 (against v1)
 # then made a v5 change.  When the local sync gets back this info it
 # sees 2 graft points: v0-v3 and v1-v4. 
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|12345|3|0||VeyronLaptop:1:0|false
-addr|12345|4|1|3|VeyronPhone:1:0|false
-addr|12345|5|4||VeyronPhone:1:1|false
+addr|12345|3|0||VeyronLaptop:1:0|false|false
+addr|12345|4|1|3|VeyronPhone:1:0|false|false
+addr|12345|5|4||VeyronPhone:1:1|false|false
diff --git a/runtimes/google/vsync/testdata/remote-conf-01.sync b/runtimes/google/vsync/testdata/remote-conf-01.sync
index b9aece7..4655a1e 100644
--- a/runtimes/google/vsync/testdata/remote-conf-01.sync
+++ b/runtimes/google/vsync/testdata/remote-conf-01.sync
@@ -3,8 +3,8 @@
 # v0, made its own conflicting v3 that it resolved into v4 (against v1)
 # then made a v5 change.  When the local sync gets back this info it
 # sees 2 graft points: v0-v3 and v1-v4. 
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|12345|3|0||logrec-03|false
-addr|12345|4|1|3|logrec-04|false
-addr|12345|5|4||logrec-05|false
+addr|12345|3|0||logrec-03|false|false
+addr|12345|4|1|3|logrec-04|false|false
+addr|12345|5|4||logrec-05|false|false
diff --git a/runtimes/google/vsync/testdata/remote-conf-link.log.sync b/runtimes/google/vsync/testdata/remote-conf-link.log.sync
index 627769a..65d0176 100644
--- a/runtimes/google/vsync/testdata/remote-conf-link.log.sync
+++ b/runtimes/google/vsync/testdata/remote-conf-link.log.sync
@@ -1,5 +1,5 @@
 # Update an object remotely, detect conflict, and bless the local version.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|12345|3|0||VeyronPhone:1:0|false
+addr|12345|3|0||VeyronPhone:1:0|false|false
 linkr|12345|3|1||VeyronPhone:1:1
diff --git a/runtimes/google/vsync/testdata/remote-init-00.log.sync b/runtimes/google/vsync/testdata/remote-init-00.log.sync
index 3a945e9..0030417 100644
--- a/runtimes/google/vsync/testdata/remote-init-00.log.sync
+++ b/runtimes/google/vsync/testdata/remote-init-00.log.sync
@@ -1,6 +1,6 @@
 # Create an object remotely and update it twice (linked-list).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|12345|0|||VeyronPhone:1:0|false
-addr|12345|1|0||VeyronPhone:1:1|false
-addr|12345|2|1||VeyronPhone:1:2|false
+addr|12345|0|||VeyronPhone:1:0|false|false
+addr|12345|1|0||VeyronPhone:1:1|false|false
+addr|12345|2|1||VeyronPhone:1:2|false|false
diff --git a/runtimes/google/vsync/testdata/remote-init-00.sync b/runtimes/google/vsync/testdata/remote-init-00.sync
index 9ae9adc..7f2189a 100644
--- a/runtimes/google/vsync/testdata/remote-init-00.sync
+++ b/runtimes/google/vsync/testdata/remote-init-00.sync
@@ -1,6 +1,6 @@
 # Create an object remotely and update it twice (linked-list).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|12345|0|||logrec-00|false
-addr|12345|1|0||logrec-01|false
-addr|12345|2|1||logrec-02|false
+addr|12345|0|||logrec-00|false|false
+addr|12345|1|0||logrec-01|false|false
+addr|12345|2|1||logrec-02|false|false
diff --git a/runtimes/google/vsync/testdata/remote-init-01.log.sync b/runtimes/google/vsync/testdata/remote-init-01.log.sync
index 9b02859..a357986 100644
--- a/runtimes/google/vsync/testdata/remote-init-01.log.sync
+++ b/runtimes/google/vsync/testdata/remote-init-01.log.sync
@@ -1,6 +1,6 @@
 # Create an object remotely and update it twice (linked-list).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|12345|0|||VeyronPhone:5:0|false
-addr|12345|1|0||VeyronPhone:5:1|false
-addr|12345|2|1||VeyronPhone:5:2|false
+addr|12345|0|||VeyronPhone:5:0|false|false
+addr|12345|1|0||VeyronPhone:5:1|false|false
+addr|12345|2|1||VeyronPhone:5:2|false|false
diff --git a/runtimes/google/vsync/testdata/remote-init-02.log.sync b/runtimes/google/vsync/testdata/remote-init-02.log.sync
index cf71306..c0053ba 100644
--- a/runtimes/google/vsync/testdata/remote-init-02.log.sync
+++ b/runtimes/google/vsync/testdata/remote-init-02.log.sync
@@ -1,17 +1,17 @@
 # Create an object remotely and update it twice (linked-list).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|123|0|||VeyronPhone:1:0|false
+addr|123|0|||VeyronPhone:1:0|false|false
 
-addr|123|1|0||VeyronPhone:1:1|true
-addr|456|0|||VeyronPhone:1:2|true
-addr|789|0|||VeyronPhone:1:3|false
+addr|123|1|0||VeyronPhone:1:1|true|false
+addr|456|0|||VeyronPhone:1:2|true|false
+addr|789|0|||VeyronPhone:1:3|false|false
 
-addr|789|1|0||VeyronPhone:1:4|false
+addr|789|1|0||VeyronPhone:1:4|false|false
 
-addr|789|2|0||VeyronTab:1:0|false
+addr|789|2|0||VeyronTab:1:0|false|false
 
-addr|789|3|1|2|VeyronPhone:2:0|false
+addr|789|3|1|2|VeyronPhone:2:0|false|false
 
-addr|123|2|1||VeyronPhone:2:1|true
-addr|456|1|0||VeyronPhone:2:2|false
\ No newline at end of file
+addr|123|2|1||VeyronPhone:2:1|true|false
+addr|456|1|0||VeyronPhone:2:2|false|false
diff --git a/runtimes/google/vsync/testdata/remote-noconf-00.log.sync b/runtimes/google/vsync/testdata/remote-noconf-00.log.sync
index 55afb29..c291155 100644
--- a/runtimes/google/vsync/testdata/remote-noconf-00.log.sync
+++ b/runtimes/google/vsync/testdata/remote-noconf-00.log.sync
@@ -1,8 +1,8 @@
 # Update an object remotely three times without triggering a conflict
 # after it was created locally up to v2 (i.e. assume the remote sync
 # received it from the local sync first, then updated it).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|12345|3|2||VeyronPhone:1:0|false
-addr|12345|4|3||VeyronPhone:1:1|false
-addr|12345|5|4||VeyronPhone:1:2|false
+addr|12345|3|2||VeyronPhone:1:0|false|false
+addr|12345|4|3||VeyronPhone:1:1|false|false
+addr|12345|5|4||VeyronPhone:1:2|false|false
diff --git a/runtimes/google/vsync/testdata/remote-noconf-00.sync b/runtimes/google/vsync/testdata/remote-noconf-00.sync
index fc7b633..9b95c86 100644
--- a/runtimes/google/vsync/testdata/remote-noconf-00.sync
+++ b/runtimes/google/vsync/testdata/remote-noconf-00.sync
@@ -1,8 +1,8 @@
 # Update an object remotely three times without triggering a conflict
 # after it was created locally up to v2 (i.e. assume the remote sync
 # received it from the local sync first, then updated it).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|12345|3|2||logrec-03|false
-addr|12345|4|3||logrec-04|false
-addr|12345|5|4||logrec-05|false
+addr|12345|3|2||logrec-03|false|false
+addr|12345|4|3||logrec-04|false|false
+addr|12345|5|4||logrec-05|false|false
diff --git a/runtimes/google/vsync/testdata/remote-noconf-link-00.log.sync b/runtimes/google/vsync/testdata/remote-noconf-link-00.log.sync
index b3849d5..ab1e2c4 100644
--- a/runtimes/google/vsync/testdata/remote-noconf-link-00.log.sync
+++ b/runtimes/google/vsync/testdata/remote-noconf-link-00.log.sync
@@ -1,5 +1,5 @@
 # Update an object remotely, detect conflict, and bless the remote version.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|12345|3|0||VeyronPhone:1:0|false
+addr|12345|3|0||VeyronPhone:1:0|false|false
 linkr|12345|1|3||VeyronPhone:1:1
diff --git a/runtimes/google/vsync/testdata/remote-noconf-link-01.log.sync b/runtimes/google/vsync/testdata/remote-noconf-link-01.log.sync
index 9495dc1..4ee0b53 100644
--- a/runtimes/google/vsync/testdata/remote-noconf-link-01.log.sync
+++ b/runtimes/google/vsync/testdata/remote-noconf-link-01.log.sync
@@ -1,5 +1,5 @@
 # Update an object remotely, detect conflict, and bless the local version.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|12345|3|0||VeyronPhone:1:0|false
+addr|12345|3|0||VeyronPhone:1:0|false|false
 linkr|12345|3|2||VeyronPhone:1:1
diff --git a/runtimes/google/vsync/testdata/remote-noconf-link-02.log.sync b/runtimes/google/vsync/testdata/remote-noconf-link-02.log.sync
index 455fb5c..53d9735 100644
--- a/runtimes/google/vsync/testdata/remote-noconf-link-02.log.sync
+++ b/runtimes/google/vsync/testdata/remote-noconf-link-02.log.sync
@@ -1,6 +1,6 @@
 # Update an object remotely, detect conflict, and bless the remote version, and continue updating.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
-addr|12345|3|0||VeyronPhone:1:0|false
+addr|12345|3|0||VeyronPhone:1:0|false|false
 linkr|12345|2|3||VeyronPhone:1:1
-addr|12345|4|2||VeyronPhone:2:0|false
+addr|12345|4|2||VeyronPhone:2:0|false|false
diff --git a/runtimes/google/vsync/testdata/remote-noconf-link-repeat.log.sync b/runtimes/google/vsync/testdata/remote-noconf-link-repeat.log.sync
index 9a04969..2ca80bf 100644
--- a/runtimes/google/vsync/testdata/remote-noconf-link-repeat.log.sync
+++ b/runtimes/google/vsync/testdata/remote-noconf-link-repeat.log.sync
@@ -1,5 +1,5 @@
 # Resolve the same conflict on two different devices.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 
 linkr|12345|2|3||VeyronLaptop:1:0
 
diff --git a/runtimes/google/vsync/testdata/test-1obj.gc.sync b/runtimes/google/vsync/testdata/test-1obj.gc.sync
index 9cef648..93eca9e 100644
--- a/runtimes/google/vsync/testdata/test-1obj.gc.sync
+++ b/runtimes/google/vsync/testdata/test-1obj.gc.sync
@@ -1,12 +1,12 @@
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 # Local node is A. Remote nodes are B and C.
-addr|12345|0|||C:1:0|false
-addr|12345|1|0||B:1:0|false
-addl|12345|2|0||A:1:0|false
-addl|12345|3|1|2|A:2:0|false
-addr|12345|4|3||C:2:0|false
-addr|12345|5|3||B:2:0|false
-addr|12345|6|4|5|B:3:0|false
+addr|12345|0|||C:1:0|false|false
+addr|12345|1|0||B:1:0|false|false
+addl|12345|2|0||A:1:0|false|false
+addl|12345|3|1|2|A:2:0|false|false
+addr|12345|4|3||C:2:0|false|false
+addr|12345|5|3||B:2:0|false|false
+addr|12345|6|4|5|B:3:0|false|false
 # Devtable state
 setdev|A|A:2,B:3,C:2
 setdev|B|A:2,B:3,C:2
diff --git a/runtimes/google/vsync/testdata/test-3obj.gc.sync b/runtimes/google/vsync/testdata/test-3obj.gc.sync
index fcf6598..d9a3899 100644
--- a/runtimes/google/vsync/testdata/test-3obj.gc.sync
+++ b/runtimes/google/vsync/testdata/test-3obj.gc.sync
@@ -1,42 +1,42 @@
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
 # Local node is A. Remote nodes are B and C.
-addl|123|1|||A:1:0|false
+addl|123|1|||A:1:0|false|false
 
-addr|456|1|||B:1:0|false
+addr|456|1|||B:1:0|false|false
 
-addr|456|2|1||B:2:0|false
-addr|123|2|1||B:2:1|false
+addr|456|2|1||B:2:0|false|false
+addr|123|2|1||B:2:1|false|false
 
-addl|456|3|2||A:2:0|false
-addl|123|4|2||A:2:1|false
+addl|456|3|2||A:2:0|false|false
+addl|123|4|2||A:2:1|false|false
 
-addr|789|1|||C:1:0|false
+addr|789|1|||C:1:0|false|false
 
-addr|789|2|1||C:2:0|false
+addr|789|2|1||C:2:0|false|false
 
-addr|123|3|1||C:3:0|false
-addr|789|3|2||C:3:1|false
+addr|123|3|1||C:3:0|false|false
+addr|789|3|2||C:3:1|false|false
 
-addr|123|5|3|2|C:4:0|false
+addr|123|5|3|2|C:4:0|false|false
 
-addl|123|6|4|5|A:3:0|false
-addl|456|4|3||A:3:1|false
-addl|789|4|3||A:3:2|false
+addl|123|6|4|5|A:3:0|false|false
+addl|456|4|3||A:3:1|false|false
+addl|789|4|3||A:3:2|false|false
 
-addr|456|5|2||B:3:0|false
+addr|456|5|2||B:3:0|false|false
 
-addl|456|7|4|5|A:4:0|false
+addl|456|7|4|5|A:4:0|false|false
 
-addr|456|6|2||C:5:0|false
-addr|123|7|5||C:5:1|false
-addr|123|8|7||C:5:2|false
-addr|789|5|3||C:5:3|false
+addr|456|6|2||C:5:0|false|false
+addr|123|7|5||C:5:1|false|false
+addr|123|8|7||C:5:2|false|false
+addr|789|5|3||C:5:3|false|false
 
-addl|123|9|6|8|A:5:0|false
-addl|456|8|6|7|A:5:1|false
-addl|789|6|4|5|A:5:2|false
+addl|123|9|6|8|A:5:0|false|false
+addl|456|8|6|7|A:5:1|false|false
+addl|789|6|4|5|A:5:2|false|false
 
-addl|123|10|9||A:6:0|false
+addl|123|10|9||A:6:0|false|false
 
 # Devtable state
 setdev|A|A:6,B:3,C:5
diff --git a/runtimes/google/vsync/util_test.go b/runtimes/google/vsync/util_test.go
index 002ab95..263ee30 100644
--- a/runtimes/google/vsync/util_test.go
+++ b/runtimes/google/vsync/util_test.go
@@ -172,7 +172,7 @@
 	if err != nil {
 		return err
 	}
-	if err := s.dag.addNode(rec.ObjID, rec.CurVers, false, rec.Parents, logKey, NoTxID); err != nil {
+	if err := s.dag.addNode(rec.ObjID, rec.CurVers, false, rec.Value.Delete, rec.Parents, logKey, NoTxID); err != nil {
 		return err
 	}
 	if err := s.dag.moveHead(rec.ObjID, rec.CurVers); err != nil {
@@ -205,7 +205,7 @@
 				ObjID:   cmd.objID,
 				CurVers: cmd.version,
 				Parents: cmd.parents,
-				Value:   LogValue{Continued: cmd.continued},
+				Value:   LogValue{Continued: cmd.continued, Delete: cmd.deleted},
 			}
 			if err := populateLogAndDAG(s, rec); err != nil {
 				return err
diff --git a/runtimes/google/vsync/watcher.go b/runtimes/google/vsync/watcher.go
index d470ce0..4d887c3 100644
--- a/runtimes/google/vsync/watcher.go
+++ b/runtimes/google/vsync/watcher.go
@@ -163,8 +163,6 @@
 	w.syncd.lock.Lock()
 	defer w.syncd.lock.Unlock()
 
-	// TODO(rdaoud): handle object deletion (State == DoesNotExist)
-
 	vlog.VI(1).Infof("processChanges:: ready to process changes")
 
 	var lastResmark []byte