Untangling the tangle


Author
Message
Enis Olgac
E
Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)
Group: Forum Members
Posts: 35, Visits: 1.6K
I am the developer of an algorithm, which untangles DAGs.

For short the algorithm generates a topologically sorted list of the edges (projection) of a DAG. Unlike a topological order produced by DSF, the projection preserves connectedness. There are three distinct orders generated based on the projection. Base, Forward, and Backward. Using these orders, the following assertion can be made:

Any two edges of a DAG, say edge(u,v) and edge(x,y), are connected to each other, if and only if edge(u,v) precedes edge(x,y) on each of the Base, and Forward orders, and succeeds on Backward order.

Patent US5878407 is about the "vertex" version of the same. The current "edge" version has some additional properties though:
  • Includes also connectedness of vertices
  • Any of the following can be implemented as a single iteration through projection:
    • Drawing DAG
    • Extracting "vertex induced" subgraph
    • Extracting "edge induced" subgraph
    • Single-Entry-Single-Target partitioning
  • Extracting "Domination Graph"
  • All-Paths challenges
Until now I was using the definition of a complete DAG as input. The way "tangle" is defined to grow, i.e. the tail of the last appended edge (tip), has no predecessor, allows to build and maintain the projection and the related orders incrementally.

As far as I can read from the white-paper, untangling the tangle may be useful in different ways:
  • Performance and simplicity of implementation of functions accessing tangle
  • Creating archives of tangle while preserving its structure
  • Detecting "orphaned" subtangles
  • Drawing the tangle
  • Calculating "weights" and "scores" on the flight
  • Enabling list operations on tangle and subtangles, while respecting the structure of each individual
  • . . .
I am wondering, whether being able to operate on tangle at any scale, and in any direction, can open new perspectives to Dr. Popov and the community?

Edited 9 Months Ago by Enis Olgac
Enis Olgac
E
Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)
Group: Forum Members
Posts: 35, Visits: 1.6K
Untangling of DAGs illustrated (1/2)



This is a sample tree to picture the properties of projection. You see the projection on the left. Edges are topologically sorted, as well as the first appearance of each vertex in the projection. The vertex order on the left (Base) is obtained via a visual top-down, left-to-right depth-first traversal. The vertex order on the right (Forward) is the result of a visual top-down, right-to-left depth-first traversal of sample tree. Furthermore:
  • Base claims 11 may reach 9, and Forward confirms this. So we can conclude that 11 and 9 are connected.
  • Base claims 11 may be reached by 8, but Forward denies this. Reason: 8 does not precede 11 on Forward. The conclusion is 11 and 8 are not connected.
  • Are 7 and 10 connected?  - Yes, and the direction of the connection is from to 10. Reason: 7 precedes 10 on Base and Forward.
  • The ordered vertex set of the subtree induced by 11 is [7, 11, 2, 9]. Select all vertices are connected to 11.
You are missing Backward, because tree is a planar dag. Planar dags are by definition two dimensional, and connectedness do not need a third arbitrator.
For the sake of completeness here is a sample of a planar dag.



Enis Olgac
E
Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)
Group: Forum Members
Posts: 35, Visits: 1.6K
Untangling of DAGs illustrated ( 2/2 )

If a DAG is non-planar, we need a third order (Backward) as the last arbitrator (a DAG has at most three dimensions). The reason is a crossing edge on the xy-plane (an indication of being non-planar).



Base and Forward claim 10 to be reachable from 8. Backward is there to deny this claim (8 does not succeed 10 on Backward). It is also a good exercise to determine the ordered vertex set induced by 8, which is [7, 3, 8, 9].

Another interesting property of projection is the wait-and-go behavior of the edges it contains. Before edge (2, Ø) is appended to projection (go), all its direct or indirect ascendants are inserted (wait). You can observe this phenomena throughout projection. An edge is appended as-soon-as-possible, but it is delayed as-long-as-needed.

Enis Olgac
E
Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)
Group: Forum Members
Posts: 35, Visits: 1.6K
Untangling the tangle

