Aspect Sequential Composition Parallel Composition
Basic Idea Privacy loss accumulates over queries executed sequentially. Multiple queries are executed simultaneously, and the strongest privacy parameter is maintained.
Privacy Bound Cumulative privacy loss is bounded by the sum of ε values across queries. Privacy bound is determined by the maximum ε value among the queries.
Privacy Amplification Privacy loss increases linearly with the number of queries. Privacy amplification depends on the query with the highest ε.
Trade-off Balances privacy loss with sequential execution order. Prioritizes strongest privacy guarantee among parallel queries.
Example If each query has ε=0.1, after 10 queries, cumulative ε=1. If queries have ε=0.1, 0.2, and 0.3, overall privacy is dominated by ε=0.3.
Applications Useful for cases where queries build on previous results. Suitable when multiple queries are independent and can be executed simultaneously.
Complexity Cumulative privacy loss calculation becomes complex for a large number of queries. Determining the maximum ε among parallel queries is straightforward.
Privacy Leakage Can lead to substantial privacy loss if many queries are executed sequentially. Maintains stronger privacy when queries are executed in parallel.
Individual Impact Privacy loss per query may decrease if queries are less sensitive. Sensitive queries can dominate overall privacy guarantee.
Dynamic Settings Well-suited for settings where queries evolve or adapt based on previous results. Not designed to adapt to dynamic query changes.
Advanced Techniques Advanced composition theorems can provide more accurate cumulative bounds. Similarly, advanced theorems can offer tighter privacy bounds for parallel execution.