You looking for a triple modular redundancy http://en.wikipedia.org/wiki/Triple_modular_redundancy
it actually takes more than three units.
Standard microcontroller watchdog integrated circuits will read a pulse from the microcontroller and this resets the watchdog counter to zero. You can do that with a dedicated circuit or if you need some repeatability and precision I'd do it with a microcontroller. See the rant below.
Since the Arduino was probably not built with the highest rated parts for military and aerospace applications and not made to class three soldering specifications you are constrained in testing units to see if they have some chance of surviving.
One of the simplest things you can do is to us one of the Arduino variants that use no socketed parts and then conformal coat the board excluding connectors or areas that need to be soldered later.
The other is to run them across the temperature range they will be exposed to and see if they fail and if possible make corrections to the board or supply environmental controls to keep the temperature where they can survive. Thermal cycling usually kills solder connections but can kill components not rated for it.
The voting system can actually be a rigorously tested Arduino. It can also act as a watchdog for the other systems. You'd want an external watchdog on it to reboot it if needed. I'd be tempted to use an ATTINY as a watchdog rather than the available dedicated watchdog integrated circuits. That is due to the following experience.
.rant. I've worked with the Dallas external watchdog integrated circuit. DS1232. I can't spit on it hard enough to kill the engineer that built this piece of *t. It has no consistency across temperature, it has no consistency between parts and if you get one batch to work the next batch you buy might not. All of the clones made by other vendors of this chip have the exact same problems. That was their DIP8 part, their surface mount part is just as bad when I tried it. Instead of redesigning the system or touching the firmware which would cost us 10s of thousands of dollars we hand select parts that work. ./rant.