Transcript election message

Synchronization (continued)
CS-4513
D-Term 2007
(Slides include materials from Operating System Concepts, 7th ed., by Silbershatz, Galvin, & Gagne,
Modern Operating Systems, 2nd ed., by Tanenbaum, and Distributed Systems: Principles & Paradigms, 2nd
ed. By Tanenbaum and Van Steen)
CS-4513, D-Term 2007
Election Algorithms
1
Review
• Real time not very good tool for some kinds
of synchronization is distributed systems
• Logical “clocks”
• Always monotonic
• Moved forward whenever a “later” message appears
• Mutual exclusion
• Centralized control
• Decentralized & Distributed control
• Token control
CS-4513, D-Term 2007
Election Algorithms
2
NTP (Network Time Protocol)
T2
B
A
T3
T4
T1
• Question: what is  = TB – TA?
• Assume transit time is approximately the same both ways
• Assume that B is the time server that A wants to
synchronize to
CS-4513, D-Term 2007
Election Algorithms
3
NTP (Network Time Protocol)
T2
B
A
T3
T4
T1
• A knows (T4 – T1) from its own clock
• B reports T3 and T2 in response to NTP request
• A computes total transit time of
T4  T1   T3  T2 
CS-4513, D-Term 2007
Election Algorithms
4
NTP (Network Time Protocol)
T2
B
A
T3
T4
T1
• One-way transit time is approximately ½ total, i.e.,
T4  T1   T3  T2 
2
• B’s clock at T4 reads approximately

T4  T1   T3  T2  T4  T1   T2  T3 
T3 

