Descriptive complexity for distributed computing with circuits

Abstract

We investigate distributed computing with identifiers in the realistic scenario where the local computations in a distributed message passing setting are operated by Boolean circuits. We call this framework the message passing circuit model. We capture the expressive power of the model with a recursive rule-based logic called modal substitution calculus MSC. The result is established via constructing translations that are highly efficient in relation to size and computation time. In particular, the worst size blow-up is quadratic and becomes linear in the bounded-degree scenario. Computation time delays are similarly modest. As a concrete demonstration of how our setting works, we establish that a very fast coloring algorithm based on Cole–Vishkin can be specified by logarithmic size programs (and thus also logarithmic size circuits) in the bounded-degree scenario.