The paper introduces a novel framework for federated unlearning, which aims to eliminate the impact of specific clients or data points on the global model learned via federated learning (FL). This problem is driven by the right to be forgotten and privacy concerns in FL. The framework is designed to meet two key criteria: communication efficiency and exact unlearning provability. The authors provide a rigorous definition of exact federated unlearning, ensuring that the unlearned model is statistically indistinguishable from the one trained without the deleted data. They identify total variation (TV) stability as a key property enabling fast exact federated unlearning, which measures the sensitivity of the model parameters to slight changes in the dataset. Leveraging this insight, they develop the FATS algorithm, which modifies the classical FedAvg algorithm for TV stability and employs local SGD with periodic averaging to reduce communication rounds. Efficient unlearning algorithms for FATS are designed for both client-level and sample-level unlearning. Theoretical guarantees are provided for the learning and unlearning algorithms, proving that they achieve exact federated unlearning with reasonable convergence rates. Empirical results on six benchmark datasets demonstrate the effectiveness and efficiency of the proposed framework, showing superior performance in terms of accuracy, communication cost, computation cost, and unlearning efficacy compared to state-of-the-art methods.The paper introduces a novel framework for federated unlearning, which aims to eliminate the impact of specific clients or data points on the global model learned via federated learning (FL). This problem is driven by the right to be forgotten and privacy concerns in FL. The framework is designed to meet two key criteria: communication efficiency and exact unlearning provability. The authors provide a rigorous definition of exact federated unlearning, ensuring that the unlearned model is statistically indistinguishable from the one trained without the deleted data. They identify total variation (TV) stability as a key property enabling fast exact federated unlearning, which measures the sensitivity of the model parameters to slight changes in the dataset. Leveraging this insight, they develop the FATS algorithm, which modifies the classical FedAvg algorithm for TV stability and employs local SGD with periodic averaging to reduce communication rounds. Efficient unlearning algorithms for FATS are designed for both client-level and sample-level unlearning. Theoretical guarantees are provided for the learning and unlearning algorithms, proving that they achieve exact federated unlearning with reasonable convergence rates. Empirical results on six benchmark datasets demonstrate the effectiveness and efficiency of the proposed framework, showing superior performance in terms of accuracy, communication cost, computation cost, and unlearning efficacy compared to state-of-the-art methods.