# historical snapshot point consensus in P2P networks

Algorithm for nodes in a p2p network to agree on a snapshot point - a point in which all the nodes had the same view of the network state. A network state is defined as both the 1) set of nodes which are part of the network and 2) their respective states. As a requirement, the snapshot point must be decided locally, based on the current and past network state in all nodes in the network.

This is a historical consensus algorithm for a replicated network of nodes, in which nodes have to all agree that at some point in time, all the replicas which are currently part of the network had the same local state.


## Network map and consensus points

The local nodes decide whether the consensus was reached based on their `netowrk map`, which is the local representation of the network state. A network map is represented as:

```
network_map = {
  N1: {
    N1: B1_state,
    N2: N2_state,
  },
  N2: {
    N1: N1_state,
    N2: N2_state,
  }
}
```

Each node maintains a local `network_map`. This network map represents the the view of the network (nodes that currently are part of the network and their state) and also what is the state of the network that those nodes see.

A state is a set of all operations/transactions that lead to the current state. For example, If R1 have applied operation A, B and C, then its state is `R1_state = [A, B, C]`. The state in the `network_map` is cumulative and idempotent.

If all nodes eventually converge to the same state (i.e. eventually have the same set of operations applied locally), it is possible to deduce locally points in the past in which all nodes in the network had the same state. In these points - `consensus points` - we can ensure that all nodes had the same set of operations applied.


## Algorithm

Everytime a new node (Rn) joins the network, it gets a copy of the `network_map` of the first node (Rj) it communicates to. The node Rj also adds Rn to its network map.

Everytime a node changes its state, it updates its `network_map` accordingly and gossips the new state to the network.


**1.Only one node N1 and one operation A**

N1_network_map (nm): {N1: [A]}


**2. New node joins the network and receives state from N1**

N1_nm: `{N1: [A], N2: [A]}`

N2_nm: `{N1: [A], N2: [A]}`

**3. N2 changes its state locally and applies operation B**

N1_nm: `{N1: [A], N2: [A]}`

N2_nm: `{N1: [A], N2: [A, B]}`

**4. N2 gossips netmap to N1**

N1_nm: `{N1: [A, B], N2: [A, B]}`

N2_nm: `{N1: [A], N2: [A, B]}`

At this point in time, N1 understands that [A, B] is a valid `consensus point`. Because all replicas have applied those operations and have the same state. N2 doesn't know about it yet.

**5. N1 changes its state locally and applies operation C**

N1_nm: `{N1: [A, B, C], N2: [A, B]}`

N2_nm: `{N1: [A], N2: [A, B]}`

**6. N1 gossips netmap to N2**

N1_nm: `{N1: [A, B, C], N2: [A, B]}`

N2_nm: `{N1: [A, B, C], N2: [A, B]}`

At this point, N2 also understands that [A, B] is a valid `consensus point`.

Notice that node N1 and N2 recognized that a `consensus point` was reached at different times. But since we assume that nodes will eventually communicate with each other their local `network map` over time, every node in the network will agree in the same `consensus points`.

**7. N3 joins the network and receives state from N2**

N1_nm: `{N1: [A, B, C], N2: [A, B]}`

N2_nm: `{N1: [A, B, C], N2: [A, B]}`

N3_nm: `{N1: [A, B, C], N2: [A, B], N3: [A, B]}`

Notice that N3 `network map` is a copy of the N2 `network map` with an entry to itself.

**8. N3 applies locally operations D and E and N1 applies locally operation F**

N1_nm: `{N1: [A, B, C, F], N2: [A, B]}`

N2_nm: `{N1: [A, B, C], N2: [A, B]}`

N3_nm: `{N1: [A, B, C], N2: [A, B], N3: [A, B, D, E]}`

Notice that N1 doesn't know about N3 yet. All nodes agree that the snapshot point is still [A, B] (set of operations that all nodes visible in the network have applied locally)

**9. N3 gossips netmap to N1**

N1_nm: `{N1: [A, B, C, F, D, E], N2: [A, B], N3: [A, B, D, E]}`

N2_nm: `{N1: [A, B, C], N2: [A, B]}`

N3_nm: `{N1: [A, B, C], N2: [A, B], N3: [A, B, D, E]}`

**10. N2 applies local change G**

N1_nm: `{N1: [A, B, C, F, D, E], N2: [A, B], N3: [A, B, D, E]}`

N2_nm: `{N1: [A, B, C], N2: [A, B, G]}`

N3_nm: `{N1: [A, B, C], N2: [A, B], N3: [A, B, D, E]}`

**11. N3 gossips netmap to N2**

N1_nm: `{N1: [A, B, C, F, D, E], N2: [A, B], N3: [A, B, D, E]}`

N2_nm: `{N1: [A, B, C, F, D, E], N2: [A, B, G, C, F, D, E], N3: [A, B, D, E]}`

N3_nm: `{N1: [A, B, C], N2: [A, B], N3: [A, B, D, E]}`

**12. N2 gossips netmap to N3**


N1_nm: `{N1: [A, B, C, F, D, E], N2: [A, B], N3: [A, B, D, E]}`

N2_nm: `{N1: [A, B, C, F, D, E], N2: [A, B, G, C, F, D, E], N3: [A, B, D, E]}`

N3_nm: `{N1: [A, B, C, F, D, E], N2: [A, B, C, D, E, F, G], N3: [A, B, C, D, E, F, G]}`

N3 now can consider [A, B, C, D, E, F, G] as snapshot point.



## Applications: CRDT snapshotting and garbage collection