Embodiments are directed to towards cloud scale automatic identity management. A floating network may be established using agents operative on hosts across one or more networks. Each node of the floating network is resident on host (computer or cloud instance) that includes an agent configured to perform one or more networking tasks that establish the floating network. Parent nodes may be nodes designated as points in the floating network for adding additional nodes. Accordingly, each parent node includes at least one parent agent that includes at least parent credentials. Agent installers provided to a host may generate a child agent for the host that includes child credentials generated based on its parent credentials. An unambiguous identity value for the new child node may be determined by tracing a trust relationship path from the child node to the root node of the floating network.