0
$\begingroup$

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):
      output.push(v)
  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.

$\endgroup$

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.