In this paper we present the first detailed analysis of von Neumann multiplexing (vN-MUX) using majority (MAJ) gates of small fan-ins Δ (MAJ-Δ) with respect to the probability of failure of the elementary (nano-)devices. Only gates with small fan-ins have been considered, as gates with large fan-ins do not seem practical (at least in the short term) in future technologies. The extensions from an exact counting algorithm (for gate defects and faults only) to device-level failures will allow us to estimate and characterize MAJ-Δ vN-MUX with respect to device-level malfunctions. The reported results depart significantly from all known gate-level analyses-either theoretical or based on simulations. These should be quite important as providing a detailed picture of the behavior of MAJ-Δ vN-MUX when considering the (unreliability of the elementary (nano-)devices (as opposed to gate-level only analyses). The main conclusion is that small fan-in gates (and redundancy schemes relying on such gates) are quite promising-in spite of all previous results at gate-level showing the contrary.