Mobile devices are rapidly becoming the major service tools. However, traditional client-server-based mobile service models are unable to meet the increasing demands from mobile users in terms of diversity of services. Cloud computing can enable mobile devices to offload complex operations of mobile applications, which are infeasible on mobile devices alone. Mobile Cloud Computing (MCC) is widely accepted as a concept that can significantly improve the user experience when accessing mobile services. In order to enhance the capability of fault tolerance and ensure network security, it is necessary to provide a stable mobile cloud service environment. Due to the Byzantine Agreement (BA) problem is a fundamental issue in fault-tolerant distributed systems. To enhance the reliability of a cluster-based MCC, it is the first time a protocol OACM (Optimal Agreement protocol for Cluster-based MCC) is proposed herein to solve the BA problem. The protocol makes all fault-free nodes communicate with each other and collect the exchanged messages to decide a common value. Based on the common value, the protocol ensures all fault-free nodes reach agreement without the influence of faulty components. Meanwhile, OACM uses the minimum number of rounds for message exchanges to make all fault-free nodes agree on a common value. The study has also proved the protocol can tolerate the maximum number of faulty components.