Linux distros do have a nfslock service that can be started. The local and remote computer communicate via rpc and you should be able to use flock like normal. How to set it up though is another matter (I have little idea -- only that on RedHat it is a default installed service).

As for File::NFSLock... it may be clunky and possibly has bugs in the stale lock time out, but we've hit it with over ten million hits a day on our web cluster (tied to our data cluster via nfs) and we have not had a single problem with inaccurate locking. So - the extras might not work in your situation, but the down and dirty functionality will work.

my @a=qw(random brilliant braindead); print $a[rand(@a)];