Following image shows "Figure 2" of the whitepaper including its projection,



and its three vertex orders.



At a first glance, something seems to be buggy. The Backward order is the inverse of the Base order, i.e. they contain the same information as far as connectedness is concerned. This would imply that the tangle in "Figure 2" must be planar, but obviously it isn't. Do we have a bug? For sure not. The algorithm, while computing the vertex orders, ignores redundant edges. For example both edge (B,F) and path (B,D).(D,F) tells us that B and F are connected. So the edge (B, F) is redundant. The simplified vertex oriented perspective of the tangle is given in the next figure:



Now the simplified tangle, equivalent to the perspective of the algorithm, is planar, and Base and Forward orders are sufficient to determine the topology of the tangle. The removed edges wouldn't be redundant, if we choose the edge oriented perspective of the tangle, though. This is a crucial difference concerning the semantics of the tangle, and is the subject of the next post.
  


Serguei Popov
S
Attached to Tangle (347 reputation)
Group: Forum Members
Posts: 9, Visits: 22
Do you have any peer-reviewed publications on this subject?

Enis Olgac
E
Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)
Group: Forum Members
Posts: 35, Visits: 1.6K
Serguei Popov - 18 Dec 2017
Do you have any peer-reviewed publications on this subject?

Unfortunately not, unless you would consider a patent script as such. The current algorithm is an enhanced version of the one described in patent script published in 1995. It is based on depth-first and breadth-first traversal, uses only dependencies defined by the edges of the graph. The breadth-first traversal differs from the one described in wikipedia and is my invention. 
Edited 9 Months Ago by Enis Olgac
Enis Olgac
E
Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)
Group: Forum Members
Posts: 35, Visits: 1.6K
Computing cumulative weights and scores

Now we will use Base and Forward orders to compute cumulative weight and score of a vertex (transaction).
First recall simplified drawing of "Figure 2":

... the cumulative weight of a transaction: it is defined as the own weight of a particular transaction plus the sum of own weights of all transactions that directly or indirectly approve this transaction.
and 
... By definition, the score of a transaction is the sum of own weights of all the transactions approved by this transaction plus the own weight of the transaction itself.

These definitions from the whitepaper can be executed to find the cumulative weight, and score of vertex as:
  • for each vertex u on Base in order until vertex v is reached
    • if vertex u precedes vertex v on Forward, i.e. u approves v directly or indirectly, add own weight of u to cumulative weight of v
  • add own weight of v to cumulative weight of v, and to score of v
  • continue with each vertex w on Base until Base is exhausted
    • if vertex w succeeds vertex v on Forward, i.e. w is approved by v directly or indirectly, add own weight of w to score of v


Enis Olgac
E
Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)
Group: Forum Members
Posts: 35, Visits: 1.6K
Computing heights and depths and How wide is the tangle?

Today we will compute the height and depth of a transaction (vertex) as they are defined in the whitepaper:
... for a transaction site on the tangle, we introduce its
  • height: the length of the longest oriented path to the genesis
  • depth: the length of the longest reverse-oriented path to some tip
and also, we will give an answer to how wide the tangle is.
Again here is the tangle, just in case you would like to verify the process below:

Process for depths:
  • for each edge e in projection until projection is exhausted
    • set depth of head of e to (depth of head of e or depth of tail of e plus 1) whichever is greater
Process for heights:
  • reverse projection
  • for each edge e in reversed projection until reversed projection is exhausted
    • set height of tail of e to (height of tail of e or height of head of e plus 1) whichever is greater
Process for width of the tangle:
  • paint vertices to green
  • for each edge e in projection until projection is exhausted
    • if tail of e is green
      • paint tail of e to red
      • add 1 to width at depth of tail of e
      • if depth of tail of e is greater than 1, set width of tangle to (width of tangle or width at depth of tail of e) whichever is greater
The width at depth 1 is equal to the number of tips.

I think the number of transaction sites at the same depth is a good measure for the width of the tangle.
The processes, depths and width, can be merged, such that only one pass along the projection will be sufficient for the computation.






