We have auto-scaling Docker environments in which we use Consul for service discovery. These environments can add or remove one instance every few minutes.
Our early Consul testing showed that it was very easy for Consul to loose its quorum. Perhaps naively, our very first experimentation was a setup in which we would start a Consul server on all instances and have that Consul server join the cluster. That part was working fine.
However, Consul does not reap unreachable nodes quickly (it take about 72 hours?) in a very scalable environments that means that the list of Consul servers keeps growing and over time, most of them are "unreachable" and at that point, the cluster loses its quorum.
We've seen armon's response from almost two years ago on this issue on GitHub: https://github.com/hashicorp/consul/issues/454#issuecomment-125767550
Most of these problems are caused by our default behavior of attempting a graceful leave. Our mental model is that servers are long lived and don't shutdown for any reason other than unexpected power loss, or a graceful maintenance in which case you need to leave the cluster. In retrospect that was a bad default. Almost all of this can be avoided by just kill -9 the Consul server, in affect simulating power loss.
We were trying to avoid running dedicated, long-lived nodes. Keep in mind that at no point, we remove N/2+1 instances from an auto-scaling group. The EC2 cluster is able at any point in time to reach most of the nodes and should be able to vote whether a node should be removed from the Consul (or other tool) cluster.