Gérard Berry Collège de France Chaire Algorithmes, machines ...podcastfichiers.college-de-france.fr/berry-20140312.pdf2014/03/12 · –plus un pour les années bissextiles : Sans-culottides

Synchronisons nos montres

Gérard Berry

Collège de France

Chaire Algorithmes, machines et langages

http://www.college-de-france.fr/site/gerard-berry

[email protected]

Cours 5, 12 mars 2014









mailto:[email protected]





12/03/2014 2G. Berry, Collège de France

Le facteur temps,

c’est l’âpre fumet,

et c’est le parfum

Anagrammes,

Etienne Klein

It is possible to own too much :

a man with one watch knows what time it is,

a man with two watches is never quite sure

Lee Segall

• Le jour et la nuit

• Le cycle lunaire, le cycle annuel

• Rythme des saisons– rythme de la lumière

– rythme décalé de la température


Les rythmes naturels – bien compliqués !

La nature a bien suivi le cours 2013

sur le temps multiforme !

• Rythmes agricoles : labourage, semailles, récolte,...

• Migration des oiseaux et des poissons

• Floraison simultanée des bambous du monde entier

• Passage d’une étoile au méridien : 23h56mn– la terre a avancé de ~1o sur son orbite !


La durée du jour

• Passage du soleil au méridien : 24h en moyenne=> équation du temps (le soleil au sud ne donne pas le midi)


Mesurer les duréesMesurer les durées

sablier (jusqu’à 1 an !)

corde à nœuds

clepsydre


Horloges à eau (clepsydres)

Ksêtíbios, 3e siècle avant Jésus-Christ



Yantra Mandir, Jaipur, ~1730

Photo G. Berry

12/03/2014 9G. Berry, Collège de FrancePhoto G. Berry


Les heures canoniales et les cloches

Matines entre minuit

et le lever du soleil

4 tintements

Prime lever du soleil 3 tintements

Tierce milieu de matinée 2 tintements

Sexte midi 1 tintement

None milieu d’après-midi 2 tintements

Vêpres coucher du soleil 3 tintements

Complies tombée de la nuit 4 tintements

Mais qu’est-ce donc qu’un tintamarre?

Irrégulières, annoncées par les cloches


Les clepsydres gèlent, inventons l’échappement !

Prieuré de Dunstable, 1283

Huygens ajoute le pendule et la cycloïde

pour régulariser le pendule (1694)

source B. Meigun



La pendule de référence (Pavillon de Breteuil)

24

12

0618

potron-minet

entre chien

et loup

pm

ecl pdhpoint d’heure

ps 7h et des

poussières

midi pétante

maqhmidi à

quatorze heures

alpavec les poules

07

pt



Le calendrier

Seuls deux calendriers actuels comptent vraiment– le calendrier vulgaire (ou Grégorien), encore utilisé

– le calendrier pataphysique : tous les 13 sont des vendredis

Mon préféré : le calendrier révolutionnaire (Laplace)– 1 mois = 3 semaines de 10 jours

– 1 jour = 10 heures

– 1 heure = 100 minutes

– 1 minute = 100 secondes

– 5 jours supplémentaires tous les ans :

Vertus, Génie, Travail, Opinion, Récompenses

– plus un pour les années bissextiles : Sans-culottides


Des Scilly à John Harrisson

Le grand prix de l’amirauté (20 000 livres)

2 novembre 1707 (Grégorien),

mauvaise estimation de longitude

(1s d’erreur = 400m)

1772 : Chronomètre H5

1/3 s par jour !


Le tourbillon Bréguet

7 messidor an IX (26 juin 1801).

Source : leblogdesmontres.fr


―On August 12, 1853, two trains on the Providence & Worcester Railroad

were headed toward each other on a single track. The conductor of one train

thought there was time to reach the switch to a track to Boston before the

approaching train was scheduled to pass through. But the conductor's watch

was slow. As his speeding train rounded a blind curve, it collided head-on

with the other train—fourteen people were killed. The public was outraged. All

over New England, railroads ordered more reliable watches for their

conductors and issued stricter rules for running on time.‖


Horloges atomiques


Horloge parlante

1991: Marie-Sylvie Behr

donne sa voix à l’horloge atomique

1933 : l’horloge parlante

d’Ernest Esclangon

