分布式系统原理与范例_6_Synchronization.pdf

Distributed Systems Synchronization Outline Clock Synchronization  Logical Clocks  Mutual Exclusion  Global Positioning of nodes  Election Algorithms Clock Synchronization  Physical Clocks  Global Positioning System Clock Synchronization Algorithms Why is it important ?  Need to measure accurately  E.g., auditing in e-commerce  Algorithms depending on  E.g., consistency,  make  Correctness of distributed systems frequently hinges upon the satisfaction of global system invariants.  E.g., Absence of deadlocks  Write access to a distributed database never granted to more than one process  the sum of all account debits and ATM payments in an electronic cash system is zero  Objects are only subject to garbage collection when no further reference to them exists E.g., UNIX make program  When each machine has its own clock, an event that occurred after another event may nevertheless be assigned an earlier time. Physical Clocks Time Synchronization Algorithms • Cristian’s method • The Berkeley Algorithm • The Network Time Protocol 时间简史  人类生活有紧密联系的太阳的运动是比较均匀  地球自传是一天，公转是一年  天文计量，自从17世纪机械钟表发明. GMT (Greenwich Mean Time)  太阳到达天空中它出现的最高点时称为中天  两次连续的太阳中天之间的时间称为一个太阳日  每天有24小时，每小时有3600秒， 1/86400个太阳日是太阳秒  物理计量，20世纪40年代  1秒是铯133原子作9,192,631,770次跃迁所用的时间  BIH (Bureau International de l’Heure)将这些值平均起来 产生国际原子时间，简称为TAI (International Atomic Time)  TAI和太阳秒计时之间的差增加到800毫秒时使用一次闰秒，修 正后的时间系统称作统一协调时间，简称UTC (Universal Coordinated Time) Physical Clocks  A high-frequency oscillator, counter, and holding regi