Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Task: Faulty Links
发信站: 哈工大紫丁香 (2002年03月29日13:53:31 星期五), 站内信件

Task: Faulty Links
Figure 1: Connection from P to C via two L-links and protocol handlers S and
 R
This task is about the communication of messages from a producer to a consum
er (see Figure 1). A message is either a bit in { 0,1 } or an error indicato
r E.
Producer P produces a sequence of messages on its output channel x (see Figu
re 2). Consumer C consumes a sequence of messages from its input channel y (
see Figure 3). Let us denote the produced sequence by p_i, where p_i in { 0,
1 } for 0<=i, and the consumed sequence by c_i (0<=i).
We would like to guarantee that C consumes exactly the sequence produced by 
P, that is, p_i = c_i for 0<=i. In particular, every bit sent by P should ar
rive at C exactly once in a finite number of steps. One solution is obtained
 by connecting P's output channel directly to C's input channel (see Figure 
4). In this task, however, P and C are far apart and, unfortunately, we have
 to connect them by faulty communication links.
A faulty communication link L, from now on called a link for short, has an i
nput channel x and an output channel y (see Figure 5). It copies each messag
e received on x to y, but it may at times damage messages. Damage is detecta
ble: a damaged message has a special appearance, distinct from undamaged mes
sages: E not in { 0,1 } (error).
A link that damages all messages from a certain moment onward would be usele
ss for our purposes, because then it cannot be guaranteed that bits always a
rrive in a finite number of steps. We postulate that a link does not behave 
this way: a link will damage only a finite number of consecutive messages (s
ee Figure 5). To put it differently: when a message is repeated often enough
 it is eventually transmitted correctly.
Let us connect P's output channel to the input channel of a link L, and L's 
output channel to C's input channel (see Figure 6). This configuration need 
not work as desired, because messages may be damaged and hence lost. For exa
mple, we can have p_0 = 0 and c_0 = E.
Retransmission Protocol
We can prevent the loss of messages by retransmitting damaged messages. For 
this purpose we also need a link in the opposite direction, called the backw
ard link; the other link is called the forward link. The retransmission prot
ocol is implemented by sender S on P's side and receiver R on C's side. S an
d R are connected to each other by the forward and backward links (see Figur
e 1).
Sender S (see Figure 7) inputs a message from P and sends it via the forward
 link to R. S then waits for an acknowledge bit from R via the backward link
. Bit 1 indicates correct reception, bit 0 damaged reception. S will repeate
dly retransmit the message until a 1 is received, after which the next messa
ge from P is processed.
Receiver R (see Figure 8) inputs a message from the forward link. When a dam
aged message is received, R requests a retransmission by sending a 0 to S vi
a the backward link. Once an undamaged message is received, R outputs the me
ssage to C and sends a 1 along the backward link to S, after which processin
g continues with the next message.
Figure 9 shows a scenario for the transmission of p_0=0 and p_1=1, where tra
nsmission of p_0 involves a damaged message. The left-hand column, labeled T
, shows the time steps. The other columns are labeled with channel identifie
rs and show the values sent along these channels.
Subtask A
The above protocol does not always work as desired. Give a scenario showing 
this. Indicate clearly on the accompanying Scenario Form A which values are 
communicated at what moments along which channels. You need not use use all 
time slots shown.
Subtask B
We change the programs for sender S and receiver R to improve the protocol. 
Sender S (see Figure 10) now tags each bit received from P alternatingly by 
0 and 1. Otherwise, S works as before. A message m in TMsg with m<>E is a ta
gged bit: m.v is the bit value and m.t the tag.
Receiver R (see Figure 11) now has a local variable u in { 0,1 } indicating 
the tag it expects. Upon reception of a message via the forward link, the re
ceiver repeats the following. When the message is damaged, R sends back 0. O
therwise, when the tag differs from u, it sends back 1 but does not deliver 
m to C. Only when an undamaged messaged with the expected tag arrives, is it
 delivered to C and is the expected tag updated. After all cases, R awaits a
 new message.
The programs for P, L, and C, and the way they are connected remain the same
, except that the forward link now deals with messages that are tagged bits 
(TMsg instead of Msg).
Give a scenario showing that the improved protocol does not work as desired.
 Indicate clearly on the accompanying Scenario Form B which values are commu
nicated at what moments along which channels. You need not use all time slot
s shown. Use an arrow to indicate a repetition of events.
Subtask C
Change sender S and receiver R to make the protocol work correctly. Write yo
ur answer on the Program Forms. You need not fill all empty lines.
You are only allowed to change the program text of S and R appearing between
 `|' and `end'. You are NOT allowed to add variables to S or R, or to change
 P, L, or C, or to change the way things are connected. You are also NOT all
