The prevalence of service-oriented computing, exemplified by search and social networking, has motivated an increasingly wide web-facing front end in Cloud data centers. Horizontal scaling is favored for its elasticity and distributed design of load balancers is highly desirable. Existing algorithms with centralized design, such as Join-the-Shortest-Queue (JSQ), have very high communication overhead with distributed dispatchers. We propose a novel class of algorithms called Join-Idle-Queue (JIQ) for distributed load balancing in large systems. A crucial observation is that good load balancing increases the arrival rate to idle processors, and in the large system limit, tracking idle processors alone achieves the optimal performance. The JIQ algorithm drastically outperforms the Power-of-Two algorithm, at all but extremely high load (e.g., 0.99), while incurring no communication overhead at job arrivals.