Fault-tolerant and highly available configuration of distributed services including a computer-implemented method for distributed task orchestration. The method includes setting a watch on a first key in a first replica of a distributed configuration store and setting a value of a second key in a second replica of the distributed configuration store where the value of the second key indicates that a first sub-task of a distributed task is successfully complete. The value of the second key is received based on the watch set on the first key and execution of the second sub-tasks is initiated based on receiving the value of the second key. Also disclosed are techniques for service lifecycle management.