<p>Are you looking for <a href="https://en.wikipedia.org/wiki/Population_protocol" rel="nofollow noreferrer">Population Protocols</a> ?</p>

CC BY-SA 4.0
2024-11-05T04:20:57.167Z
Precisely! I missed some details (for instance, the communication was originally one-way) but the core idea seems to remain intact after years of dilution in my memory.
Ivan Smirnov
CC BY-SA 4.0
2024-11-05T00:00:09.473Z
2024-11-05T00:00:09.473Z
Denis
<p>I've been once told of a model of computation which is capable of computing various boolean functions but cannot find the source anymore.</p>
<p>There are multiple agents. Each agent serves as an input to the function and carries a single input bit. Aside of that bit, an agent has constant memory. Sometimes two agents meet each other and interact; interaction allows them to modify their state. They have no access to any information except their memory and input bits. In particular, the agents are all identical and not numbered. At any point of time each agent may <em>vote</em> for the result of the function.</p>
<p>It is guaranteed that each pair of agents will meet infinite number of times. The model is said to compute the function if for any set of inputs there will be a point of time such after which each agent will vote for the correct result and never change their votes.</p>
<p>Majority is an example function computable in this model (given that the number of agents is odd):</p>
<ul>
<li>initially the agent votes for its input bit</li>
<li>when two unlocked agents with different bits meet, they become locked</li>
<li>when a locked agent A meets an unlocked agent B, A will start voting for B's input bit (until he meets another unlocked agent with different input, if ever)</li>
</ul>
<p>It can be shown that eventually all unlocked agents will have the same input value (equal to the majority) and so will eventually convince everyone to vote for it.</p>
<p>What is the name of this model, if any? Which keywords should I use to find any papers analyzing it?</p>

CC BY-SA 4.0
2024-11-03T14:53:19.697Z
*the agents are all identical and not numbered* — So, this means that a priori only *symmetric* Boolean functions can be computed in this model, making it quite restrictive.
Emil Jeřábek
CC BY-SA 4.0
2024-11-04T12:31:37.033Z
What is the meaning of “randomly interact” in the title? Does this just refer to the fact that the pair of agents that meet is chosen nondeterministically at each time step, or do you allow the actual interaction between two agents to use randomness? In particular, if two agents with the same memory and input bits meet, do they also have to have the same memory after they part?
Emil Jeřábek
CC BY-SA 4.0
2024-11-04T18:38:16.653Z
@EmilJeřábek I meant that the choice of interacting agents is random. Better to say arbitrary, because there is no randomness involved. The agents themselves are deterministic, I think, so the agents in your question indeed have the same memory after they meet; however, I don't remember the model precisely (that's why I'm looking for a reference) and there might be a variation with internal randomness of agents.
Ivan Smirnov
CC BY-SA 4.0
2024-11-04T19:39:03.137Z
All right, thank you. I understand that the question is a reference request, but I’m just curious.
Emil Jeřábek
<reference-request><lo.logic>
Name for a model of computation where constant-memory agents randomly interact with each other
Ivan Smirnov
# Name for a model of computation where constant-memory agents randomly interact with each other

(Asked by: username_0 on 2024-11-03)

I've been once told of a model of computation which is capable of computing various boolean functions but cannot find the source anymore.

There are multiple agents. Each agent serves as an input to the function and carries a single input bit. Aside of that bit, an agent has constant memory. Sometimes two agents meet each other and interact; interaction allows them to modify their state. They have no access to any information except their memory and input bits. In particular, the agents are all identical and not numbered. At any point of time each agent may *vote* for the result of the function.

It is guaranteed that each pair of agents will meet infinite number of times. The model is said to compute the function if for any set of inputs there will be a point of time such after which each agent will vote for the correct result and never change their votes.

Majority is an example function computable in this model (given that the number of agents is odd):

* initially the agent votes for its input bit
* when two unlocked agents with different bits meet, they become locked
* when a locked agent A meets an unlocked agent B, A will start voting for B's input bit (until he meets another unlocked agent with different input, if ever)

It can be shown that eventually all unlocked agents will have the same input value (equal to the majority) and so will eventually convince everyone to vote for it.

What is the name of this model, if any? Which keywords should I use to find any papers analyzing it?

**Tags:** reference-request, lo.logic

> **Comments:**
> **username_1**: *the agents are all identical and not numbered* — So, this means that a priori only *symmetric* Boolean functions can be computed in this model, making it quite restrictive.  
> **username_1**: What is the meaning of “randomly interact” in the title? Does this just refer to the fact that the pair of agents that meet is chosen nondeterministically at each time step, or do you allow the actual interaction between two agents to use randomness? In particular, if two agents with the same memory and input bits meet, do they also have to have the same memory after they part?  
> **username_0**: @EmilJeřábek I meant that the choice of interacting agents is random. Better to say arbitrary, because there is no randomness involved. The agents themselves are deterministic, I think, so the agents in your question indeed have the same memory after they meet; however, I don't remember the model precisely (that's why I'm looking for a reference) and there might be a variation with internal randomness of agents.  
> **username_1**: All right, thank you. I understand that the question is a reference request, but I’m just curious.  

---

## 1 answers

### Answer by username_2 on 2024-11-05. Score: 3 | Accepted answer

Are you looking for [Population Protocols](https://en.wikipedia.org/wiki/Population_protocol) ?

> **Comments:**
> **username_0**: Precisely! I missed some details (for instance, the communication was originally one-way) but the core idea seems to remain intact after years of dilution in my memory.  

---