owed to invent new language constructs (statements or expressions).
----------------------------------------------------------------------------
----
P = proc (x!Msg).
begin i: var Nat & m: var Msg
| i := 0
; forever
  do m := p_i ; x!m
   ; i := i+1
  od
end
Figure 2: Program for producer P
----------------------------------------------------------------------------
----
C = proc (y?Msg).
begin i: var Nat & m: var Msg
| i := 0
; forever
  do y?m ; c_i := m
   ; i := i+1
  od
end
Figure 3: Program for consumer C
----------------------------------------------------------------------------
----
Figure 4: Direct connection from P to C
----------------------------------------------------------------------------
----
L = proc (x?Msg & y!Msg).
begin m: var Msg & n: var Nat
| forever
  do n :in Nat
   ; for n do x?m ; y!E od
   ; x?m ; y!m
  od
end
Figure 5: Program for faulty link L
----------------------------------------------------------------------------
----
Figure 6: Connection from P to C via L
----------------------------------------------------------------------------
----
S = proc (x?Msg & sf!Msg & bs?Msg).
begin m, a: var Msg
| x?m
; forever
  do sf!m ; bs?a
   ; if a = 1 then x?m fi
  od
end
Figure 7: Program 1 for sender S
----------------------------------------------------------------------------
----
R = proc (fr?Msg & rb!Msg & y!Msg).
begin m: var Msg
| forever
  do fr?m
   ; if m = E then rb!0
     else y!m ; rb!1
     fi
  od
end
Figure 8: Program 1 for receiver R
----------------------------------------------------------------------------
----
_________________________________
| T | x | sf | fr | rb | bs | y |
|___|___|____|____|____|____|___|
| 0 | 0 |    |    |    |    |   |
|___|___|____|____|____|____|___|
| 1 |   | 0  |    |    |    |   |
|___|___|____|____|____|____|___|
| 2 |   |    | E  |    |    |   |
|___|___|____|____|____|____|___|
| 3 |   |    |    | 0  |    |   |
|___|___|____|____|____|____|___|
| 4 |   |    |    |    | 0  |   |
|___|___|____|____|____|____|___|
| 5 |   | 0  |    |    |    |   |
|___|___|____|____|____|____|___|
| 6 |   |    | 0  |    |    |   |
|___|___|____|____|____|____|___|
| 7 |   |    |    |    |    | 0 |
|___|___|____|____|____|____|___|
| 8 |   |    |    | 1  |    |   |
|___|___|____|____|____|____|___|
| 9 |   |    |    |    | 1  |   |
|___|___|____|____|____|____|___|
|10 | 1 |    |    |    |    |   |
|___|___|____|____|____|____|___|
|11 |   | 1  |    |    |    |   |
|___|___|____|____|____|____|___|
|12 |   |    | 1  |    |    |   |
|___|___|____|____|____|____|___|
|13 |   |    |    |    |    | 1 |
|___|___|____|____|____|____|___|
|   |   |    |    |    |    |   |
|___|___|____|____|____|____|___|
|   |   |    |    |    |    |   |
|___|___|____|____|____|____|___|
|   |   |    |    |    |    |   |
|___|___|____|____|____|____|___|
|   |   |    |    |    |    |   |
|___|___|____|____|____|____|___|
|   |   |    |    |    |    |   |
|___|___|____|____|____|____|___|
|   |   |    |    |    |    |   |
|___|___|____|____|____|____|___|
|   |   |    |    |    |    |   |
|___|___|____|____|____|____|___|
|   |   |    |    |    |    |   |
|___|___|____|____|____|____|___|
|   |   |    |    |    |    |   |
|___|___|____|____|____|____|___|
|   |   |    |    |    |    |   |
|___|___|____|____|____|____|___|
| T | x | sf | fr | rb | bs | y |
|___|___|____|____|____|____|___|
Figure 9: Scenario for p_0=0 and p_1=1 involving a retransmission for p_0
----------------------------------------------------------------------------
----
S = proc (x?Msg & sf!TMsg & bs?Msg).
begin m: var TMsg & a: var Msg
| m.t := 0 ; x?m.v
; forever
  do sf!m ; bs?a
   ; if a = 1
     then m.t := 1-m.t ; x?m.v
     fi
  od
end
Figure 10: Program 2 for sender S
----------------------------------------------------------------------------
----
R = proc (fr?TMsg & rb!Msg & y!Msg).
begin m: var TMsg & u: var Nat
| u := 0
; forever
  do fr?m
   ; if m = E then rb!0
     else if m.t = u
          then y!m.v ; u := 1-u
          fi
        ; rb!1
     fi
  od
end
Figure 11: Program 2 for receiver R

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]