A method and system are directed towards balancing loads on an authentication system. The system employs a first authentication server that is configured to authenticate a user. The system includes a master authentication server. When the master authentication server determines that a load on it has reached a pre-determined value, a data store associated with the master authentication server is partitioned between authentication servers that assume a master authentication server role for its partition of the data store. In one embodiment, each new master authentication server is further enabled to partition its respective partition of the data store, if their respective loads reach the pre-determined value.