@mix Any (non-garbage) cypherlink in any ssb message establishes a happens-before relation. Most messages in the current social networking applications include cypherlinks. Building the partial order won't be a problem, and it is unlikely that it will be too sparse either.

By adding cypherlinks as a dedicated logical datatype, checking messages for them will become very easy - with wort-case time complexity linear in the message size (with far better constants than would currently be required), and a lot faster in the average case where you get to skip a lot of data of differing types.

Implementation of causal order in sbot would be a great way for anyone to contribute to the current push to renew the protocol #somebodyshould. The causal order is simply the reachability relation on the directed graph obtained by treating ssb messages as nodes and cypherlinks as directed edges. The linked wikipedia article mentions a few algorithms, and there should be a ton of literature out there. The implementation can stay fairly simple (without changing the database representation), but in the future it might be worth considering to adapt the db to allow constant-time lookup/computation.

Fun fact: Combining the causal order aka reachability relation with some sort of tiebreaker yields a topological sorting (which is a total order).

Computing the causal order is another of those things where all the thinking has already been done for us. Moving to a db with constant-time reachability lookup will be some work, but might be worth it. But it is not required to so before we roll out causal order sorting in sbot, there are less sophisticated but still sufficently performant algorithms.

CC @arj, @cryptix and @keks for database related thoughts. You might want to keep this in mind for the go implementation.