For various collective-epistemics and cooperative-decision-making endeavours, I think a key technical enabler might be DVCS for structured data. To that end, I am interested in funding work in this direction. Aside from being in a position to allocate some funding, I think I have some comparative advantage in a broad inside-view awareness of potentially relevant theoretical footholds, and this post is intended to start unfurling that inside view, initially as a list of links. People who I fund to work on this should read the abstracts of all of these papers, pay special attention to those marked with (!), skim/read further as they see fit, and cite them in their writeups (at least under “related work”). I’m posting this here as part of a general policy of using this platform for any of my even-vaguely-technical output that goes beyond tweets.
This paper describes the theory and implementation of an operation (double-pushout-rewriting a.k.a. DPO-rewriting) on a data model (C-sets) which is what I’m currently most excited about exploring as a notion of “patch” (or “commit”) in DVCS of structured data.
(!) One specific type of structured data I’m particularly interested in applying the proposed work to is hypernets, a combinatorial representation of string diagrams, defined alongside a double-pushout-rewriting scheme for them in section 4 of Functorial String Diagrams for Reverse-mode Automatic Differentiation. Ideally, this should be a special case of the above.
Another one I’m interested in is Polynomial Circuits, which can be represented as hypernets.
This paper introduces a consistency criterion that is weak enough to be satisfied by most CRDTs, but stronger than mere eventual consistency. I would expect any DVCS to probably satisfy this criterion.
This short paper outlines some simple, git-like mechanisms for rejecting invalid messages that I would want to see in basically any decentralized system.
I would like the system to support incremental updating of the outputs of functions defined on the structured data (a.k.a. “views” in the database sense), and I think this paper describes a good building block for that. I have flagged it for special attention because I want compatibility with the Datalog model to be in the back of our minds as we make design decisions.
This is an alternative data-model where database states are functors from C→Rel instead of functors from C→Set. This is in some ways closer to the relational database model, so there might be some interest in generalizing the C-Set DPO algorithm to “C-Rel”s. However, morphisms in Rel can be represented as spans in Set, and that’s probably easier.
For various collective-epistemics and cooperative-decision-making endeavours, I think a key technical enabler might be DVCS for structured data. To that end, I am interested in funding work in this direction. Aside from being in a position to allocate some funding, I think I have some comparative advantage in a broad inside-view awareness of potentially relevant theoretical footholds, and this post is intended to start unfurling that inside view, initially as a list of links. People who I fund to work on this should read the abstracts of all of these papers, pay special attention to those marked with (!), skim/read further as they see fit, and cite them in their writeups (at least under “related work”). I’m posting this here as part of a general policy of using this platform for any of my even-vaguely-technical output that goes beyond tweets.
(!) A Categorical Theory of Patches
(!) The CALM Theorem: When Distributed Consistency is Easy
Weaker Forms of Monotonicity for Declarative Networking: A More Fine-Grained Answer to the CALM-Conjecture
Logic and Lattices for Distributed Programming
(!) Double-pushout-rewriting of C-sets
This paper describes the theory and implementation of an operation (double-pushout-rewriting a.k.a. DPO-rewriting) on a data model (C-sets) which is what I’m currently most excited about exploring as a notion of “patch” (or “commit”) in DVCS of structured data.
(!) One specific type of structured data I’m particularly interested in applying the proposed work to is hypernets, a combinatorial representation of string diagrams, defined alongside a double-pushout-rewriting scheme for them in section 4 of Functorial String Diagrams for Reverse-mode Automatic Differentiation. Ideally, this should be a special case of the above.
Another one I’m interested in is Polynomial Circuits, which can be represented as hypernets.
A Generalized Concurrent Rule Construction for Double-Pushout Rewriting
Describes when DPO rewrite rules are compatible in the sense that they can be merged into a single concurrent rule.
Replication-Aware Linearizability
This paper introduces a consistency criterion that is weak enough to be satisfied by most CRDTs, but stronger than mere eventual consistency. I would expect any DVCS to probably satisfy this criterion.
(!) Making CRDTs Byzantine Fault Tolerant
This short paper outlines some simple, git-like mechanisms for rejecting invalid messages that I would want to see in basically any decentralized system.
(!) Fixing incremental computation: Derivatives of fixpoints & the recursive semantics of Datalog
I would like the system to support incremental updating of the outputs of functions defined on the structured data (a.k.a. “views” in the database sense), and I think this paper describes a good building block for that. I have flagged it for special attention because I want compatibility with the Datalog model to be in the back of our minds as we make design decisions.
Knowledge Representation in Bicategories of Relations
This is an alternative data-model where database states are functors from C→Rel instead of functors from C→Set. This is in some ways closer to the relational database model, so there might be some interest in generalizing the C-Set DPO algorithm to “C-Rel”s. However, morphisms in Rel can be represented as spans in Set, and that’s probably easier.
Datalog: Bag Semantics via Set Semantics
Algebraic Property Graphs
Concise, Type-Safe, and Efficient Structural Diffing