The Post Office Problem

"Do you know the answer?" "No, you know it?" "No."

"Now I know the answer." "Now I know it too."

Ahh! I know what are you two's answers!

DESCRIPTION: See this page

Source Code: post.cpp

More description and a nice verifier from Yusuke Shinyama: See this page

Three practice exercise for post office problem:

Different constraint: Only one post office and every body has an option to send a message 'all clear'. Only member 1 knows the start time of the protocol.

(a) The spy can look in the post office only once. Each participant has only 16 envelopes. Should take no more than two day if no delay.

Solution: @1 send his/her message to everyone. Others send their messages immediately after they got m1.

Correctness: Assume @X received m1 latest. Then mX will not appear in the post office before m1 disappeared. So these two messages were mutually exclusive in the post office. Thus the spy can't success by taking only one visit.

Time: It takes 2 days if there is no delay in message delivering.

(b) The spy can look in the post office twice. Each participant has only 17 envelopes. Should take no more than five day if no delay.

Solution: @1 send m1 to @2~@16. After receiving m1, @2~@16 sent their message to all other guys, include @17. After getting m2~m16, @17 broadcasts m17. Then @2~@16 send 'all clear' to @1. @1 will send m1 to @17 after receiving m17 and 'all clear' from @2~@16.

Correctness: The spy can look up at most 15 messages in the first two days. (NOT 16 due to the same reason as above) Since m17 is mutually exclusive from others messages, the spy can not see all messages on the other visit.

Time: It takes 5 days if there is no delay in message delivering.

(c) The spy can look in the post office twice but need only see 10 messages to do severe damage. Each participant has 35 envelopes. Should take no more than eight day if no delay.

Solution: In first day member 1 broadcast his/her message, member 2~5 broadcast their messages right after receiving message1. Every one should send an 'all clear' message to member 6~9 after collecting message 1~5 (4 extra envelopes needed). After getting everybody's 'all clear' signal, member 6~9 then broadcast their messages. Again every one sends an 'all clear' message to 10~13. Then broadcast message 10~13, 'all clear' for 10~13, broadcast 14~17 and done.

Correctness: The maximum messages the spy could look up once will be 5(1~5), all other times there will be at most 4 messages in the post office, so the protocol is safe.

Time: It takes 8 days if there is no delay in message delivering.

My Algorithm:

In this problem, I implemented a well-known SEND-ACK model.

First, I defined S(Safe) = (FRACTION-1)/VISIT. If every day there are at most S messages in any post office, then the spy can't get more than S*VISIT = FRACTION-1 messages overall.

Then, on odd days, S*P (P = number of post offices) people in turn broadcasted their messages. On even days, all people send an ACK message to next S*P people once they successfully received all messages delivered on last day.

After all, I allowed some extra messages appeared in post office on the first day if FRACTION-1>S*VISIT. So there will be FRACTION-1-(VISIT-1)*S messages in post office A on day 1.

Number of days needed to pass all messages without delay was given by the following formula:

Here is an example for S*P=8 :

A finite automata generated by Yusuke's verifier:

MESSAGE=6 FRACTION=5 VISIT=2 P=2

If there is no ACK message:

If S = 1

Claim: If S=1, Broadcast is not allowed without ACK message. (Why?) Since every one must get (N-1) messages, N(N-1) delivery are necessary. So just find an Eular tour in Kn (Complete directed graph) and it would always take N(N-1) days to finish the protocol. In this case, more post offices

A simple protocol if S = 2

Now I designed a protocol if we were going to limit the maximum number of messages in any post office not exceed 2 (N=MESSAGE):

                                                                       Broadcast 1    

                           2 ------> 1 -----> N -----> N-1 ---  ................   -------->  4 --------> 3 ---- (pass message 2 on this line)

    with message        1              2           1, 2                                        1, 2              1, 2             |

                                                                      Broadcast 3    <-----------------------------------

                          4 -------> 3 ------->  2 -------> 1 ----> N -- .............. --->  6--------> 5 ----- (pass message 4 on this line)

   with message           3               4             3, 4         3, 4                        3, 4           3, 4 

                                                                             ....

                                                                      Broadcast 2k-1

                           2k -----> 2k-1 -----> 2k-2 -- ... --> 1 ----------> N ---------> N-1 --- ... --> 2k+1  (pass message 2k on this line)

     with message      2k-1              2k              2k-1, 2k      2k-1, 2k       2k-1, 2k           2k-1, 2k

Time: It takes (N2-N+2)/2 days assume no delay in message delivering when N is odd and takes N2/2 days if N is even.

If there are P post offices, after the first one broadcast his/her message, members could be divided into P equal size groups. Each group send messages with different post office. Thus the protocol was speeded up by a factor of P. So the number of days needed will be roughly N2/2P.

If S > 2

Interesting. Not yet solved.

back


Chien-I Liao