diff --git a/htrace-core/src/main/java/org/apache/htrace/Span.java b/htrace-core/src/main/java/org/apache/htrace/Span.java
index c6ec37b..71ed872 100644
--- a/htrace-core/src/main/java/org/apache/htrace/Span.java
+++ b/htrace-core/src/main/java/org/apache/htrace/Span.java
@@ -30,8 +30,9 @@
  * Base interface for gathering and reporting statistics about a block of
  * execution.
  * <p/>
- * Spans form a tree structure with the parent relationship. The first span in a
- * trace has no parent span.
+ * Spans should form a directed acyclic graph structure.  It should be possible
+ * to keep following the parents of a span until you arrive at a span with no
+ * parents.<p/>
  */
 @JsonSerialize(using = Span.SpanSerializer.class)
 public interface Span {
@@ -67,7 +68,10 @@
   String getDescription();
 
   /**
-   * A pseudo-unique (random) number assigned to this span instance
+   * A pseudo-unique (random) number assigned to this span instance.<p/>
+   *
+   * The spanId is immutable and cannot be changed.  It is safe to access this
+   * from multiple threads.
    */
   long getSpanId();
 
@@ -86,12 +90,20 @@
   String toString();
 
   /**
-   * Returns the parents of the span.
+   * Returns the parent IDs of the span.<p/>
+   *
    * The array will be empty if there are no parents.
    */
   long[] getParents();
 
   /**
+   * Set the parents of this span.<p/>
+   *
+   * Any existing parents will be cleared by this call.
+   */
+  void setParents(long[] parents);
+
+  /**
    * Add a data annotation associated with this span
    */
   void addKVAnnotation(String key, String value);
diff --git a/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java b/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java
index 9babfc1..9956ddb 100644
--- a/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java
+++ b/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java
@@ -54,7 +54,7 @@
   private long end;
   private final String description;
   private final long traceId;
-  private final long parents[];
+  private long parents[];
   private final long spanId;
   private Map<String, String> traceInfo = null;
   private final String processId;
@@ -220,6 +220,11 @@
   }
 
   @Override
+  public void setParents(long[] parents) {
+    this.parents = parents;
+  }
+
+  @Override
   public long getTraceId() {
     return traceId;
   }
diff --git a/htrace-hbase/src/test/java/org/apache/htrace/impl/TestHBaseSpanReceiver.java b/htrace-hbase/src/test/java/org/apache/htrace/impl/TestHBaseSpanReceiver.java
index 79d6e9b..7bf7bac 100644
--- a/htrace-hbase/src/test/java/org/apache/htrace/impl/TestHBaseSpanReceiver.java
+++ b/htrace-hbase/src/test/java/org/apache/htrace/impl/TestHBaseSpanReceiver.java
@@ -20,6 +20,7 @@
 import java.io.ByteArrayInputStream;
 import java.io.IOException;
 import java.io.InputStream;
+import java.lang.UnsupportedOperationException;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
@@ -155,6 +156,11 @@
     }
 
     @Override
+    public void setParents(long[] parents) {
+      throw new UnsupportedOperationException();
+    }
+
+    @Override
     public long getStartTimeMillis() {
       return span.getStart();
     }