Warning:
JavaScript is turned OFF. None of the links on this page will work until it is reactivated.
If you need help turning JavaScript On, click here.
This Concept Map, created with IHMC CmapTools, has information related to: Ch 10, Accuracy of NTP For each pair of messages between two servers, NTP estimates an offset o, between the two clocks and a delay di (total time for the two messages, which take t and t’) Ti-2 = Ti-3 + t + o and Ti = Ti-1 + t’ - o This gives us (by adding the equations) : di = t + t’ = Ti-2 - Ti-3 + Ti - Ti-1 Also (by subtracting the equations) o = oi + (t’ - t )/2 where oi = (Ti-2 - Ti-3 + Ti-1 - Ti)/2 Using the fact that t, t’ɬ it can be shown that oi - di /2 ≤ o ≤ oi + di /2 . Thus oi is an estimate of the offset and di is a measure of the accuracy NTP servers filter pairs <oi, di>, estimating reliability from variation, allowing them to select peers Accuracy of 10s of millisecs over Internet paths (1 on LANs) theory Lamport’s logical clocks A logical clock is a monotonically increasing software counter. It need not relate to a physical clock. Each process pi has a logical clock, Li which can be used to apply logical timestamps to events LC1: Li is incremented by 1 before each event at process pi LC2: (a) when process pi sends message m, it piggybacks t = Li (b) when pj receives (m,t) it sets Lj := max(Lj, t) and applies LC1 before timestamping the event receive (m), Why Peer-to-Peer Networking? The Internet has three valuable fundamental assets — information, bandwidth, and computing resources — all of which are vastly under utilized, partly due to the traditional client-server computing model. Information - Hard to find, impossible to catalog and index Bandwidth - Hot links get hotter, cold ones stay cold Computing resources - Heavily loaded nodes get overloaded, idle nodes remain idle also Computing Resources Moore’s Law: processor speed doubles every 18 months Computing devices ( server, PC, PDA, cell phone) are more powerful than ever Storage capacity has increased dramatically Computation still accumulates around data centers, We need to measure time accurately: to know the time an event occurred at a computer to do this we need to synchronize its clock with an authoritative external clock Algorithms for clock synchronization useful for concurrency control based on timestamp ordering authenticity of requests e.g. in Kerberos There is no global clock in a distributed system this chapter discusses clock accuracy and synchronisation Logical time is an alternative It gives ordering of events - also useful for consistency of replicated data in which Each computer in a DS has its own internal clock used by local processes to obtain the value of the current time processes on different computers can timestamp their events but clocks on different computers may give different times computer clocks drift from perfect time and their drift rates differ from one another. clock drift rate: the relative amount that a computer clock differs from a perfect clock Even if clocks on all computers in a DS are set to the same time, their clocks will eventually vary quite significantly unless corrections are applied, Peer-to-Peer An alternative to the client/server model of distributed computing is the peer-to-peer model. Client/server is inherently hierarchical, with resources centralized on a limited number of servers. In peer-to-peer networks, both resources and control are widely distributed among nodes that are theoretically equals. (A node with more information, better information, or more power may be “more equal,” but that is a function of the node, not the network controllers.) In which Decentralization A key feature of peer-to-peer networks is decentralization. This has many implications. Robustness, availability of information and fault-tolerance tends to come from redundancy and shared responsibility instead of planning, organization and the investment of a controlling authority. On the Web both content providers and gateways try to profit by controlling information access. Access control is more difficult in peer-to-peer, although Napster depended on a central index., Berkeley algorithm Cristian’s algorithm - a single time server might fail, so they suggest the use of a group of synchronized servers it does not deal with faulty servers Berkeley algorithm (also 1989) An algorithm for internal synchronization of a group of computers A master polls to collect clock values from the others (slaves) The master uses round trip times to estimate the slaves’ clock values It takes an average (eliminating any above some average round trip time or with faulty clocks) It sends the required adjustment to the slaves (better than sending the time which depends on the round trip time) Measurements 15 computers, clock synchronization 20-25 millisecs drift rate < 2x10-5 If master fails, can elect a new master to take over (not in bounded time) contains synchronisation of servers The synchronization subnet can reconfigure if failures occur, e.g. a primary that loses its UTC source can become a secondary a secondary that loses its primary can use another primary Modes of synchronization: Multicast A server within a high speed LAN multicasts time to others which set clocks assuming some delay (not very accurate) Procedure call A server accepts requests from other computers (like Cristiain’s algorithm). Higher accuracy. Useful if no hardware multicast. Symmetric Pairs of servers exchange messages containing time information Used where very high accuracies are needed (e.g. for higher levels), Each computer in a DS has its own internal clock used by local processes to obtain the value of the current time processes on different computers can timestamp their events but clocks on different computers may give different times computer clocks drift from perfect time and their drift rates differ from one another. clock drift rate: the relative amount that a computer clock differs from a perfect clock Even if clocks on all computers in a DS are set to the same time, their clocks will eventually vary quite significantly unless corrections are applied also Berkeley algorithm Cristian’s algorithm - a single time server might fail, so they suggest the use of a group of synchronized servers it does not deal with faulty servers Berkeley algorithm (also 1989) An algorithm for internal synchronization of a group of computers A master polls to collect clock values from the others (slaves) The master uses round trip times to estimate the slaves’ clock values It takes an average (eliminating any above some average round trip time or with faulty clocks) It sends the required adjustment to the slaves (better than sending the time which depends on the round trip time) Measurements 15 computers, clock synchronization 20-25 millisecs drift rate < 2x10-5 If master fails, can elect a new master to take over (not in bounded time), Lamport’s logical clocks A logical clock is a monotonically increasing software counter. It need not relate to a physical clock. Each process pi has a logical clock, Li which can be used to apply logical timestamps to events LC1: Li is incremented by 1 before each event at process pi LC2: (a) when process pi sends message m, it piggybacks t = Li (b) when pj receives (m,t) it sets Lj := max(Lj, t) and applies LC1 before timestamping the event receive (m) in which Summary on time and clocks in distributed systems accurate timekeeping is important for distributed systems. algorithms (e.g. Cristian’s and NTP) synchronize clocks in spite of their drift and the variability of message delays. for ordering of an arbitrary pair of events at different computers, clock synchronization is not always practical. the happened-before relation is a partial order on events that reflects a flow of information between them. Lamport clocks are counters that are updated according to the happened-before relationship between events. vector clocks are an improvement on Lamport clocks, we can tell whether two events are ordered by happened-before or are concurrent by comparing their vector timestamps, Decentralization A key feature of peer-to-peer networks is decentralization. This has many implications. Robustness, availability of information and fault-tolerance tends to come from redundancy and shared responsibility instead of planning, organization and the investment of a controlling authority. On the Web both content providers and gateways try to profit by controlling information access. Access control is more difficult in peer-to-peer, although Napster depended on a central index. why p2p Why Peer-to-Peer Networking? The Internet has three valuable fundamental assets — information, bandwidth, and computing resources — all of which are vastly under utilized, partly due to the traditional client-server computing model. Information - Hard to find, impossible to catalog and index Bandwidth - Hot links get hotter, cold ones stay cold Computing resources - Heavily loaded nodes get overloaded, idle nodes remain idle, synchronisation of servers The synchronization subnet can reconfigure if failures occur, e.g. a primary that loses its UTC source can become a secondary a secondary that loses its primary can use another primary Modes of synchronization: Multicast A server within a high speed LAN multicasts time to others which set clocks assuming some delay (not very accurate) Procedure call A server accepts requests from other computers (like Cristiain’s algorithm). Higher accuracy. Useful if no hardware multicast. Symmetric Pairs of servers exchange messages containing time information Used where very high accuracies are needed (e.g. for higher levels) ???? Accuracy of NTP For each pair of messages between two servers, NTP estimates an offset o, between the two clocks and a delay di (total time for the two messages, which take t and t’) Ti-2 = Ti-3 + t + o and Ti = Ti-1 + t’ - o This gives us (by adding the equations) : di = t + t’ = Ti-2 - Ti-3 + Ti - Ti-1 Also (by subtracting the equations) o = oi + (t’ - t )/2 where oi = (Ti-2 - Ti-3 + Ti-1 - Ti)/2 Using the fact that t, t’ɬ it can be shown that oi - di /2 ≤ o ≤ oi + di /2 . Thus oi is an estimate of the offset and di is a measure of the accuracy NTP servers filter pairs <oi, di>, estimating reliability from variation, allowing them to select peers Accuracy of 10s of millisecs over Internet paths (1 on LANs)