mais qui est donc cet homme ?http://www.dailymotion.com/video/xxeyyr_le-visage-de-l-horloge-parlante_news

http://www.dailymotion.com/video/xxeyyr_le-visage-de-l-horloge-parlante_news













Horloge atomique de poche !

• < 120mW power consumption

• < 17cm3 volume

• 35g weight

• ± 5 1011 accuracy at

shipment

• σy < 5 10 12 at τ = 1 hour

short-term stability (Allan

Deviation)

• < 3 10 12 / month aging rate

source Symmetricom.com


La seconde, unité globale

La seconde est la durée de 9 192 631 770 périodes de la

radiation correspondant à la transition entre les niveaux

hyperfins F=3 et F=4 de l’état fondamental 6S½ de l’atome de

césium 133, à la température de référence du zéro absolu.

• Oeuf coque, niveau de la mer, 0 absolu = 3mn 45s

compter jusqu’à 2 068 342 148 250 ~ 2 téra-laps

• Oeuf coque, Paris, 35m, 100 Celsius = 4mn 03s

compter jusqu’à 2 233 809 520 110 laps

Laps de temps : 1 s = 9 192 631 770 laps

1 s ~ 9.2 giga-laps


La fin de notre Kilogramme étalon?

90% platine, 10% Iridium

h = d = 39,17mm

Australie : sphère de silicium parfaite

diamètre précis à 70 nm

défauts de rugosité < 0,3 nm

Pavillon de Breteuil

Sèvres

source : CSIRO Industrial Physics


Le NIST américain : masse = temps

Kg défini par la seconde, la

la vitesse de la lumière c

et la constante de Planck h !

Balance

du Watt Photo par

Richard Steiner


Physiciens ou ‘Pataphysiciens ?

La seconde est la durée de 9 192 631 770 périodes de la radiation

correspondant à la transition entre les niveaux hyperfins F=3 et F=4

de l’état fondamental 6S½ de l’atome de césium 133,

à la température de référence du zéro absolu.

1 mètre = la distance parcourue par la lumière dans le

vide en 1 / 299 792 458 seconde

Le kilogramme est la masse qui subirait une accélération de

précisément 2×10-7 m/s2 lorsqu’elle est soumise à la force par

mètre entre deux conducteurs parallèles, rectilignes, de

longueur infinie, de section circulaire négligeable, placés à

une distance d’un mètre l’un de l’autre dans le vide, et à

travers desquels passe un courant électrique constant

d’exactement 6,24150962915265×1018 charges élémentaires

par seconde.

http://fr.wikipedia.org/wiki/Acc%C3%A9l%C3%A9ration

http://fr.wikipedia.org/wiki/Force_(physique)

http://fr.wikipedia.org/wiki/Vide

http://fr.wikipedia.org/wiki/Courant_%C3%A9lectrique

http://fr.wikipedia.org/wiki/Charge_%C3%A9l%C3%A9mentaire

• GMT : heure déterminée par le passage du soleil moyen au

méridien de Greenwich (équation du temps) – 0h00 à midi !– après bagarre avec les français, bien sûr !

– 1847-48 : adopté par les compagnies ferroviaires

– mais une loi de 1858 impose le temps local !

– 1880: loi imposant l’heure GMT en Angleterre


Quelle heure : GMT, TU, UTC, ou TAI ?

• UTC mix(TUC, CUT) !– temps civil mondial, TAI + secondes (ralentissement de la terre, etc.)

• TAI (Temps Atomique International) : moyenne de plus de

200 horloges au Césium– correction de gravité

– base d’encore autre temps

• TCB (planètes), TCG (temps géocentrique), TT (temps

terrestre), etc. – vive la relativité générale !

• 31/12/2008 : tous les lecteurs MP3 Zune (Microsoft)

vident leur piles à minuit en bouclant sur deux tests


Bugs de temps

voir Parler du temps, mais de manière formelle,

cours 1 du 04/02/2013, http://www.college-de-france.fr/site/gerard-berry/course-2013-04-02-10h00.htm

• 28/02/2010 : les PS3 FAT de Sony repassent au

01/01/2000 (ou autres), perdant le réseau et les jeux

• 10/2010 : les iPhones US passent à l’heure d’hiver,

• 10/2010 : mais pas leurs réveils !

• 25/02/1991: 28 morts et 98 blessés suite à la chute d’un

SCUD sur une caserne américaine, due au système

