HTTPS SSH

Thought Leadering Time

Thought Leadering Time is a protocol for time synchronization in mesh networks.

  • Time is distributed from a single root out to all transitively connected nodes.
  • Messages can be sent through the protocol to schedule future actions.
  • The protocol adapts to changing node connectivity.

Getting Started

To install all dependencies, run:

$ tools/setup

To build the project, run:

$ tools/build

The resulting image will be in thought-leadering-time.hex (it's a symlink pointing to the right file in the build directory). You can flash it to your microbits by copying it into the filesystem. There's also a script for flashing it onto all connected micro:bits:

$ tools/flash thought-leadering-time.hex

To play music on the micro:bits:

  1. Flash the micro:bits with the image.
  2. Select one to be the root by pressing the A and B buttons simultaneously. (the bottom row of LEDs should go blank, indicating level 0)
  3. On the laptop connected to the root, run:

    $ tools/play-music -p /dev/ttyACM* -s 0 5062 843

By default, play-music uses a trigger delay of 2 seconds: you can adjust that with the --trigger-delay-ms (-t) flag.

Music

The music data is in src/song-data.h. You can regenerate it to include all MIDI files in the music directory by running:

$ tools/generate-music
music/ode-to-joy.midi: tools/play-music -p /dev/ttyACM* -s 0 5062 843

If you then rebuild and flash the image onto your micro:bits, you can use the commands printed out to play each MIDI file.

Protocol Overview

The protocol continually runs two processes: determining network latency, and adjusting nodes’ clocks.

Network latency is determined by each node, by periodically broadcasting a PING_REQUEST message with a unique id (and recording the time at which it was sent). Adjacent nodes in the network will respond with a PING_RESPONSE message (which also lets nodes know how many hops it is from the root).

Along with the PING_REQUEST message, nodes include a list of "votes" for nodes which they have recently received messages from and are closer to the root than they are.

Periodically, every node calculates a score for every node they've seen votes for, and if they are the most voted for node, will broadcast a SYNC message, which advertises their current time to the network. Nodes further from the root adjust their clocks using this and the learnt network latency to converge towards the root's clock.

Nodes have a level, which is a number approximating the number of hops from the root. When a node receives a SYNC message from a level which causes it to adjust its own time by less than $EPSILON, it reduces its own level to one more than the level in the SYNC message. If it doesn't manage to do this in $LEVEL_INCREASE_PERIOD, it doubles its level.

SYNC messages may contain triggers for events to happen in the future. Nodes must propagate the union of all received triggers (modulo memory limits). Triggers past the node's timestamp should be expired.

Protocol Messages

Unless specified, all multi-byte data is encoded in big-endian format.

PING_REQUEST

This packet is sent to request all adjacent nodes to reply, to determine network latency.

Format: <01> <uint8: req_node> <uint8: req_level> <uint16: ping_id> {<uint8: vote>} (1 + 1 + 1 + 2 + (1) * n = 5 + n bytes)

  • req_node: the id of the node requesting the ping
  • req_level: the node's level
  • ping_id: a unique id for this ping request
  • vote: a list of node ids this node would like to sync from

The ping_id is not sensitive and may be generated in any manner, provided the probability of an id collision is sufficiently low. Using sequential numbers for the id is allowed, but not recommended.

The list of node ids in vote should be randomly ordered, to ensure a fair distribution of sync messages across the optimal nodes.

PING_RESPONSE

This packet is sent in response to a PING_REQUEST.

Format: <02> <uint8: req_node> <uint8: resp_node> <uint8: resp_level> <uint16: ping_id> <uint32: req_end_timestamp> (1 + 1 + 1 + 1 + 2 + 4 = 10 bytes)

  • req_node: copied from PING_REQUEST.req_node
  • resp_node: the id of the node responding to the ping
  • resp_level: the level of the node responding to the ping
  • ping_id: copied from PING_REQUEST.ping_id
  • req_end_timestamp: the time at which the PING_REQUEST was received, according to the responding node's clock.

SYNC

This packet is sent periodically from nodes to advertise their current time, and to advertise future triggers.

Format: <03> <uint8: node> <uint8: level> <uint32: timestamp> {<uint8: trigger_id> <uint16: trigger_delta>} (1 + 1 + 1 + 4 + (2 + 1) * n = 7 + 3n bytes)

  • node: the node advertising the current time
  • level: the node's level
  • timestamp: the node's current timestamp
  • trigger_id: the ids of a trigger to run
  • trigger_delta: delta to timestamp for when the trigger should run

Appendix: Constants

  • $EPSILON: 10ms
  • $LEVEL_INCREASE_PERIOD: 1000ms
  • $SYNC_PERIOD: 250ms
  • $PING_PERIOD: 189ms