The problem of binary consensus for an undirected, synchronous, fixed topology network through noiseless, binary communication is the focus of this paper. We propose a binary consensus protocol that guarantees network convergence to the initial network majority via binary communication among one-hop neighbors. The proposed protocol requires the nodes to keep track of an internal state, which accounts for the local disagreement and the local average of the network vote. Convergence of the algorithm to the initial global majority is proved using the lossy S-procedure. Numerical simulations are included to demonstrate the performance of the proposed protocol.