02-11-2012, 12:35 PM
Termination Detection Algorithm for Distributed Computations
Termination Detection.pdf (Size: 40.43 KB / Downloads: 22)
Initiation
• Machine nr.0 initiates the “probe”
• Ring-Minimize the signaling traffic
• Assumption about passivity
Presence of Messages
• P0 is falsified -> Weaker invariant P0 V
P1
• P1: (E j: 0<=j<=t : machine nr.j is black)
– A machine sending a message to a machine with a
number higher than it’s own makes itself Black
• Termination Detection
– (t=0^machine nr.0 is white) => ~P1
• P1 may be falsified and hence invariant P0 V
P1 – Weaker invariant P0 V P1 V P2
• P2 : the token is black
– nr. i+1 hands over a black token to nr. i if it itself is
black
• Termination detection
– Token is white => ~P2
Unsuccessful Probe
• A black token at nr. 0 or a black nr. 0
• Next probe
– nr. 0 makes itself white and sends a white token to
nr. N-1
• Upon transmission of the token to nr. i
machine nr. i+1 becomes white (P1 is not
falsified)
Termination
• A probe initiated after termination will end up
with all machines white, and , hence a next
probe is guaranteed to return a white token to
a white machine nr.0.
• Simplified rule – A machine sending a
message makes itself black.
• Assumption of instantaneous messaging.