[Networkit] [review][patch] vertex diameter computation

Matteo Riondato matteo at cs.brown.edu
Thu Sep 24 02:30:44 CEST 2015


Hi all,

The attached patch is meant to solve a potential race in writing to vd. Specifically, as the code is now in Dev, the following race can happen:

Assume that at some point vd is 20, thread1 has maxDist + maxDist2 equal to 22, and thread2 has maxDist + maxDist2 equal to 21.

Both thread1 and thread2 enter the block guarded by "if (maxDist + maxDist2 > vd)”.
At this point, we may have that thread1 updates vd to 22, and then thread2 updates vd to 21.
Hence the value stored in vd is not correct.

The patch solve the issue by using a reduction on vd.

I haven’t seen the race in practice, but I believe the patch is needed for correctness.

I’d love a review before I commit it to Dev. Thanks in advance.

Matteo

-------------- next part --------------
A non-text attachment was scrubbed...
Name: Diameter.cpp.diff
Type: application/octet-stream
Size: 813 bytes
Desc: not available
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150923/f4fe30c8/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 163 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150923/f4fe30c8/attachment.sig>


More information about the NetworKit mailing list