We study the problem of scheduling permanent jobs on un- related machines when the objective is to minimize the Lp norm of the machine loads. The problem is known as load balancing under the Lp norm. We present an improved up- per bound for the greedy algorithm through simple analy- sis; this bound is also shown to be best possible within the class of deterministic online algorithms for the problem. We also address the question whether randomization helps on- line load balancing under Lp norms on unrelated machines; this is a challenging question which is open for more than a decade even for the L2 norm. We provide a positive answer to this question by presenting the ¯rst randomized online algorithms which outperform deterministic ones under any (integral) Lp norm for p = 2; :::; 137. Our algorithms es- sentially compute in an online manner a fractional solution to the problem and use the fractional values to make ran- dom choices. The local optimization criterion used at each step is novel and rather counterintuitive: the values of the fractional variables for each job correspond to °ows at an ap- proximate Wardrop equilibrium for an appropriately de¯ned non-atomic congestion game. As corollaries of our analysis and by exploiting the relation between the Lp norm and the makespan of machine loads, we obtain new competitive algo- rithms for online makespan minimization, making progress in another longstanding open problem.