How can a distributed system cooperate to determine rules of its environment?

Question

I'm sorry if this question is silly or elementary. I'm not a computer scientist so I don't know the vocabulary to use to ask this question. Thus I've produced an analogy to explain the challenges I'm facing in my program. Please do point me in the right direction, I don't know what I need to learn to solve this problem:

An Analogous Puzzle:

Assume you are given a new house with 4 rooms. But this house is very strange; each room has 1-3 lights in it and 1-3 light switches. Some diabolical electrician has wired the house very strangely so that the switches can control lights in other rooms of the house. Furthermore, the behavior of the lights and switches may depend which lights are on at the time.

For instance a switch in room 1 may turn on on a light in room 2 if a light in room 4 is off, but it won't if room 4 is lit up. Almost all the light switches have a very strange relationship to some of or all of the other lights in this way. But they're not random, in their behavior: given the same state of the house a light switch will have the same effect as it did.

Now imagine you and 3 friends each occupy a room and are able to do one action in the house at a time. You can talk to each other by calling or texting each other on your cell phones, but every minute costs money, or every text costs money so you want to communicate as little as possible (thus you want to be efficient).

What I need to figure out is the answer to the following question:

How do you and your 3 friends need to communicate (what information do you need to share with each other) in order for the 4 of you to work together to deduce the wiring rules that govern the lights?

Does each person need to know the state of each room? Or do they only need to know the state of each room when something unexpected happens? How do they deduce the rules that govern the lights?

I need to find a universal way for the agents to infer the rules underlying the system efficiently. That's basically it.

In a more complicated scenario (thousands or millions of rooms), does anything change? What do I need to learn to solve this puzzle in a way that scales?

One other consideration: if necessary for a scalable algorithm you can recruit other friends from outside the house and give them information. I'm not sure why you would need to, but that's also a possibility.

That is the puzzle I have: many agents, mainly identical and independent are interacting with the same system.

I need to find an algorithm of cooperation/communication that results in the system as a whole, or each individual agent to infer/deduce (or even just behave in accordance with) the underly rules of the environment.

Answer 1

This is a non-mathematical riddle, so part of the solution is determining the rules of the game. The computer science way of solving this, however, would be to use a Gray code and a synchronized system. The idea is as follows. Suppose that there were only 3 switches. You will go over their states in the following order: $$ 000\\001\\011\\010\\110\\111\\101\\100 $$ (Here 0 is the original state of the switch, and 1 is the other state of the switch.) Decide on a reasonable time interval $t$. There will be 8 rounds (or, in general, $2^k$ rounds if there are $k$ switches), each taking $t$ units of time. Each round other than the first begins with the appropriate person changing one of the switches (the appropriate person can be determined in advance once we know how many switches are in each room). Then they all record the "output" that they see in their room. When this process ends, they can compare notes and reconstruct the entire function.

This strategy is optimal with respect to the number of switch flips. While it takes $2^k$ rounds for $k$ switches, you can't really do any better since the function converting the input (switches) to the output (lights) is completely arbitrary. This does mean that it doesn't scale at all. If you want a strategy that does scale, you'll have to adjust the problem by restricting the set of possible functions (switch–light correspondences).