In the case of adding columns, all that is really going on with an 'ALTER' statement in CQL is some meta-data entry in the system tables. No data files are being re-written.
This meta-data is then used for validation from both the API transports and compaction.
If you really have that big a cluster, you will need to wait a short while for the change to propagate - cqlsh blocks until this happens, IIRC.