Satellite Image of Hokkaido Island, Japan.
Changes:
The problem appeared when you write something like "+1,+2" in your conditions. With probablistic delay, it's not likely that these two messages arrived at the same time. So you need to add another two conditions "+1,=2" and "=1,+2". But this was ignored in the previous version because it assumed the executions with probablistic delay happen *exactly* in the same order as the situation without delay. As a result, the program "misses" some of actions which should have been executed, which results in a very low probability of protocol success. Sometime it wrongly reports "the protocol failed." because of the very low probability. In the newer version I weakened this restriction by dynamically constructing a time constraint graph. Now you can add both "+1,=2" and "=1,+2" which gives a better result.
What was the problem anyway?
Assume each delivery might take up to 2days with 50% probability.
Now consider the following protocol:
Then I noticed the same argument applies to trigger conditions, because we decided that each statement is executed if ALL the conditions are satisfied. I assumed the probabilities of each condition was independent. However, some of conditions should never be true at the same time due to similar exclusivity.
Apparently the only way to get things right is to track every possible outcome following the probability distribution. But this was impractical. This is why I needed to put the additional assumption above. This way, we know a temporal relationship between two actions (= which action should occur first) by using the knowledge obtained in the discrete assumption. If one action occurs after another, the outcomes of these two actions should never be valid at the same time.
Better (and faster) spy's simulated annealing. Fancy HTML output (-H option). See a sample.
Specification change:
Now it accepts a "wait" action (e.g. "*2
" means "wait 2 days")
(See the format).
I also modified the parameter format a bit. Now it takes the number of postoffices
instead of taking a string list of postoffice names
(However it still assumes the name of each postoffice is an uppercase alphabet starting from 'A').
Also, you can now assume the reachability
(an integer list of likelihood ratio) takes exactly five elements, because the original
problem assumes each delivery takes at most five days. So the parameter format now consists of
a fixed number of integers, which makes easy to handle for those who are
using languages like C.
Important points I didn't mention in the class:
Bugs: Slow. The source is messy. The simulated annealing part should be still improved. Any other bug in correctness?
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. 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.
This problem is different from the original problem in that delivery happens probabilistically. In the original problem, every state was considered as discrete and the spy could delay each delivery to arbitrary length to fit to the spy's plan. But in this modified version each delivery follows a certain distribution. Here is the original problem description.
Here is a schematic view of the description above:
At every morning, each member can make a decision based on the following information:
They do not know:
With these restrictions, your protocol can be written as a set of if-then statements (see below).
(In theory, the spy can change the decision dynamically depending on where a message is. But the actual implementation performs all the calculation in advance based on the statistical inference and does not change it throughout the game.)
Each delivery takes at least one day. Some of them may take several days. The number of days follows a certain distribution which is given as a parameter.
Examples:
At the beginning of a game, your program receives the following parameters:
Here is a sample:
MESSAGE 4 FRACTION 2 VISIT 2 POSTOFFICE 4 (there are four postoffices: A, B, C and D.) REACHABILITY 50 30 20 0 0 (equivalent to [0.5, 0.3, 0.2, 0.0, 0.0])
After taking these parameters, your program generates a set of if-then statements for each member in the following format:
@member: cond1, cond2, ..., condN: action1, action2, ..., actionM
Each line should contain a member label, conditions, and actions. For example:
@1: =1,!2,+3: 1>4-A, *2, 3>2-B
The first field (@1) indicates which member this statement is instructed to.
The second field (=1,!2,+3) is a list of conditions.
Each condition is specified in the following format:
NOTE1: Each statement must contain at least one +n condition. This is activated only when the message is delivered, and it triggers the following actions. At the very beginning (day=0), every member receives his/her own message. This initiates the whole process.
NOTE2 (Oct. 31): Extra blanks and commas are ignored. Therefore,
is also a valid statement.@ 1 : =1, ! 2, +3,,, : 1 > 4 - A,, *2, 3 > 2 - B ,
The third field (1>4-A, *2, 3>2-B) is a list of performed actions if ALL the conditions are satisfied (if you want to write "OR" condition, you can do this by giving multiple statements). Each action is specified in the following format:
The sample statement can read as follows:
"For Member-1,
if you already have Message-1 and do not have Message-2, and Message-3 is just delivered,
then send Message-1 to Member-4 via Postoffice-A, rest 2 days, and then send Message-3 to Member-2 via Postoffice-B."
You can give multiple statements to each member. At every turn, all statements are scanned and any satisfied statement is executed parallelly.
Any string following "#" character can be regarded as a comment. A sample list can be:
# for member 1 @1: =1,!2,+3: 1>4-A, *2, 3>2-B @1: =1,=2,+4: 1>3-C, 2>4-A, 4>2-B @1: +1: 1>2-A, 1>3-D # this must be triggered first. # for member 2 @2: =2,+3: 2>1-B, 3>4-D ...
The evaluation program takes the parameters and your output specified above and gives a score of your protocol. The score is calculated based on the probability of each message staying at a postoffice without running an actual protocol.
The system maintains two matrix: event matrix and postoffice matrix.
A event matrix (shown below) holds the probability of having or receiving a message for each member and day. First, the system calculates the probability for each condition being triggered for a certain day. Then the system assigns the probability of deliveries caused by each action to the following days. By repeating this from day=0, it can calculate the probabilities of delivery chains.
For example, there are two conditional statements in the protocol:
@1: +1: 1>2-A ...(1) @2: +1: 1>3-B ...(2)
In this case, the probability of the statement (1) being triggered at day=0 is 1.0. Then it distributes the probability of delivery 0.5, 0.3 and 0.2 for Member-2 to the following days. Now, say at day=2, the probability of the statement (2) being triggered is 0.3 because Member-2 will receive the message with probability=0.3 at this time. Then it further distributes the probability of delivery caused by the statement (2) for Member-3, so on:
At the same time, the system also builds a postoffice matrix, which holds the probability of a certain message staying at a certain postoffice.
In addition to the example above, suppose at the morning of day=2, Member-3 sent his/her own message to someone via Postoffice-B. Then the postoffice matrix could be:
In the above example, there are Message-3 at Postoffice-B with 100% probability, and Message-1 at Postoffice-B with 15% probability. So if the spy visits this point, he/she will read one or two messages with this probability.
The scoring metrics of this problem is also different from the original. You get two numbers: the expected days to deliver all the messages and the probability of being caught by the spy. In the class we decided "the security is first" which means that the probability of success takes precedence over the speed.
The strategy of the spy is to pick a set of locations and dates which maximizes the probability of having messages. Then the program takes the messages which have FRACTION highest probabilities. Since this is a kind of NP-complete problem, there is no guarantee to find the best answer in some short time. The expected days is computed from the event matrix deterministically.
The evaluation program is post.py
.
On Sun machines it's placed at /home/yusuke/post.py
.
When you run this on your machine, you need Python 2.3 or newer.
First it reads parameters and then reads a protocol specification. You can give them with either a single (concatenated) file or multiple files. It reads files from given arguments or the standard input. You can also give or override some parameters with command-line options on the fly.
post.py [-d] [-H] [-m member] [-f fraction] [-p postoffice] [-v visit] [-r 1,2,...,n] [-i iteration] [file ...]
or$ ./yourprogram parameterfile > result $ ./post.py -H result > result.html $ netscape result.html
$ ./yourprogram parameterfile | ./post.py -m 4 -f 2 -p 2 -v 2 -r 50,50 -i 10000
The following options can be used to override parameters:
There are arithmetic errors with small probability. If the process is so spread out (e.g. the reachability has a wide distribution), it might not give a correct result.
How did I calcuate the probabilities?
In the probabilistic situation, each action doesn't occur at once. It is "spreading" over several days like clouds.
Consider the following:
Person: | 1 | 2 | ||
---|---|---|---|---|
day=0 | send m1 | |||
day=1 | recv m1 & send m2 (50%) | |||
day=2 | recv m2 (25%) | recv m1 & send m2 (50%) | - (Can we expect we can get both 2 and 1 with 0.25*0.50 = 12.5% ? - NO) | |
day=3 | recv m2 (50%) | |||
day=4 | recv m2 (25%) | |||
day=5 |
But you cannot get both Message 1 and 2 at once. Becasue these two event are exclusive (not independent).
To capture this, I firstnumbered each action and then constructed the "execution order graph":
Then I looked at every cell, and cluster every action which is preceding any action within the same cell (which means the date and location).
At the postoffice A:
Person: | 1 | 2 | ||
---|---|---|---|---|
day=0 | m1 | |||
day=1 | m1 by A1 (50%) | |||
day=2 | m2 by A2 (25%) | || | m1 by A1 (50%) | - (You can expect only either case.) |
day=3 | m2 by A2 (50%) | |||
day=4 | m2 by A2 (25%) | |||
day=5 |
But you can add the probability originating the same action, because if the spy sits at the same place for three days it eventually gets the message:
At the postoffice A:
Person: | 1 | 2 | ||
---|---|---|---|---|
day=0 | m1 | |||
day=1 | m1 by A1 (50%) | |||
day=2 | m2 by A2 (25%) | v | m1 by A1 (50%) | - (You can expect only either case.) |
day=3 | m2 by A2 (50%) | v | ||
day=4 | m2 by A2 (25%) | v | ___100% | |
day=5 |
Now suppose that third person were sending Message 2 at the same time (for some reason he already had that message):
At the postoffice A:
Person: | 1 | 3 | 2 | ||
---|---|---|---|---|---|
day=0 | m1 | ||||
day=1 | m2 by A3 (50%) | m1 by A1 (50%) | |||
day=2 | m2 by A2 (25%) + | m2 by A3 (50%) = 62.5% | || | m1 by A1 (50%) | - (now A2 and A3 can be in the same cluster.) |
day=3 | m2 by A2 (50%) | ||||
day=4 | m2 by A2 (25%) | ||||
day=5 |
Because there is not sequential guarantee between A2 and A3, we can conclude these two are independent.
Then we can combine the two probabilities (25% and 50%) as in:
In the simulated annealing, I tried to find a cell which subsumes other cells:
Person: | 1 | 2 | ||
---|---|---|---|---|
day=0 | m1 | |||
day=1 | m1 by A1 (50%) | |||
day=2 | 1:m2 by A2 (62.5%) | || | m1 by A1 (50%) | - (You can expect only either case.) |
day=3 | 2:m2 by A2 (50%) | |||
day=4 | 3:m2 by A2 (25%) | |||
day=5 |
These cells form a cluster. Now each step of simulated annealing is to find the best combination of the clusters.