Previous vs. concurrent/independent work

Should Paper X cite Paper Y as previous or concurrent/independent work? This is sometimes tricky: maybe Paper Y circulated privately before Paper X, maybe the authors of Paper X knew about Paper Y maybe not — nobody can know for sure. One can say that the authors of Paper Y should have posted Paper Y online earlier to prevent this issue, but that is not standard practice and might lead to other problems, including Paper Y never getting published!

I propose the following guiding principle:

“If a different accept/reject outcome would have forced paper X to cite paper Y as previous work, then paper X should cite paper Y as previous work.”

The reasons behind my principle seem to me especially valid in the fast-moving theoretical computer science community, where papers are typically sent to conferences and thus seen by the entire program committee plus around 3 external referees, who are typically experts — only to be rejected. Moreover, the progress is extremely fast, with the next conference cycle making obsolete a number of papers in just the previous cycle.