layout: true class: typo, typo-selection --- class: nord-dark, middle, center # **Cyclic Quorum Systems and Difference Covers** 🤝 @luk036 2025-05-06 📅 --- ## Abstract This presentation explores the relationship between cyclic quorum systems and difference covers—fundamental concepts in combinatorial design theory with applications across distributed computing, wireless networks, and string algorithms. We'll examine the theoretical foundations of these mathematical structures and their practical implementations in energy-efficient scheduling, distributed algorithms, mutual exclusion protocols, and string processing. --- ## Understanding Quorum Systems - **Intersection Property** 🔀 Any two quorums must have a non-empty intersection, ensuring coordination between entities using different quorums. *Example (N=13):* Quorum A = {0,1,3,9} and Quorum B = {1,2,4,10} (shift of A by 1) intersect at 1. - **Rotation Closure** 🔄 For all quorums G, H and any integer i, G ∩ (H + i) ≠ ∅, where H + i represents a cyclic shift of H by i. *Example:* A = {0,1,3,9} and (A + 5) = {5,6,8,1} intersect at 1. - **Applications** 📱 Quorum systems enable mutual exclusion, data replication, and consensus in distributed environments with limited connectivity. --- ## Cyclic Quorum Systems (CQS) 🔁 - **Definition** 📖 Given a cycle length n and a base quorum A, a cyclic quorum system X is defined as the set of all cyclic shifts of A: X = {A + i mod n | i ∈ {0, 1, ..., n-1} }. *Example:* Base quorum A = {0,1,3,9} generates 13 quorums via cyclic shifts. - **Construction** 🏗️ CQS are constructed using relaxed difference sets where every non-zero difference modulo n can be formed by at least one pair of elements in the set. *Example:* For A = {0,1,3,9}, differences cover all numbers 1-12 mod 13. - **Efficiency** ⚡ For a quorum system over N, the bound of quorum size d is d ≥ √n. Cyclic quorum systems often achieve sizes close to this theoretical lower bound (√13 ≈ 3.6, so d=4 is efficient). .mermaid[ <pre> graph LR A[Set A]:::set -->|Cyclic shifts + i mod n| B[Quorum System X]:::sys B --> C[X = {A + i mod n}]:::sys C --> D{Intersection?}:::check D -->|G ∩ H ≠ ∅| E[Valid CQS]:::valid D -->|No| F[Invalid]:::invalid classDef set fill:#9c27b0,stroke:#7b1fa2,color:white classDef sys fill:#2196f3,stroke:#1976d2,color:white classDef check fill:#ff9800,stroke:#f57c00,color:black classDef valid fill:#4caf50,stroke:#388e3c,color:white classDef invalid fill:#f44336,stroke:#d32f2f,color:white </pre> ] --- ## Difference Covers 🧮 - **Definition** 📝 A multiset D of elements from a finite abelian group G is a difference cover with parameters (v,d,λ) if every element z ∈ G appears exactly λ times as a non-trivial difference z = x_i - x_j of elements in D. *Example (N=13):* D = {0,1,3,9} covers all differences mod 13: - 1-0=1, 3-1=2, 9-3=6, etc. - **Cyclic Difference Covers** 🔄 When the underlying group G is cyclic (typically Z_v under addition modulo v), the difference cover is called cyclic—particularly relevant to constructing cyclic quorum systems. - **Relaxed Difference Sets** 🛋️ A relaxed difference set requires every non-zero difference to occur at least once, rather than exactly λ times, making it a broader type of difference cover. .mermaid[ <pre> graph TD D[a1, a2, ..., ak]:::set -->|Differences| Diff[Non-zero differences]:::diff Diff -->|Cover all| Z[Every z in Zv, z != 0]:::cover Z --> DC[(v, k, lambda) difference cover]:::params classDef set fill:#9c27b0,stroke:#7b1fa2,color:white classDef diff fill:#2196f3,stroke:#1976d2,color:white classDef cover fill:#4caf50,stroke:#388e3c,color:white classDef params fill:#ff9800,stroke:#f57c00,color:black </pre> ] --- ## Relationship Between CQS and Difference Covers 🔗 - **🏛️ Theoretical Foundation** Cyclic quorum systems are fundamentally linked to difference covers - **🚧 Construction Principle** A group of sets forms cyclic quorum sets if and only if their base is a relaxed difference set - **💯 Intersection Guarantee** The difference cover property ensures non-empty intersection between any two quorums **Theorem 1** establishes that a group of sets B_i = {a_1 + i, a_2 + i, ..., a_d + i} mod N forms cyclic quorum sets if and only if D = {a_1, a_2, ..., a_d} is a relaxed (N,d)-difference set. .mermaid[ <pre> graph LR A[Base Quorum A]:::base -->|Cyclic shifts| B[CQS X]:::cqs D[Relaxed Diff Set]:::diffset -->|Forms| E[Difference Cover]:::cover B <-->|Theorem 1| E classDef base fill:#9c27b0,stroke:#7b1fa2,color:white classDef cqs fill:#2196f3,stroke:#1976d2,color:white classDef diffset fill:#ff9800,stroke:#f57c00,color:black classDef cover fill:#4caf50,stroke:#388e3c,color:white </pre> ] --- ## Energy-Efficient WSN Scheduling with CQS-Pair 🔋 - **🔋 Heterogeneous Requirements** Different nodes have varying power-saving needs; clusterheads need shorter discovery delays while member nodes prioritize energy conservation - **💡 CQS-Pair Solution** Two cyclic quorum systems with different cycle lengths satisfy heterogeneous rotation closure property - **🔍 Guaranteed Discovery** Nodes using different quorums are guaranteed to hear each other at least once within every m consecutive slots - **⚖️ Optimized Trade-offs** Balances energy consumption and discovery delay based on node roles --- ## Distributed All-Pairs Algorithms with Cyclic Quorum Sets 🤖 - **Data Distribution** 🛢 Each process holds only a subset (quorum) of the total datasets *Example:* With 13 processes, each stores ~4 datasets (from {0,1,3,9} + i). - **All-Pairs Property** ᯤ Every pair of datasets exists together in at least one quorum *Example:* Datasets 5 and 12 both appear in quorum {5,6,8,1} (shift by 5). - **Scalability Benefits** 📈 Quorum size grows as O(√P) with P processes, significantly reducing memory requirements --- ## Distributed Mutual Exclusion 🔒 - **Request Permission** 🔒 Process requests access from all members of its quorum - **Verify Availability** ✅ Quorum members check for conflicts with other processes - **Enter Critical Section** ⛔ Process accesses shared resource when permitted - **Release Resource** 📢 Process notifies quorum members upon completion Cyclic quorum systems provide efficient mutual exclusion with quorum sizes approaching the theoretical minimum of √N. The cyclic nature ensures symmetry (equal responsibility for all sites) while requiring only one base quorum to define the entire system. --- ## Suffix Array Construction - **Difference Cover Sampling** 🎯 Select a subset of positions based on a difference cover modulo v (e.g., positions i ≡ 1 mod 3 and i ≡ 2 mod 3 in DC3 algorithm) - **Recursive Sorting** 🔁 Sort the sampled suffixes recursively, using the property that any two positions have a small offset where both are in the sample - **Complete Suffix Array** ✅ Use the sorted sample to induce the order of remaining suffixes and merge to obtain the complete suffix array The difference cover property ensures that for any two positions i and j, there exists a small offset l such that both i+l and j+l are sample positions. This property is crucial for efficient comparison and merging steps in linear-time suffix array construction algorithms. --- ## Future Research Directions 🔮 - **Efficient Construction Methods** ⚙️ Develop more efficient algorithms for constructing optimal relaxed difference sets and cyclic quorum systems for arbitrary parameters, especially for large system sizes where exhaustive search is infeasible. - **Adaptive Quorum Systems** 🔄 Investigate dynamic and adaptive quorum systems based on cyclic structures for more resilient solutions in the face of node failures or changing network conditions. - **New Applications** 🚀 Explore connections between difference covers and advanced data structures beyond suffix arrays to reveal novel applications in computational theory and practice. --- class: nord-dark, middle, center # Q&A 🎤 --