02-11-2012, 12:48 PM
Performance of Token-based Distributed Mutual Exclusion Algorithms
Performance of Token.pdf (Size: 107.25 KB / Downloads: 27)
Token-based Algorithms
• A single token circulates through the system
• A process wants to enter CS, it requests token
• A process gets the token, it can enter CS (in
general)
• Message Types
– Token
– Request
Raymond’s Token DMX
• Based on a tree structure
• Each node holds a pointer to a node that
either holds the token or points to where the
token is
• A request is held locally and is sent through
the tree until it reaches the token
• Token traverses the request path until it
reaches the requester
Suzuki-Kasami Token DMX
• Fully connected network
• Requester broadcasts requests to all other
nodes with sequence number of request
• Before sending the token, holder calculates
which requests have not been satisfied and
enters those into the token request queue
• Send token to the request at the top of the
queue
Initial Verification Experiments
Setup
• Done to ensure correctness and begin
experimentation
• Attributes
– Synchronization Delay
• Number of messages between each CS entry
– Message Complexity
• Total number of messages per CS entry
• Variables
– Network size
• Range from 5 to 30 for Suzuki-Kasami (why?)
• Range from 5 to 60 for Raymond (why?)
– Contention level
• low (sequential request/release) and high (all request/all release)
Conclusions
• Raymond
– Better performance with many children
– Log(n)/log© message complexity and sync delay
• Suzuki Kasami
– Very low sync delay
– Steady increase in total token forwards for high
contention system
• Neither algorithm guarantees granting CS in
timestamp order