I'm quite intrigued by this - is there ever any algorithm where you wouldn't want full consistency? I would expect that if you are modifying data that you would want full consistency to ensure correctness. If you have vertex consistency and two adjacent vertices write to the same edge don't we have a problem there?
bob_sacamano
There are many situations (especially in convergence-based iterative algorithms) where the partially-consistent approximate solution is fine, if we get great performance gains by relaxing consistency requirements. The rationale for assignment 3 and assignment 4 were similar - we used simulated annealing to improve our likelihood of finding the globally optimal solution. Across different runs of the program, we used to get marginally different results that were within an acceptable ballpark. With the relaxed consistency constraints given to us by the course staff, we could improve the speedup by working with partially stale data. In the end, the tradeoff between performance and consistency is application-dependent.
carnegieigenrac
@cloudhary: An example where edge consistency would be trivially sufficient would be one where vertices only read and write from their adjacent edges, and not their adjacent vertices. Vertex consistency would also be fine if vertices don't write to their edges. However, these looser constraints may still be appropriate in scenarios where 0 correctness isn't necessary, such as in assignments 3 and 4 as bob_sacamano mentioned.
I'm quite intrigued by this - is there ever any algorithm where you wouldn't want full consistency? I would expect that if you are modifying data that you would want full consistency to ensure correctness. If you have vertex consistency and two adjacent vertices write to the same edge don't we have a problem there?
There are many situations (especially in convergence-based iterative algorithms) where the partially-consistent approximate solution is fine, if we get great performance gains by relaxing consistency requirements. The rationale for assignment 3 and assignment 4 were similar - we used simulated annealing to improve our likelihood of finding the globally optimal solution. Across different runs of the program, we used to get marginally different results that were within an acceptable ballpark. With the relaxed consistency constraints given to us by the course staff, we could improve the speedup by working with partially stale data. In the end, the tradeoff between performance and consistency is application-dependent.
@cloudhary: An example where edge consistency would be trivially sufficient would be one where vertices only read and write from their adjacent edges, and not their adjacent vertices. Vertex consistency would also be fine if vertices don't write to their edges. However, these looser constraints may still be appropriate in scenarios where 0 correctness isn't necessary, such as in assignments 3 and 4 as bob_sacamano mentioned.