CS API refers to undefined terms stream ordering and topological ordering

[DMRobertson]

Link to problem area:

• stream: https://spec.matrix.org/v1.4/client-server-api/#get_matrixclientv3sync definition of m.heroes under "Room Summary"
• threads: e.g. https://spec.matrix.org/v1.4/client-server-api/#get_matrixclientv1roomsroomidrelationseventid

Issue

From https://spec.matrix.org/v1.4/client-server-api/#get_matrixclientv3sync definition of m.heroes under "Room Summary" defining m.heroes:

The users which can be used to generate a room name if the room does not have one. Required if the room’s m.room.name or m.room.canonical_alias state events are unset or empty.

This should be the first 5 members of the room, ordered by stream ordering, which are joined or invited. The list must never include the client’s own user ID. When no joined or invited members are available, this should consist of the banned and left users. More than 5 members may be provided, however less than 5 should only be provided when there are less than 5 members to represent.

(emphasis mine.)

It is not clear what "stream ordering" means. (AFAIK is a concept that Synapse defines for its own use?)

https://spec.matrix.org/v1.4/appendices/ makes no mention either.

Similarly much of the relations work speaks of "topological ordering" that isn't defined either.

Related:

• Clarify if notifications are cleared by stream ordering or topological ordering #1167
• Reduce confusion between topological and stream position tokens (SPEC-268) #125
• Consider changing /messages to use stream ordering for events #852

[DMRobertson]

This should be the first 5 members of the room, ordered by stream ordering, which are joined or invited.

Judging from https://github.com/matrix-org/synapse/blob/66a785733458d0b5801097caff53624e202a91b4/synapse/handlers/sync.py#L831, it seems Synapse doesn't do the ordering properly.

[MadLittleMods]

After crafting #1917, I think I found how we can derive the following definitions from this existing piece of spec:

Events are ordered in this API according to the arrival time of the event on the homeserver. This can conflict with other APIs which order events based on their partial ordering in the event graph. This can result in duplicate events being received (once per distinct API called). Clients SHOULD de-duplicate events based on the event ID when this happens.

Therefore:

• stream_ordering: Ordered by the "arrival time of the event on the homeserver"
• topological_ordering: Ordered by the "partial ordering in the event graph". This corresponds to the baked in depth field but ideally homeservers would use some graph linearization strategy. Perhaps some online topological ordering (Katriel–Bodlaender algorithm) where depth/topological_ordering is dynamically updated whenever new events are inserted into the DAG.