d’horloge logicielle d’une station Patriot

http://www.college-de-france.fr/site/gerard-berry/course-2013-04-02-10h00.htm















• Deux versions, 2002 puis 2008

• Base : GPS, horloges atomiques– travaille en TAI, communique l’écart avec UTC

• Réseaux multicast (Ethernet ou autres)

• Objectifs– Synchronisation < 1 s

– charge faible sur les machines et réseaux

– simple à administrer

• Contraintes– temps de propagation dans le réseau symétriques


PTP = Precise Time Protocol, IEEE 1588

White paper : Precision Clock Synchronization,

The Standard IEEE 1588, Hirschmann


Réseau hiérarchique PTP

Source Hirschmann


Types de noeuds PTP

Boundary Clock switch temporellement précis

esclave en réception, maître en émission

compensation des délais internes

Source Hirschmann


Protocoles de synchronisation PTPmaître esclave

sync 998 (~t1)

1007fup 1000

t1 1000 1005

1015

t’1

délai de transmission non connu !sync 1010 (~t1)

1013fup 1013

t2 1013

1015 1002 101510131013

t’2

1008 101510071000

sync 1027 (~t4)

fup 1030

t4 1030

1002

1030t’4

dresp 1025

dreq 1021

t3 1025

délai (t’2t2t3t’3) / 2 2

1021t’3

10331035 1035 t’5 délai1033t’5

calcul du délai

1008

1015

1011


Architecture d’un nœud PTP

Les timestamps doivent être construits au plus près du HW

La communication HW / SW doit être soignée

(drivers réseau / horloges)Source Hirschmann


La couche logicielle

recherche du meilleur Master

par observation des horloges

Source Hirschmann


Un exemple extrême, le LHC

Le projet WhiteRabbit du CERN synchronise les horloges à 10 km de

distance à ~80 picosecondes près par GPS, IEEE 1588 PTP et Ethernet

synchrone

Source CERN

• Dimension : gigantesque, l’ensemble d’Internet, au moins !

• Rôle : essentiel, pour le routage comme pour les utilisateurs!


NTP : Network Time Protocol

• Contraintes :

– travail en conditions difficiles (mauvais réseau, pannes, etc.)

– hiérarchie à plusieurs niveaux

– les sous-réseaux doivent pouvoir survivre, même déconnectés longtemps

– le protocole doit agir en continu et synchroniser les horloges standards

– des ordinateurs, sur Internet standard, et en utilisant peu de ressources

– il doit être sécurisé face aux attaques malicieuses

– les événements importants doivent être stockés pour analyse éventuelle

– le logiciel soit être simple, standard, et facile à installer


Format du temps dans NTP

de la naissance de l’univers

à la mort du soleil

232 ps

500 as

(1 as = 1018 s)

era = 136 ans, base 01/01/1900 00:00

• Chaque serveur a un compteur de temps qui

avance l’horloge système tous les 10ms

• La lecture du temps doit toujours être croissante

• Correction du temps toutes les secondes– agent majeur de fluctuation, la température (1PPM / C)

– doit respecter la monotonie correction douce!

– correction faite dans le noyau précision ~1s


Gestion du temps sur un hôte NTP

• Associations permanentes ou éphémères,

symétriques ou asymétriques (client serveur)


Fonctionnement global de NTP

• Détection automatique des serveurs,

reconfiguration automatique en cas de panne

(algorithmes byzantins)

• Authentification cryptographique des accès,

détection d’intrusions

• Algorithmes statistiques d’évaluation du temps et

de la qualité des serveurs


NTP : protocole riche et complexe, devenu universel

Un énorme travail collectif né de David Mills,

qui touche à beaucoup de domaines :

algorithmes distribués, statistiques, réseau,

noyau OS, cryptographie, etc.

Synchronisations ms s normales

Synchronisations ~50ns devenues possibles


Localiser les défauts d’une ligne électrique

Source

Ptolemy II

E. A. Lee et al.

UC Berkeley

Cf.

prochain cours !


Attention à la symétrie des délais réseau !


• TTP : système de réseau et protocoles destiné

au temps-réel critique–Hermann Kopetz, Vienna University ot Technology

–Compagnies TTTech, HW Austria Microsystems, Altera,

ON semiconductors.

–développé pour le temps-réel critique et la tolérance

aux fautes, en particulier en remplacement du bus CAN


