According to FHS-3.0, /tmp is for temporary files and /run is for run-time variable data. Data in /run must be deleted at next boot, which is not required for /tmp, but still programs must not assume that the data in /tmp will be available at the next program start. All this seems quite similar to me.

So, what is the difference between the two? By which criterion should a program decide whether to put temporary data into /tmp or into /run?

According to the FHS:

Programs may have a subdirectory of /run; this is encouraged for programs that use more than one run-time file.

This indicates that the distinction between "system programs" and "ordinary programs" is not a criterion, neither is the lifetime of the program (like, long-running vs. short-running process).

Although the following rationale is not given in the FHS, /run was introduced to overcome the problem that /var was mounted too late such that dirty tricks were needed to make /var/run available early enough. However, now with /run being introduced, and given its description in the FHS, there does not seem to be a clear reason to have both /run and /tmp.