Abstract
In this paper, we propose distributed algorithms that solve a system of Boolean equations over a network, where each node in the network possesses only one Boolean equation from the system. The Boolean equation assigned at any particular node is a private equation known to this node only, and the nodes aim to compute the exact set of solutions to the system without exchanging their local equations. We show that each private Boolean equation can be locally lifted to a linear algebraic equation under a basis of Boolean vectors, leading to a network linear equation that is distributedly solvable. A number of exact or approximate solutions to the induced linear equation are then computed at each node from different initial values. The solutions to the original Boolean equations are eventually computed locally via a Boolean vector search algorithm. We prove that given solvable Boolean equations, when the initial values of the nodes for the distributed linear equation solving step are i.i.d selected according to a uniform distribution in a high-dimensional cube, our algorithms return the exact solution set of the Boolean equations at each node with high probability. Furthermore, we present an algorithm for distributed verification of the satisfiability of Boolean equations, and prove its correctness. The proposed algorithms put together become a complete framework for distributedly solving Boolean equations: verifying satisfiability and computing the solution set whenever satisfiable.
Introduction
Boolean equations are the bedrock of computer science, appearing in everything from cryptography and circuit design to modeling gene regulatory networks. Often, these equations are distributed across a network where each node holds a specific part of the system. A significant challenge arises when these equations are private; for instance, different hospitals might hold logical constraints on a disease model but cannot share raw data due to privacy laws. Standard Boolean Satisfiability (SAT) solvers are typically centralized and require full access to all constraints. This paper introduces a framework for finding common solutions to collective Boolean equations without revealing individual equations to other nodes.
Methodology
The proposed framework bridges the gap between discrete logic and continuous mathematics through a three-stage approach.
Boolean Matricization (The "Lifting" Trick)
Each node converts its private Boolean equation into a linear algebraic equation by mapping $m$ binary variables into a $2^m$-dimensional vector space. This "lifts" a combinatorial problem into a geometric one—specifically, finding the intersection of affine subspaces.
As illustrated in Figure 1, the lifting process allows a Boolean function $g(x)$ to be represented as a matrix $M_g$ acting on lifted vectors. This transformation enables the use of powerful tools from control theory and distributed optimization to solve logic problems.
Distributed Linear Algebraic Solver (DistributedLAE)
Nodes utilize a "projection consensus" algorithm. Each node maintains a state and iteratively updates it by projecting it onto their own local solution space and averaging it with their neighbors' states. To capture the entire solution set, this process is run multiple times ($k_*$ rounds) starting from different random initial values, effectively "painting" the entire solution subspace.
Boolean Vector Search
Once the nodes have converged on the global linear solution space, they perform a local search to map those high-dimensional vectors back to the original binary variables ($0$s and $1$s).
Privacy and Satisfiability
To handle real-world privacy concerns, the authors introduce a Differentially Private (DP) version of the algorithm. By injecting calibrated Laplace noise into the consensus steps, they ensure that an eavesdropper cannot infer a specific node's private equation.
Additionally, the framework provides a method for distributed verification of satisfiability. If the nodes' states converge to different values despite the consensus process, it serves as a mathematical signal that the global system is unsatisfiable.
Key Results and Complexity
The authors prove that with $k_* = 2^m + 1$ random starts, the algorithm returns the exact solution set with probability 1. While the local complexity is $O(2^{3m} + 2^{2m}n)$—exponential in the number of variables $m$, as expected for NP-complete problems—it scales linearly with the number of nodes $n$, making it suitable for large networks with relatively simple local constraints.
Limitations and Future Work
The primary bottleneck is the "curse of dimensionality" caused by the $2^m$ scaling. Future work is needed to find sparser representations or lifting techniques that do not explode in dimension. Furthermore, the high communication overhead of sending high-dimensional vectors suggests a need for accelerated or parallel versions of the algorithm to reduce costs in large-scale deployments.
Summary updated