Design a distributed rate limiter

Design a rate limiter to ensure API calls do not exceed a given QPS with optional burst allowance. Compare and implement two approaches (e.g., token bucket and sliding window), specifying data structures, time/space complexity, and correctness under concurrent access. Extend your design to a distributed setting across multiple application instances: discuss coordination (centralized store like Redis vs. sharded counters), clock skew tolerance, atomicity, idempotency, failure modes (node loss, partial updates), and strategies to maintain consistency and fairness. Provide APIs, example configurations, and monitoring/alerting for saturation.