summary refs log tree commit diff
path: root/docs/state_resolution.rst
diff options
context:
space:
mode:
authorMatthew Hodgson <matthew@matrix.org>2014-10-09 20:38:00 +0200
committerMatthew Hodgson <matthew@matrix.org>2014-10-09 20:38:00 +0200
commite1170d4edbc3563730028047c23a4169e6420c59 (patch)
tree4664a10735780cca5ef41f08f6abad32f106cfb3 /docs/state_resolution.rst
parentAdd spec-additions.rst with info on recaptcha and common event fields. (diff)
downloadsynapse-e1170d4edbc3563730028047c23a4169e6420c59.tar.xz
move matrix-generic content to new matrix-doc git project
Diffstat (limited to 'docs/state_resolution.rst')
-rw-r--r--docs/state_resolution.rst51
1 files changed, 0 insertions, 51 deletions
diff --git a/docs/state_resolution.rst b/docs/state_resolution.rst
deleted file mode 100644
index fec290dd79..0000000000
--- a/docs/state_resolution.rst
+++ /dev/null
@@ -1,51 +0,0 @@
-State Resolution
-================
-This section describes why we need state resolution and how it works.
-
-
-Motivation
------------
-We want to be able to associate some shared state with rooms, e.g. a room name
-or members list. This is done by having a current state dictionary that maps
-from the pair event type and state key to an event.
-
-However, since the servers involved in the room are distributed we need to be
-able to handle the case when two (or more) servers try and update the state at
-the same time. This is done via the state resolution algorithm.
-
-
-State Tree
-------------
-State events contain a reference to the state it is trying to replace. These
-relations form a tree where the current state is one of the leaf nodes.
-
-Note that state events are events, and so are part of the PDU graph. Thus we
-can be sure that (modulo the internet being particularly broken) we will see
-all state events eventually.
-
-
-Algorithm requirements
-----------------------
-We want the algorithm to have the following properties:
-- Since we aren't guaranteed what order we receive state events in, except that
-  we see parents before children, the state resolution algorithm must not depend
-  on the order and must always come to the same result. 
-- If we receive a state event whose parent is the current state, then the
-  algorithm will select it.
-- The algorithm does not depend on internal state, ensuring all servers should
-  come to the same decision.
-
-These three properties mean it is enough to keep track of the current state and
-compare it with any new proposed state, rather than having to keep track of all
-the leafs of the tree and recomputing across the entire state tree.
-
-
-Current Implementation
-----------------------
-The current implementation works as follows: Upon receipt of a newly proposed
-state change we first find the common ancestor. Then we take the maximum
-across each branch of the users' power levels, if one is higher then it is
-selected as the current state. Otherwise, we check if one chain is longer than
-the other, if so we choose that one. If that also fails, then we concatenate
-all the pdu ids and take a SHA1 hash and compare them to select a common
-ancestor.