The introduction of Proximity services (ProSe) in Long Term Evolution Advanced (LTE-A) allows User Equipments (UEs) to communicate directly without routing the data through the LTE access network. This is a major step towards supporting mission-critical communication for first responders who need the ability to communicate ubiquitously. To properly receive data, the UEs must be synchronized. Thus, reducing the synchronization delays is important to avoid service disruption. When operating outside of the network coverage, UEs cannot rely on the synchronization information provided by the base station. In such cases, a distributed protocol is required to announce and detect the synchronization information within devices in proximity. In this paper, we present an adaptive algorithm that reduces the out-of-coverage synchronization delays while meeting the requirements specified in the LTE-A standard. The algorithm takes into account the UE traffic and synchronization conditions to achieve these goals. We evaluate the algorithm performance using our ns-3 ProSe implementation and show that fast convergence time to a synchronized state can be achieved using the proposed algorithm while satisfying the standard performance constraints.