How can HBase strongly consistent without consensus algorithm like paxos

Many articles refer that HBase is a strongly consistent system because the read/write only goes to the primary region server.

But I am thinking a scenario that the consistency can not hold

(1) a write failed to be replicated to some HDFS replicas (afaik, HBase replication relies on HDFS) but succeeded on some others and the primary responds a failure to the client.

(2) then the primary failed and a new leader got elected, which happened to have the success write in step (1).

The client will get uncommitted data, which breaks the strong consistency guarantee.

You are right that HBase is not real "strong consistency". They claim it's "strong consistency" because of the master/slave replication where a client can only read/write from the master, which guarantees to have the latest write. So HBase folks categorize this as strong. Actually, the consistency of this type is still weak consistency (one of the failure examples is the scenario you described)

Ryan Barret from Google had a talk back in 2009 to explain the difference and M/S is an eventual consistency model, cite the diagram here and more details in this book chapter