CLICK HERE TO DOWNLOAD PPT ON Distributed Systems Principles and Paradigms
Distributed Systems Principles and Paradigms Presentation Transcript
1.Distributed Systems Principles and Paradigms
2.Communication & Synchronization
Why do processes communicate in DS?
To exchange messages
To synchronize processes
Why do processes synchronize in DS?
To coordinate access of shared resources
To order events
Why do processes communicate in DS?
To exchange messages
To synchronize processes
Why do processes synchronize in DS?
To coordinate access of shared resources
To order events
3.Time, Clocks and Clock Synchronization
Time
Why is time important in DS?
E.g. UNIX make utility (see Fig. 5-1)
Clocks (Timer)
Physical clocks
Logical clocks (introduced by Leslie Lamport)
Vector clocks (introduced by Collin Fidge)
Clock Synchronization
How do we synchronize clocks with real-world time?
How do we synchronize clocks with each other?
Time
Why is time important in DS?
E.g. UNIX make utility (see Fig. 5-1)
Clocks (Timer)
Physical clocks
Logical clocks (introduced by Leslie Lamport)
Vector clocks (introduced by Collin Fidge)
Clock Synchronization
How do we synchronize clocks with real-world time?
How do we synchronize clocks with each other?
4.Problem: Clock Skew – clocks gradually get out of synch and give different values
Solution: Universal Coordinated Time (UTC):
Formerly called GMT (Greenwich Mean Time)
Based on the number of transitions per second of the cesium 133 atom (very accurate).
At present, the real time is taken as the average of some 50 cesium-clocks around the world – International Atomic Time
Introduces a leap second from time to time to compensate that days are getting longer.
UTC is broadcasted through short wave radio (with the accuracy of +/- 1 msec) and satellite (Geostationary Environment Operational Satellite, GEOS, with the accuracy of +/- 0.5 msec).
Question: Does this solve all our problems? Don’t we now have some global timing mechanism?
Solution: Universal Coordinated Time (UTC):
Formerly called GMT (Greenwich Mean Time)
Based on the number of transitions per second of the cesium 133 atom (very accurate).
At present, the real time is taken as the average of some 50 cesium-clocks around the world – International Atomic Time
Introduces a leap second from time to time to compensate that days are getting longer.
UTC is broadcasted through short wave radio (with the accuracy of +/- 1 msec) and satellite (Geostationary Environment Operational Satellite, GEOS, with the accuracy of +/- 0.5 msec).
Question: Does this solve all our problems? Don’t we now have some global timing mechanism?
5.Clock Synchronization Principles
Principle I: Every machine asks a time server for the accurate time at least once every d/2r seconds (see Fig. 5-5).
But you need an accurate measure of round trip delay, including interrupt handling and processing incoming messages.
Principle II: Let the time server scan all machines periodically, calculate an average, and inform each machine how it should adjust its time relative to its present time.
Ok, you’ll probably get every machine in sync. Note: you don’t even need to propagate UTC time (why not?)
Principle I: Every machine asks a time server for the accurate time at least once every d/2r seconds (see Fig. 5-5).
But you need an accurate measure of round trip delay, including interrupt handling and processing incoming messages.
Principle II: Let the time server scan all machines periodically, calculate an average, and inform each machine how it should adjust its time relative to its present time.
Ok, you’ll probably get every machine in sync. Note: you don’t even need to propagate UTC time (why not?)
6.Clock Synchronization Algorithms
The Berkeley Algorithm
The time server polls periodically every machine for its time
The received times are averaged and each machine is notified of the amount of the time it should adjust
Centralized algorithm, See Figure 5-6
Decentralized Algorithm
Every machine broadcasts its time periodically for fixed length resynchronization interval
Averages the values from all other machines (or averages without the highest and lowest values)
Network Time Protocol (NTP)
the most popular one used by the machines on the Internet
uses an algorithm that is a combination of centralized/distributed
The Berkeley Algorithm
The time server polls periodically every machine for its time
The received times are averaged and each machine is notified of the amount of the time it should adjust
Centralized algorithm, See Figure 5-6
Decentralized Algorithm
Every machine broadcasts its time periodically for fixed length resynchronization interval
Averages the values from all other machines (or averages without the highest and lowest values)
Network Time Protocol (NTP)
the most popular one used by the machines on the Internet
uses an algorithm that is a combination of centralized/distributed
7.Network Time Protocol (NTP)
a protocol for synchronizing the clocks of computers over packet-switched, variable-latency data networks (i.e., Internet)
NTP uses UDP port 123 as its transport layer. It is designed particularly to resist the effects of variable latency
NTPv4 can usually maintain time to within 10 milliseconds (1/100 s) over the public Internet, and can achieve accuracies of 200 microseconds (1/5000 s) or better in local area networks under ideal conditions
visit the following URL to understand NTP in more detail
http://en.wikipedia.org/wiki/Network_Time_Protocol
8.The Happened-Before Relationship
a protocol for synchronizing the clocks of computers over packet-switched, variable-latency data networks (i.e., Internet)
NTP uses UDP port 123 as its transport layer. It is designed particularly to resist the effects of variable latency
NTPv4 can usually maintain time to within 10 milliseconds (1/100 s) over the public Internet, and can achieve accuracies of 200 microseconds (1/5000 s) or better in local area networks under ideal conditions
visit the following URL to understand NTP in more detail
http://en.wikipedia.org/wiki/Network_Time_Protocol
8.The Happened-Before Relationship
9.Logical Clocks (1/2)
Problem: How do we maintain a global view on the system’s behavior that is consistent with the happened-before relation?
Solution: attach a timestamp C(e) to each event e, satisfying the following properties:
P1: If a and b are two events in the same process, and a ?b, then we demand that C (a) < C (b)
P2: If a corresponds to sending a message m, and b to the receipt of that message, then also C (a) < C (b)
Problem: How do we attach a timestamp to an event when there’s no global clock? ? maintain a consistent set of logical clocks, one per process.
Problem: How do we maintain a global view on the system’s behavior that is consistent with the happened-before relation?
Solution: attach a timestamp C(e) to each event e, satisfying the following properties:
P1: If a and b are two events in the same process, and a ?b, then we demand that C (a) < C (b)
P2: If a corresponds to sending a message m, and b to the receipt of that message, then also C (a) < C (b)
Problem: How do we attach a timestamp to an event when there’s no global clock? ? maintain a consistent set of logical clocks, one per process.
10.Fidge’s Logical Clocks
11.Note: any process P can initiate taking a distributed snapshot
P starts by recording its own local state
P subsequently sends a marker along each of its outgoing channels
When Q receives a marker through channel C, its action depends on whether it had already recorded its local state:
– Not yet recorded: it records its local state, and sends the marker along each of its outgoing channels
– Already recorded: the marker on C indicates that the channel’s state should be recorded: all messages received before this marker and the time Q recorded its own state.
Q is finished when it has received a marker along each of its incoming channels
P starts by recording its own local state
P subsequently sends a marker along each of its outgoing channels
When Q receives a marker through channel C, its action depends on whether it had already recorded its local state:
– Not yet recorded: it records its local state, and sends the marker along each of its outgoing channels
– Already recorded: the marker on C indicates that the channel’s state should be recorded: all messages received before this marker and the time Q recorded its own state.
Q is finished when it has received a marker along each of its incoming channels
12.Election Algorithms
Principle: Many distributed algorithms require that some process acts as a coordinator. The question is how to select this special process dynamically.
Note: In many systems the coordinator is chosen by hand (e.g., file servers, DNS servers). This leads to centralized solutions => single point of failure.
Question: If a coordinator is chosen dynamically, to what extent can we speak about a centralized or distributed solution?
Question: Is a fully distributed solution, i.e., one without a coordinator, always more robust than any centralized/coordinated solution?
13.Election in a Ring
Principle: Process priority is obtained by organizing processes into a (logical) ring. Process with the highest priority should be elected as coordinator.
Any process can start an election by sending an election message to its successor. If a successor is down, the message is passed on to the next successor.
If a message is passed on, the sender adds itself to the list. When it gets back to the initiator, everyone had a chance to make its presence known.
The initiator sends a coordinator message around the ring containing a list of all living processes. The one with the highest priority is elected as coordinator. See Figure 5-12.
Principle: Many distributed algorithms require that some process acts as a coordinator. The question is how to select this special process dynamically.
Note: In many systems the coordinator is chosen by hand (e.g., file servers, DNS servers). This leads to centralized solutions => single point of failure.
Question: If a coordinator is chosen dynamically, to what extent can we speak about a centralized or distributed solution?
Question: Is a fully distributed solution, i.e., one without a coordinator, always more robust than any centralized/coordinated solution?
13.Election in a Ring
Principle: Process priority is obtained by organizing processes into a (logical) ring. Process with the highest priority should be elected as coordinator.
Any process can start an election by sending an election message to its successor. If a successor is down, the message is passed on to the next successor.
If a message is passed on, the sender adds itself to the list. When it gets back to the initiator, everyone had a chance to make its presence known.
The initiator sends a coordinator message around the ring containing a list of all living processes. The one with the highest priority is elected as coordinator. See Figure 5-12.
14.Nested Transactions
Constructed from a number of subtransactions
The top-level transaction may create children that run in parallel with one another to gain performance or simplify programming
Each of these children is called a subtransaction and it may also have one or more subtransactions
When any transaction or subtransaction starts, it is conceptually given a private copy of all data in the entire system for it to manipulate as it wishes
If it aborts, its private space is destroyed
If it commits, its private space replaces the parent’s space
If the top-level transaction aborts, all the changes made in the subtransactions must be wiped out
Constructed from a number of subtransactions
The top-level transaction may create children that run in parallel with one another to gain performance or simplify programming
Each of these children is called a subtransaction and it may also have one or more subtransactions
When any transaction or subtransaction starts, it is conceptually given a private copy of all data in the entire system for it to manipulate as it wishes
If it aborts, its private space is destroyed
If it commits, its private space replaces the parent’s space
If the top-level transaction aborts, all the changes made in the subtransactions must be wiped out
15.Implementing Transactions
Private Workspace
Gives a private workspace (i.e., all the data it has access to) to a process when it begins a transaction
Writeahead Log
Files are actually modified in place but before any block is changed, a record is written to a log telling
which transaction is making the change
which file and block is being changed
what the old and new values are
Only after the log has been written successfully, the change is made to the file
Private Workspace
Gives a private workspace (i.e., all the data it has access to) to a process when it begins a transaction
Writeahead Log
Files are actually modified in place but before any block is changed, a record is written to a log telling
which transaction is making the change
which file and block is being changed
what the old and new values are
Only after the log has been written successfully, the change is made to the file
16.Serializability
Two operations conflict is they operate on the same data and if at least one of them is a write operation
read-write conflict: exactly one of the operations is a write
write-write conflict: involves more than one write operations
Concurrency control algorithms can generally be classified by looking at the way read and write operations are synchronized
Using locking
Explicitly ordering operations using timestamps
Two operations conflict is they operate on the same data and if at least one of them is a write operation
read-write conflict: exactly one of the operations is a write
write-write conflict: involves more than one write operations
Concurrency control algorithms can generally be classified by looking at the way read and write operations are synchronized
Using locking
Explicitly ordering operations using timestamps
17.Two-Phase Locking (1)
In two-phase locking (2PL), the scheduler first acquires all the locks it needs during the growing (1st) phase, and then releases them during the shrinking (2nd) phase
See the rules on pg. 284
In two-phase locking (2PL), the scheduler first acquires all the locks it needs during the growing (1st) phase, and then releases them during the shrinking (2nd) phase
See the rules on pg. 284
18.In strict two-phase locking, the shrinking phase does not take place until the transaction has finished running and has either committee or aborted.
Posts
0 comments