Directed Graphs, Data-Flow, and Distributed Ledgers


Author
Message
Enis Olgac
E
IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)
Group: Forum Members
Posts: 40, Visits: 1.7K
This is the title of an article I have just published. Hope you will enjoy reading it. Here is the link:
Directed Graphs, Data-Flow, and Distributed Ledgers



Enis Olgac
E
IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)
Group: Forum Members
Posts: 40, Visits: 1.7K
And here is an excerpt from abstract for your convenience:

...

The system proposed in this paper is a value transfer system with its distributed, decentralized, immutable, and extensible ledgers. It leans on the principles of real existing transaction recording systems (double-entry bookkeeping), which make use of ledgers. These systems are distributed. They are decentralized, if the artificial requirement for trusted parties, who are privileged to assign Ids to individual accounts, are removed. They are immutable, and for sure extensible. Fraud is only possible at the cost of very heavy crime. The introduced system includes a process to prove ownership of accounts, making a central authority superfluous. Immutability is guaranteed by allowing “append” as the only operation to modify a ledger.

Enis Olgac
E
IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)
Group: Forum Members
Posts: 40, Visits: 1.7K
Added section "Generalized Ledgers"

Here is a short excerpt:

... But care is in order; any generalization should not sacrifice the two main principles of being a ledger (an ordered list of transactions), by no means. These principles are:
1. One ledger per account, and one account per ledger
2. Preserving the relative order of entries as they occurred
Otherwise the resulting data-structures would be anything but a ledger


the same link to article

Enis Olgac
E
IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)
Group: Forum Members
Posts: 40, Visits: 1.7K
The story "Tangle" is telling us?

Every “Directed Graph” tells a story. Subject-Predicate-Object is the combination of three words from which any sentence in a directed graph is formed. Subject, and object are vertices. Predicate the edge. Each sentence can be interpreted standing alone (as is), where:
•    Subject is the person or a thing who or which carries out the action of the verb
•    Object is the person or a thing upon whom or upon which the action of the verb is carried out.
•    Predicate is what tells about what a person or a thing does or did or what happened to a person or to a thing.(source: English for students)
The sentences are linked by referring to subjects and/or objects in more than one sentence. There exists only one rule how a chain (path) of sentences can be interpreted to have a meaning, the rule of transitivity. The rule is defined as:
If two sentences are linked by referring to the object of the first as the subject of the second, the same predicate applies to the sentence build by subject of the first, and the object of the second.

That’s all the theoretical knowledge we need in order to understand what a directed graph is telling us. What is “Tangle” telling us? As defined in the white paper a sentence in tangle has the form:
Bundle has selected Tip as its predecessor according to "Tip Selection Algorithm"
I used bundle instead of a transaction, because “IOTA Reference Implementation” (IRI) had to introduce bundles of transactions as a design patch. This is the consequence of the “Tip Selection Algorithm”, where transactions which ought to run in sequence cannot be guaranteed to do so.(see also my related post)
 
That’s it, no more no less. Bundles are not related by any other means. As a consequence, the assertion “Bundle does confirm that tip doesn’t double spend (doesn’t use its assets improperly)” cannot be reused (it is not a relation in tangle, let alone be transitive). Therefore, a search on the history of an account is likely to become a blind walk, may be ending up traversing the complete tangle, each time a confirmation is required. Augmenting vertices and/or edges with flags and parameters will be inevitable design patches to overcome challenges arising during implementation. But doing so, one would be deviating from basic principles of directed graphs paving the way for more proprietary interpretations of tangle.

Enis Olgac
E
IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)IOTAn Pending (1.2K reputation)
Group: Forum Members
Posts: 40, Visits: 1.7K
Extended Abstract

I published an extended abstract (https://www.researchgate.net/publication/326461478_Structure_of_Directed_Acyclic_Graphs) of an upcoming article which will discuss the algorithm to extract the structure, i.e. organization and connectedness, of a directed acyclic graph.

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