I have a set of version vectors (or vector clocks) and need to implement a filter function that takes this set and returns a new set where all elements are either "equal", "happened after", "concurrent" to every element in the original set.

I have a rather crude implementation that does this in O(n^2*k) (where n is the size of the input set and k is the number of entries in each version vector), but was wondering if I can do better. Pseudo code:

def is_predecessor_in(candidate, vv_set):
  for vv in vv_set:
    if candidate.happens_before(vv):
      return True
  return False

def filter(input):
  let output = []
  for v in input:
    if !is_predecessor_in(v, input):
  return output

Additionally, if someone could recommend a resource for algorithms with version vectors (or vector clocks) such as this one, that would be greatly appreciated.



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.