It does actually rely on agreement. Clients track the network speed and only accept difficult enough hashes.