Hi! I'm new here, a terrible computer-scientist, and have no idea what I'm doing; I'm more expecting / hoping for links to research on algorithms or data-structures that contribute to problems like this, than a straightforward answer (I don't even know how to properly ask the question.)

In some programming-language work of mine, I've got a ginormous, homogenous, directed graph, on disjoint subgraphs of which multiple actors operate concurrently.

One such operation is to add an element to an ordered set, supplicants, on a given node (it's a behaviour to declare “I'm waiting for write-access to this structure”, basically.) That membership is cascaded through the graph to some extent (i.e. adding an element to $a$'s supplicants, when $a⇸b$, places that same element in $b$'s supplicants as well.)

Now, normally, in my situation, the above bit where these two subgraphs are disjoint is guaranteed — at the time. However, there's an edge case¹ where two such subgraphs both have different values added to supplicants while disjoint, and are then joined. In this situation, I'm not sure how to deterministically order the two sets of supplicants amongst one-another.

I've heard of things like vertex clocks that I'd hoped might help with this, but after looking into it a bit today, none of the mechanisms I'm aware of are very helpful in this situation. The actors are unaware of eachother working ‘adjacently’ (or soon-to-be-adjacently, when they're joined). To make them aware of eachother would defeat the point (i.e. if participant $\text{foo}$ had to walk over (all|most) of the graph leaving supplicants hints that currently-working-disjoint-but-maybe-someday-not participants could find, and order themselves against, would be as pointless as just having a single globally-locked set shared amongst all threads); so I'm looking for some sort of lockless algorithm or distributed-systems solution for them to collaborate without(?) explicit communication.

  1. (i.e., all of programming. :P)
  • 1
    $\begingroup$ What exactly is the requirement on the joined ordering? Is just determinism enough (i.e. any new ordering is fine, as long as it's consistent with the old orderings and deterministic)? Can the elements have some kind of globally unique ids, which could be used for the new ordering? $\endgroup$ – svick Jun 25 '17 at 11:39
  • $\begingroup$ Do you have synchronized clocks among all of the machines? Can you use a timestamp? With GPS in some cases it's reasonably feasible to get extremely precise time synchronization. $\endgroup$ – D.W. Jun 25 '17 at 17:27
  • $\begingroup$ I don't think I can dictate the latter — this is intended to be a distributed system, which can be embedded in lots of other pieces of software or run on lots of diverse systems; $\endgroup$ – ELLIOTTCABLE Jun 29 '17 at 14:02
  • $\begingroup$ As for the former, the goal is to achieve input-order (i.e. if mutator-A adds an item first, it should be represented first in supplicants.) — but anything deterministic would be a step up, I think, right now. And all items do have GUIDs, although those are defined elsewhere and not ordered in any way, $\endgroup$ – ELLIOTTCABLE Jun 29 '17 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.