2
2
CS-4513, D-Term 2007
Election Algorithms
5
NTP (Network Time Protocol)
T2
B
A
T3
T4
T1
• B’s clock at T4 reads approximately (from previous slide)
T4  T1   T2  T3 
2
• Thus, difference between B and A clocks at T4 is
T4  T1   T2  T3   T  T2  T1   T3  T4 
4
2
2
CS-4513, D-Term 2007
Election Algorithms
6
Questions?
CS-4513, D-Term 2007
Election Algorithms
7
Election Algorithms
• If we are using one process as a coordinator
for a shared resource …
• …how do we select that one process?
• Often, there is no owner or master that is
automatically considered as coordinator
• E.g., Grapevine, there is no owner for a Registry
• By contrast:–DNS has a master for every domain
CS-4513, D-Term 2007
Election Algorithms
8
Solution – an Election
• All nodes currently involved get together to
choose a coordinator
• If the coordinator crashes or becomes
isolated, elect a new coordinator
• If a previously crashed or isolated node,
comes on line, a new election may have to
be held.
CS-4513, D-Term 2007
Election Algorithms
9
Election Algorithms
• Wired systems
• Bully algorithm
• Ring algorithm
• Wireless systems
• Very large-scale systems
CS-4513, D-Term 2007
Election Algorithms
10
Bully Algorithm
• Assume
• All processes know about each other
• Processes numbered uniquely
• Suppose P notices no coordinator
• Sends election message to all higher numbered
processes
• If none response, P takes over as coordinator
• If any responds, P yields
• …
CS-4513, D-Term 2007
Election Algorithms
11
Bully Algorithm (continued)
• …
• Suppose Q receives election message
• Replies OK to sender, saying it will take over
• Sends a new election message to higher numbered
processes
• Repeat until only one process left standing
• Announces victory by sending message saying that
it is coordinator
CS-4513, D-Term 2007
Election Algorithms
12
Bully Algorithm (continued)
CS-4513, D-Term 2007
Election Algorithms
13
Bully Algorithm (continued)
• …
• Suppose R comes back on line
• Sends a new election message to higher numbered
processes
• Repeat until only one process left standing
• Announces victory by sending message saying that
it is coordinator (if not already coordinator)
• Existing (lower numbered) coordinator yields
• Hence the term “bully”
CS-4513, D-Term 2007
Election Algorithms
14
Alternative – Ring Algorithm
• All processed organized in ring
• Independent of process number
• Suppose P notices no coordinator
• Sends election message to successor with own
process number in body of message
• (If successor is down, skip to next process, etc.)
• Suppose Q receives an election message
• Adds own process number to list in message body
• …
CS-4513, D-Term 2007
Election Algorithms
15
Alternative – Ring Algorithm
• Suppose P receives an election message
with its own process number in body
• Changes message to coordinator message,
preserving body
• All processes recognize highest numbered process
as new coordinator
• If multiple messages circulate …
• …they will all contain same list of processes
(eventually)
• If process comes back on-line
• Calls new election
CS-4513, D-Term 2007
Election Algorithms
16
Ring Algorithm (continued)
CS-4513, D-Term 2007
Election Algorithms
17
Wireless Networks
• Different assumptions
• Message passing is less reliable
• Network topology constantly changing
• Expanding ring of broadcast
• Election messages
• Decision rules for when to yield
• Not very well developed.
• Topic of current research
CS-4513, D-Term 2007
Election Algorithms
18
Very Large Scale Networks
• Sometimes more than one node should be
selected
• Nodes organized as peers and super-peers
• Elections held within each peer group
• Super-peers coordinate among themselves
CS-4513, D-Term 2007
Election Algorithms
19
Questions?
CS-4513, D-Term 2007
Election Algorithms
20
Digression
Domain Name Service
CS-4513, D-Term 2007
Election Algorithms
21
DNS
• Maps names of the form
www.cs.wpi.edu
to IP addresses
• Maps aliases to names
• Maps mailbox requests to names
• Maps service requests to names
• Maps IP addresses to names
• I.e., reverse mapping
CS-4513, D-Term 2007
Election Algorithms
22
DNS Naming Hierarchy
CS-4513, D-Term 2007
Election Algorithms
23
Iterative Resolution of Names
CS-4513, D-Term 2007
Election Algorithms
24
Iterative Resolution of Names
CS-4513, D-Term 2007
Election Algorithms
25
DNS Domain Registry Database
• Text file containing records
• Each record is {Name, Type, value(s)}
CS-4513, D-Term 2007
Election Algorithms
26
Example
CS-4513, D-Term 2007
Election Algorithms
27
DNS Implementation
• One master copy per domain or subdomain
• Edited manually by system administrator
• Multiple slave copies
• Automatically copied / updated periodically from
master
• Stored in file on slave server, reloaded up restart
• Caching in DNS clients
• Lots and lots of caching
• Entries include TTL (time-to-live) specification
CS-4513, D-Term 2007
Election Algorithms
28
Implementation in Linux/Unix
• BIND — Berkeley Internet Name Domain
• http://www.bind9.net/
• named — the Name Daemon
– Implements local DNS service
– Multiple databases
• Primary or secondary
• Secondary database points back to primary
– Pointer to “higher level” service
• For resolving names not in own database
CS-4513, D-Term 2007
Election Algorithms
29
Example
• Want to find www.cs.wpi.edu
• My DNS contacts DNS server 68.87.71.226
• A Comcast server specified in my DHCP lease
• Comcast DNS service
•
•
•
•
Almost certainly has root (global) domain in cache
Probably has many .edu entries in cache (very large)
Possibly has .wpi.edu in cache (many local users)
May have .cs.wpi.edu
• Consults cache or official server for IP address
• nslookup
CS-4513, D-Term 2007
Election Algorithms
30
Example (continued)
C:\>nslookup cs.wpi.edu
Server: cns.chelmsfdrdc2.ma.boston.comcast.net
Address: 68.87.71.226
Non-authoritative answer:
Name:
cs.wpi.edu
Address: 130.215.28.181
CS-4513, D-Term 2007
Election Algorithms
31
Some Special Cases
• Google
• Yahoo
• MSN
• Need to distribute names geographically
• Need to distribute different addresses for same name
• Special handling of replicated databases
• More (perhaps) later in term
CS-4513, D-Term 2007
Election Algorithms
32
Naming Privacy
• Problem:– corporations need to have own
domains
• www.merl.com
• Some public hosts – mail server, web server, etc.
• Does not want to expose names of internal
hosts to outside world
• E.g., proprietary stuff
• But wants to make them visible internally
• hotspur.merl.com
CS-4513, D-Term 2007
Election Algorithms
33
Solution
• Two name services for same domain name!
• Internal
• External
• External — visible to Internet (DMZ)
• Database contains only a few names
• Points to other internet DNS’s for resolution of internet names
• Internal — seen only by internal hosts
• Database contains all internal names
• Points to external version for resolution of internet names
CS-4513, D-Term 2007
Election Algorithms
34
Result
• Internal names can be resolved internally,
not externally
• hotspur.merl.com
• Internal names and IP addresses are
invisible on Internet
• All external names can be resolved
internally
• Two levels of indirection
CS-4513, D-Term 2007
Election Algorithms
35
Questions?
Next Topic
CS-4513, D-Term 2007
Election Algorithms
36