You don’t need agreement. A newly added node can try best effort to find the optimal placement based upon the known state of the cluster and then advertise that it is going to a specific place in the hash ring. When clients learn about the new node they will also learn where that node has decided to put itself into the ring. No coordination is needed. There are probably moments that a client learns about the node they also atomically learn about where that nodes is placed.

There are probably other issues where simultaneously added nodes may try to insert themself into the same position in the ring, you could add some jitter in the placement to compensate for this, but then I guess you are now introducing randomness which is one step closer to just having vnodes again.