<p>Blockchain is a distributed ledger that various applications can use to store data in a secure, decentralized, and immutable manner. The key piece in a blockchain is the consensus algorithm that different blockchain nodes run to obtain mutual agreement. While the Practical Byzantine Fault Tolerant (PBFT) is one of the most used algorithms and provides several advantages, it has a high communication cost, and it is executed in a sequential manner for consistency. To improve PBFT for blockchain consensus use, related works have added restrictive assumptions that can compromise security, consistency, and fault tolerance capabilities. This paper proposes a novel parallel PBFT-based consensus algorithm called Random-Cluster parallel PBFT. Our algorithm runs parallel consensus on random clusters in the blockchain network and then the resulting consensus is broadcasted to the blockchain network for a global consensus. Our proposal reduces the communication costs and improves the performance of the consensus which makes the blockchain more scalable. We provide formal proofs of the correctness of our algorithm. We have also proposed an algorithm to resolve the transaction order problem to address a consistent distributed ledger with concurrent consensus. The evaluation of throughput and communication complexity shows that Random-Cluster parallel PBFT provides better performance and more relevant results.</p>