If two requests arrive at an arbiter within a few picoseconds (today, femtoseconds) of each other, the circuit may become meta-stable before reaching one of its stable states to break the tie.
The probability of not having reached a stable state decreases exponentially with time after inputs have been provided.
Although an arbiter that makes a decision in a fixed time is not possible, one that sometimes takes a little longer in the hard case (close calls) can be made to work.
The classic paper is [Kinniment and Woods 1976], which describes how to build a "3 state flip flop" to solve this problem, and [Ginosar 2003], a caution to engineers on common mistakes in arbiter design.
Some early multiprocessors with independent clocks for each processor suffered from arbiter race conditions, and thus unreliability.
Arbiters are used in synchronous contexts as well in order to allocate access to a shared resource.