Edited 9 Months Ago by Enis Olgac
Enis Olgac
E
Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)
Group: Forum Members
Posts: 35, Visits: 1.6K
Summary

In earlier posts, I presented a data-structure, called projection, which encodes two aspects of a DAG:
  1. Topology: Whether any two vertices of a DAG are connected or not
  2. Structure: How does the connection between two vertices of a DAG look like
Now, I will discuss the cost of generating, maintaining, and using the projection of tangle.

Cost of generation:

Generating the projection of a snapshot of tangle, which is a DAG whose vertices are:
  • A distinguished transaction Genesis, with no successor
  • Any number of transactions with two (not necessarily distinct) successors, and any number of predecessors
  • any number of tips, transactions with at most two successors and no predecessors
 consists several steps:
  1. Generate an ordered list of edges of tangle O(|V| + |E|)
  2. Remove those edges which are redundant O(|V| + |E|)
  3. Generate projection of tangle O(|V| + O|R|)
  4. Generate Base O(|R|)
  5. Generate Forward O(|V| + |R|)
  6. Generate Backward O(|V| + |R|)
where |V| denotes the number of vertices (transactions), and |E| the number of edges in tangle. |R| is the number of edges of the reduced tangle, tangle after removing its redundant edges.

Cost of maintenance:


Tangle grows with tips. Tips have no predecessors, and either one or two successors. Therefor adding a tip to tangle costs at most two insertions to projection. O(1)

Cost of usage:

Once the projection is generated, it can be used whenever the knowledge about topology and structure of tangle is of interest. In general, cost of a query about the topology of tangle alone, i.e. a query whether two transactions are connected or not, will be O(1).
If the knowledge about the structure of tangle is needed, projection can replace the otherwise necessary traversal of tangle, reducing the cost from O(|V| + |E|) to O(|R|). For example:

  • Calculating cumulative weight and score of a transaction
  • Calculating height of all transactions
  • Calculating depth of all transactions
  • Calculating width of tangle and number of tips

Edited 9 Months Ago by Enis Olgac
Enis Olgac
E
Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)Attached to Tangle (715 reputation)
Group: Forum Members
Posts: 35, Visits: 1.6K
Conclusion ( 1/3 )

The Tangle, backbone of IOTA, is a DAG. Its vertices are "sites", which are "transactions" issued by nodes and revealed to tangle. Its edges are relations, called approval, where the tail of an edge said to "approve" the head, and the head is said to be "approved by" the tail. A site newly added to tangle has no predecessor, i.e. it is not yet approved by any other site, and is called a tip. Upon entering tangle, a tip approves one or more sites (in the current implementation of IOTA mostly two sites). Furthermore, four attributes are defined to describe position of a site within the tangle.
  • Cumulative Weight: The own weight of a site plus the sum of own weights of all sites that directly or indirectly approve this site. This attribute changes its value as tangle grows.
  • Score: The sum of own weights of all sites approved by this site plus the own weight of the site itself. This attribute, once calculated, remains constant for the life time of tangle.
  • Height: The length of the longest oriented path to the genesis.
  • Depth: The length of the longest reversed oriented path to some tips.
I believe, this is the complete information about tangle, as a DAG. Before I go into some details, I should mention an observation.

Unfortunately, a topological order of the tangle is a temporal order of sites, and not of transactions. Therefor it is not possible to compute a temporally ordered ledger of transactions simply by topologically sorting the tangle. The reason is rather unspectacular; a tip which is introduced relatively late to tangle, may be selected earlier than others for approval (Note: I was not able to find any restriction in the white paper which would prevent this case). Discovering the temporal order of transactions out of tangle can be an expensive journey, especially when tangle has to grow like several thousand transactions per second. As far as I know, this is a requirement of a formal accounting process, though.

GO

Merge Selected

Merge into selected topic...



Merge into merge target...



Merge into a specific topic ID...




Reading This Topic

Login

Explore
Messages
Mentions
Search