Postoffice Problem Architecture Version 2

Here is the original problem description.

Satellite Image of Hokkaido Island, Japan.

Changes:


Scenario:

There are N members and one spy. Initially each member has exactly one message with his/her own identification. Each member wants to distribute the message to all the members. Each message should be sent via one postoffice. The spy tries to read a fraction of the messages at one or more postoffices. A member can also send an acknowledgement message to signal other members, but the spy is not interested in these acknowledgement messages. Your mission is to design a protocol which distribute the messages to all the members as quickly as possible with preventing the spy from reading messages as much as possible.

Unlike the previous version, this problem is discrete. The action of each member can be represented as a finite state automaton without any cycle (no loop). Unlike the original problem, there is no guarantee of delivery time. The spy can have each message stay at a postoffice arbitrary long to maximize the number of messages s/he can collect at one visit.

Rules:


Format:

The behaviour of each member is described as a finite state automaton:

# comment
@person/state : action1, action2, ... : +cond1/branch1, +cond2/branch2, ...

person and state is a non-zero integer. An action is either "mi>@dest-postoffice" (sending a secret message) or "ai>@dest-postoffice" (sending an ack). A condition is a message specification ("mi" or "ai"). A branch is a state number.

NOTICE 1: A branch state number must be greater than the current state number (so there is no way to express a loop).

For example,

@1/0 : m1>@2-A : +m2/1, +a2/4
This can read as "For member @1 at state 0: send m1 to member @2 via postoffice A. Then if you receive m2 then go to state 1. If you receive a2 then go to state 4."

Now the whole automaton might be written as follows:

# Person 1
@1/0: m1>@2-A: +m2/1, +a2/4
# (case1)
@1/1:        : +a2/2
@1/2:        : +m3/3
@1/3: m3>@2-B:
# (case2)
@1/4:        : +m3/5
@1/5: m3>@2-A: +m2/6
@1/6:        :
The equivalent graph to this automation is following:

There are two possible execution cases in this protocol (case1 and case2). The actual execution path depends on which message is delivered first. Since we assumed the spy can control every message delivery, the spy might pick a weaker case and control the entire delivery to realize that case. But increasing the number of possible paths is useful to confuse the spy, because the number of combinations grows exponentially.

NOTICE 2: Branch statements also works as a declaration of recipient slot. Every message must be received explictly by its recipient (via the declaration). A member cannot know if a message has been already delivered before s/he starts to wait.

NOTICE 3: Each message can be received only once throughout the execution path. For example, "+m2" cannot appear twice at each case.


How the spy works:

Now let us consider a complete example:

# Sample 1
MESSAGE 3
FRACTION 2
VISIT 1
POSTOFFICE 2

# Person 1
@1/0: m1>@2-A: +m2/1, +a2/4
# (case1)
@1/1:        : +a2/2
@1/2:        : +m3/3
@1/3: m3>@2-B:
# (case2)
@1/4:        : +m3/5
@1/5: m3>@2-A: +m2/6
@1/6:        :

# Person 2
@2/0: a2>@1-A         : +m1/1
@2/1: m2>@1-B, m1>@3-B: +a1/2
@2/2: m2>@3-B         : +m3/3
@2/3:                 :

# Person 3
@3/0:                 : +m1/1
@3/1: m3>@1-A, a1>@2-A: +m2/2
@3/2:                 :

The equivalent graph to this is following:

Yep, this is already way complicated because there are two possible executions combined into one graph. The point is these colored arcs represent the dependency of each action. So if there is a cycle, the protocol is not executable.

Note that there are two possible outcomes for this protocol:

Case 1:

Case 2:

Knowing each plan, the spy removes redundant nodes from the graph and merge some nodes into one. Then the problem is converted to find the best cuts which maximize its flow (= the number of messages staying during the delivery).


Implementation Problems:

To implement the spy, there are two sources of exponential explosion:

  1. The combination of possible execution paths for each member.
  2. The combination of visits which maximize the number of reachable messages (max-size subset problem).

Currently I am planning to do just random trials for 1. For 2., I am going to implement simulated annealing search as I did in the previous version.


Yusuke Shinyama