Abstract
This paper proposes distributed algorithms for solving systems of Boolean equations over a network where each node holds a private local equation. The objective is to compute the exact set of global solutions without nodes exchanging their private equations. The approach involves "lifting" discrete Boolean equations into linear algebraic equations in a high-dimensional space, which are then solved using distributed linear algebraic equation (DistributedLAE) solvers. We prove that with random initializations, the exact solution set is recovered with high probability. Furthermore, we integrate differential privacy via the Laplace mechanism and provide a method for distributedly verifying satisfiability.
Introduction
Boolean equations are fundamental to computer science, underpinning fields such as circuit design, cryptography, and gene regulatory network modeling. Solving a system of these equations—a variation of the Boolean Satisfiability (SAT) problem—typically requires a central processor with access to all constraints. However, in decentralized networks like IoT clusters or multi-agent systems, privacy concerns often prevent nodes from sharing their local data.
This research addresses the challenge of finding a global solution that satisfies all local constraints under three strict requirements: local privacy (no direct exchange of equations), decentralized computation (neighbor-only communication), and differential privacy (mathematical guarantees against eavesdropping).
Methodology
The proposed framework utilizes a three-stage pipeline to bridge the gap between discrete logic and distributed continuous optimization.
Boolean Matricization (The "Lifting" Trick)
Each node first converts its Boolean equation into a linear algebraic equation. By using a basis of Boolean vectors to represent the $2^m$ possible states of $m$ variables, the problem is "lifted" from a discrete search space into a high-dimensional Euclidean space. This transformation allows Boolean logic to be handled via linear algebra.
As illustrated in the figure above, the Boolean function $g(x)$ is mapped to a linear transformation $M_g$ acting on the lifted vector representations $\delta_{2^m}^{\lfloor x \rfloor}$. This mapping ensures that the discrete logic is preserved within the continuous linear subspace.
Distributed Projection Consensus
Once lifted, the network employs a DistributedLAE solver. Nodes maintain a local state and update it by projecting it onto their own solution space and then averaging it with their neighbors' states. By repeating this process with multiple random initializations ($2^m + 1$ times), the nodes collectively map out the entire affine subspace of solutions. The authors prove that if initial values are i.i.d. selected from a uniform distribution in a high-dimensional cube, the entire solution set can be reconstructed with high probability.
Boolean Vector Search
After identifying the continuous subspace, each node locally executes a specialized search algorithm to "pull" the discrete Boolean solutions out of the continuous space, effectively reversing the lifting process.
Privacy and Verification
To ensure differential privacy, the authors integrate the Laplace Mechanism, injecting calculated noise into the consensus steps. They derive an explicit noise level required to ensure the algorithm is $\epsilon$-differentially private, revealing a clear tradeoff: higher privacy requires more iterations ($T$) or rounds ($K$) to maintain accuracy.
Additionally, the paper introduces a method for Distributed Verification. If a system is unsatisfiable, the nodes' states will converge to different limits, providing a definitive signal that no global solution exists.
Key Results and Discussion
- Exactness: The algorithm is proven to return the exact set of Boolean solutions with high probability for solvable systems.
- Complexity: The computational complexity is approximately $O(2^{3m} + 2^{2m}n)$, where $m$ is the number of variables and $n$ is the number of nodes.
- Robustness: Numerical simulations demonstrate that the algorithm remains functional even with moderate levels of injected noise, though accuracy naturally improves as noise decreases.
Limitations and Future Work
The primary limitation is the "curse of dimensionality." Because the vectors grow at a rate of $2^m$, the algorithm becomes computationally and communicationally expensive as the number of variables increases. Future research may explore sparse representations or compression techniques to mitigate this overhead. Additionally, extending the work to find "least squares" approximate solutions for over-determined systems remains an open area for exploration.
Summary updated