Something to keep in mind if you are inclined to try solving the puzzle is that solutions ought to work on NFS file systems. Why does that matter?
Well, consider a system call like rename(2) or mkdir(2). Suppose that on a local file system, two programs both try to rename "a" to "b" at roughly the same time. At most one will succeed.
Not so, on NFS! An NFS implementation is permitted to behave this way: (1) Client x issues the rename request; (2) Client y issues the same rename request; (3) The server reports "success" to x; (4) The server reports "fail" to y, but the server's report packets get lost so y doesn't get the message. (5) Client y asks the server "Hey, whatever happened to my rename request?"; (6) Server notices that "a" doesn't exist but "b" does and replies "Success". Then both x and y think that they renamed "a" to "b".
The rename itself took place atomically. It's just unclear to each client which client actually triggered the rename. Similarly for other operations.
In other words, return values from file system calls don't reliably tell you when your process was able to perform some atomic action.