munication connectivity varies due to environmental and electromagnetic factors, with the additional constraint that no human being will shepherd the device to a better setting, as with a cell phone or a laptop. The degree of the network at a node, i.e., the number of nodes in its communication neighborhood, is determined not by the desired network organization but by the physical device placement, which is often dictated by application requirements and physical constraints. There may be thousands of nodes in close proximity, or just a few. A single transmission may be received by many devices, so any retransmission, response, or even a simple acknowledgment, may cause huge contention, interference, and loss. Redundancy is essential for reliability, but it also can be a primary cause of loss.

This last point is one of the key observations that have emerged from a decade of development of networking abstractions for wireless sensor networks: the variety of network topologies and densities across which sensor network protocols must operate calls for a polite, density-aware, local retransmission scheme. This paper describes the Trickle algorithm, which uses such a communication pattern to provide an eventual consistency mechanism to protocols and services. In the past ten years, a key insight that has emerged from the wireless sensor network community is that many protocol problems can be reduced to maintaining eventual consistency. Correspondingly, Trickle has emerged as the core networking primitive at the heart of practical, efficient, and robust implementations of many sensor network protocols and systems. Before diving into the details of the Trickle, however, we review how core sensor networking protocols work and differ from conventional networking protocols, with the goal of exploring how a Trickle-like primitive satisfies some of their needs.

2. net WoRKinG PRotocoLS

Networking issues are at the core of embedded sensor network design because radio communication—listening, receiving, and transmitting—dominates the active energy budget and defines system lifetime. The standard energy cost metric for multihop protocols, in either link layer meshing or network layer routing, is communication cost, defined as the number of individual radio transmissions and receptions. One protocol is more efficient than another if it can provide equivalent performance (e.g., throughput, latency, delivery ratio) at a lower communication cost. Protocols focus on minimizing transmissions and making sure transmitted packets arrive successfully.

Almost all sensor network systems rely on two multihop protocols for their basic operation: a collection protocol for pulling data out of a network and a dissemination protocol for pushing data into a network through one or more distinguished nodes or egress routers. Many higher level protocols build on dissemination and collection. For example, reprogramming services such as Deluge⁹ use dissemination to deliver commands to change program images. Management layers²² and remote source-level debuggers²⁵ also use dissemination. Reliable transport protocols, such as RCRT, ¹⁸ and rate control protocols such as

IFRC, ¹⁹ operate on collection trees. Point-to-point routing schemes, such as S4, ¹⁶ establish overlays over multiple parallel collection topologies.

While collection and dissemination have the opposite communication patterns (all-to-one vs. one-to-all) and differ in reliability (unreliable vs. reliable), both maintain eventually consistent shared state between nodes. The rest of this section provides a high-level overview of these two protocol classes. It provides details on the challenging problems they introduce, and how some of them can be solved through eventual consistency.

2. 1. Pushing data in: dissemination

One problem sensor network administrators face is dynamically changing how a network collects data by changing the sampled sensors, the sampling rate, or even the code running on the nodes by disseminating the change to every node in a network. We begin with a discussion of dissemination protocols because they were the original impetus for Trickle and are its simplest application.

Early systems used packet floods to disseminate changes. Flooding protocols rebroadcast packets they receive. Flooding is very simple—often just a line or two of code—but has many problems. First, floods are unreliable. Inevitably, some nodes do not receive the packet, so users typically repeatedly flood until every node receives it. Second, in high density networks, many nodes end up rebroadcasting packets at the same time. These messages collide and cause a form of network collapse called a “broadcast storm.” ¹⁷

Second-generation dissemination and network programming systems like Xnp³ and TinyDB¹⁵ use an adaptive flood combined with a protocol to request missing messages. Adaptive flooding uses an estimate of the node density to limit the flooding rate. The missing message protocol allows nodes to request the (hopefully few) missing messages from their neighbors. Unfortunately, getting such protocols to work well can be tricky, especially across a range of network densities and object sizes.

Another way to look at dissemination protocols is that they ensure that every node has an eventually consistent version of some shared state, such as the value of a configuration parameter or command. Data consistency is when all nodes have the same version of that state, and nodes resolve inconsistencies by updating neighbors to the newer version. Inductively, these definitions cause the network to converge on the most recent version. To disseminate a command, a system installs it on one node as a newer version and initiates the consistency protocol.

Casting dissemination as a data consistency problem means it does not provide full reliability. Eventual consistency only promises to deliver the most recent version to connected nodes. Disconnected nodes can and often do miss updates. In practice, however, this limitation is rarely problematic. An administrator who changes the data reporting rate three times then adds some new nodes and expects them to receive the most recent reporting rate, not all three. Similarly, when sending commands, users do not expect a new node to receive the entire history of all commands injected into a net-