When a node rejoins after a restart, have all other nodes drop any pending transactions initiated by the node in question. I implemented something similar for a distributed filesystem and it worked pretty well.