Here's how I calculate hold up. Start with an equation that determines energy in terms of voltage and capacitance. Then solve for C.
E = (1/2 C * Vstart^2 - 1/2 C * Vdropout^2)
For the algebra challenged, here's the steps broken down to solve for C.
1. Take your circuit's current times the circuit's voltage, to get Power (then double it)
P = 2x (Voltage * Current)
Calculate energy required by multiplying power by time.
E = Power x HoldUpTime
Calculate the V^2
Vrange = Vstart^2 - Vdropout^2
Solve for C.
C = E / Vrange
An Arduino board by itself draws 30-40mA depending on which regulator, so assume 50mA for margin. The ATmega328 chip is only rated to 4V (or so) at 16MHz.
P = 5V * 50mA = 250mW * 2 = 500mW
This is an extreme estimate.
E = 500mW * 500mS = 250mJ
Time is 500mS (or recalculate for 100mS)
Vrange = 5^2 - 4^2 = 9V
The 4v dropout is probably higher than it really is, so you get some additional margin.
C = 250mJ / 9V = 0.02777 F
So thats 27mF or 27,778uF.
I'd probably round up to a 33,000 or 47,000uF. However, the whole calculation has lots of margins built into it, so its your call.
No need for a Supercapacitor/EDLC. You can get away with a regular aluminum electrolytic. Not critical, but try to get the lowest ESR you can.