0
$\begingroup$

(Short discaimer: I'm a mathematician by education (category theory, algebraic geometry) and so mostly unaware of how different fields in CS relate to each other. I'd be very happy to just get some directions. Also I'm not sure if the tags I added to the question are all correct.)

My question is concerned with information in distributed systems in relation to time. And I guess it also goes into the direction of blockchains.

Question: Is there research that deals with something along the lines of the following class of structures?

  • The core items are triples (i, t, p) where i is a piece of information (think string, JSON blob, etc.), t is a "point in time" and p is a proof that we interpret as "i existed after t".
  • A relation ~< on all t where t1 ~< t2 is interpreted as t1 was before t2. (I'm not requiring that this relation is a linear order at this point. Not even that it's transitive or antisymmetric. But I guess it should at least be reflexive).
  • Some check is_legit(i, t, p) that tells us if p actually is a correct proof of "i existed after t".
  • Additionally, some form of algebraic structure: Given two such triples (i1, t1, p1) and (i2, t2, p2) we'd want to build a new triple 
    ( i1, shared_past(t1, t2), combined_proof(p1, p2, i2))
    with the property that firstly t1 ~< shared_past(t1, t2) and t2 ~< shared_past(t1, t2) and secondly that the new triple is_legit if and only if the two inputs are legit.

Clearification: I don't expect the definition above to be the correct one. Rather, I hope it outlines the flavour of things I'm interested in.

Improve this question
$\endgroup$
7
  • $\begingroup$ But what is your question ?? $\endgroup$
    – user16034
    Sep 19, 2022 at 12:22
  • $\begingroup$ @YvesDaoust I've updated the post to mark the question more clearly. $\endgroup$
    – Gerrit Begher
    Sep 19, 2022 at 12:41
  • $\begingroup$ I don't understand what your shared_past() thing is or why you think that an unrelated triple (i2, t2, p2) give you any reason to believe that i1 existed earlier than previously known. Some motivation seems missing. Rather than telling us "is there any solution that looks something like the following?", could you tell us what is the problem you are trying to solve? $\endgroup$
    – D.W. ♦
    Sep 19, 2022 at 18:38
  • $\begingroup$ The initial problem I had in mind is "blockchains in space": My intuition would be that (due to relativity) at large distances, consensus can not be achieved for all nodes within a reasonable time limit. And so it might not be reasonable to even try it. Rather my idea was that every information comes with it's own temporal frame of reference and whenever two such pieces of information "meet", they can update by forming a shared past. $\endgroup$
    – Gerrit Begher
    Sep 19, 2022 at 19:34
  • 1
    $\begingroup$ @GerritBegher, got it. I updated my answer to include one more reference/phrase that might be helpful and interesting to you. $\endgroup$
    – D.W. ♦
    Sep 20, 2022 at 3:15

1 Answer 1

Reset to default
1
$\begingroup$

The happened-before relation is a standard mathematical tool for reasoning about time ordering of events in distributed systems. You can find a lot of development on foundations of it, tools for tracking it, and systems built on this concept.

Timestamping is one way to prove that information existed at a certain period of time. You can trawl through https://crypto.stackexchange.com/questions/tagged/timestamping and https://security.stackexchange.com/questions/tagged/timestamp to find some research on that. This might be one way to implement the "proof" notion you are looking for.

Lastly, you might be interested in "timeline entanglement" - that might be exactly what you are looking for, in merging two different timelines/events/histories.

Combining those two might give a starting point towards what you are hoping for; or a foundation and a language for expressing what properties you want from a scheme.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.