TTP : Time-Triggered Protocol

• 1 ou 2 canaux redondants 25 Mbits / s, –TDMA (Time Division Multiplexing Access), allocation

statique de slots et rounds, déterminisme, synchronisation

précise des horloges

–détection de fautes fondées sur le temps : non-réception

ou sur-réception de messages, détection de pannes, etc.

• Ferroviaire– interlocking, contrôle local et distant, conduite

automatique, diagnostic, tout au niveau SIL4 (Thales)


TTP : utilisations

• Avionique– FADEC (contrôle moteur) : Aermacchi, General Electric

– Pressurisation (Airbus A380), contrôle électrique et

clim (Boeing 787), par Hamilton-Sunstrand

• Automobile– voitures automatiques (Red Team, DARPA Challenge)

• Consortium automobile (jusqu’en 2009), standard ISO

• Protocole TDMA déterministe similaire, synchronisation

d’horloges + messages asynchrones (pour récupérer CAN)

• Utilisé dans des voitures allemandes (Audi, BMW, Mercedes,

Rolls-Royce)


FlexRay

Autres choix possibles

Divers Ethernet déterministes

LTTA (séminaire A. Benveniste, 05/03/2014)

Et pour comprendre les horreurs qu’on peut hélas trouver

en automobile, voir

http://www.safetyresearch.net/2013/11/07/toyota-unintended-acceleration-and-the-big-bowl-of-spaghetti-code/




















• Base de données répliquée mondialement, avec plusieurs

répliques à chaque endroit (performance et redondance).

Millions de machines, milliards d’enregistrements !


Spanner, BD distribuée de Google

• Système TrueTime de timestamps en forme d’intervalles

[earliest, latest], avec garantie (selon la synchro) que le

timestamp d’un événement e de date absolue t vérifie

earliest t latest

• Synchronisation mondiale fine des horloges (~6ms)

• Transactions distribuées atomiques, protocole two-phase

commit


Garanties temporelles de Spanner

• Pour deux transactions d’écriture T1 et T2 enregistrées à t1

et t2 et committées à c1 et c2, garantie de monotonicité

des timestamps : c1 t2 latest(c1) earliest(c2)

• Possibilité de lecture d’un snapshot pour un timestamp

donné, résultat indépendant de la réplique

• Possibilité de lecture ―best effort‖ si besoin de timestamp

réduit

• Maintien permanent du dernier timestamp d’écriture locale

sur chaque réplique

La synchronisation temporelle précise devient essentielle

pour un nombre toujours plus grand d’applications, et

est réalisable à complexité et coût raisonnable


Conclusion

Pourtant, le sujet est encore peu connu et peu

développé dans le système académique,

d’où ce cours !


Références sur le temps en général

Le temps (qui passe ?)

Etienne Klein, Bayard (2013)

Le facteur temps ne sonne jamais deux fois

Etienne Klein, Flammarion (2009)

The Book of Nothing

John D. Barrow, Vintage Books (2001)

La mesure du temps

Bernard Meiguen, Editions Apogée (2009)

La mesure du temps au XXIe siècle

Christophe Salomon, séminaire du cours de Serge Harochehttp://www.college-de-france.fr/site/serge-haroche/seminar-2013-03-12-11h00.htm

http://www.college-de-france.fr/site/serge-haroche/seminar-2013-03-12-11h00.htm
















Références plus techniquesPrecision Clock Synchronization: the Standard IEEE 1588

White paper, Hirschmann

Computer Network Time Synchronization :

the Network Time Protocol on Earth and in Space

David L. Mills, CRC Press (2011)

Spanner: Google's Globally-Distributed Database

Proc. OSDI’12, Hollywood, 2012James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, JJ Furman,

Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh,

Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura,

David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak,

Christopher Taylor, Ruth Wang, and Dale Woodford

System Design, Modeling, and Simulation using Ptolemy II

Claudius Ptolemaeus, Editor (2014)

téléchargable avec toutes les démos animées:

http://ptolemy.eecs.berkeley.edu/books/Systems/

http://ptolemy.eecs.berkeley.edu/books/Systems/

Documents

Gérard Berry Collège de France Chaire Algorithmes, machines ...podcastfichiers.college-de-france.fr/berry-20140312.pdf2014/03/12 · –plus un pour les années bissextiles : Sans-culottides