Stable computation of relations and predicates

James Aspnes. Stable computation of relations and predicates. arXiv:2412.02008 [cs.DC].

Abstract

A population protocol stably computes a relation R(x,y) if its output always stabilizes and R(x,y) holds if and only if y is a possible output for input x. Alternatively, a population protocol computes a predicate R(<x,y>) on pairs <x,y> if its output stabilizes on the truth value of the predicate when given <x,y> as input.

We consider how stably computing R(x,y) and R(<x,y>) relate to each other. We show that for population protocols running on a complete interaction graph with n≥2, if R(<x,y>) is a stably computable predicate such that R(x,y) holds for at least one y for each x, then R(x,y) is a stably computable relation. In contrast, the converse is not necessarily true unless R(x,y) holds for exactly one y for each x.

• ArXiv version: arXiv:2412.02008 [cs.DC].

BibTeX

@misc{Aspnes2024,
title={Stably computable relations and predicates}, 
author={James Aspnes},
year={2024},
eprint={2412.02008},
archivePrefix={arXiv},
primaryClass={cs.DC},
url={https://arxiv.org/abs/2412.02008}, 
}