Single-Bit Distributed Equality-Constraint Optimal Scheduling and Allocation

Distributed resource allocation finds applications in multi-agent-based networked scheduling scenarios. In this work, a single-bit solution is proposed for distributed resource allocation to optimize strictly convex cost functions. The main contribution is that the proposed solution only requires the exchange of single-bit of (local) gradient information. This significantly reduces the computational complexity and communication load on agents. The solution further preserves anytime feasibility over weight-balanced directed graphs, which ensures that the equality-constraint (between resource and demand) is always met. This implies that at any termination time the allocated resources are equal to the demand and there is no service disruption. Due to the reduced order of information exchange and complexity, the proposed single-bit algorithm converges to the neighborhood of the optimal solution. The general Lyapunov-based proof technique (i) is regardless of this particular sign-based nonlinearity and (ii) holds under weak network connectivity (uniform-connectivity, i.e., connectivity of the union network over time). Further, the solution solves general (possibly) non-quadratic objectives including additive penalty terms (and barrier functions) to address the local box constraints approximations. The algorithm works over weight-balanced networks, relaxing the need for iterative stochastic weight design, e.g., in case of link failure or packet drops. Applications in power resource allocation and CPU scheduling are simulated to verify the theoretical results.