Here are three Matrix homeservers, each with one client connected.

The clients are all participating in the same Matrix room, which is synchronised across the three participating servers.

Alice sends a JSON message to a room on her homeserver.

curl -XPOST
 -d '{"msgtype":"m.text", "body":"hello"}'
 "https://matrix.alice.com/_matrix/client
 /v2/rooms/ROOM_ID/send/m.room.message
 ?access_token=ACCESS_TOKEN"

{
  "event_id": "$YUwRidLecu:alice.com"
}

Alice's homeserver adds the JSON to its graph of history, linking it to the most recent unlinked object(s) in the graph.

The server then signs the JSON including the signatures of the parent objects to calculate a tamper-resistent signature for the history.

The server then sends the signed JSON over HTTPS to any other servers which are participating in the room.

curl –XPOST –H 'Authorization: X-Matrix origin=alice.com,...' –d '{
  "ts": 1413414391521,
  "origin": "alice.com",
  "destination": "bob.com",
  "pdus": [{
      "event_id": "$YUwRidLecu:alice.com",
      "content": {
      "body": "hello world",
      "msgtype": "m.text"
    },
    ...
    "pdu_type": "m.room.message",
    "signatures": {
      "matrix.org": {
        "ed25519:auto": "jZXTwAH/7EZ..."
      }
    },
    "sender": "@alice:alice.com"
  }]
}' https://matrix.bob.com:8448/_matrix/federation/v1/send/916d...

The destination servers perform a series of checks on the message:

Validate the message signature to protect against tampering with history
Validate the HTTP request's auth signature to protect against identity spoofing
Validate whether Alice's historical permissions allow her to send this particular message

If these checks pass, the JSON is added to the destination servers' graphs.

Destination clients receive Alice's message with a long-lived GET request. (Clients are free to implement more efficient transports than polling as desired).

curl "https://matrix.bob.com/_matrix/client
 /v2/sync?access_token=ACCESS_TOKEN"
{
  "next_batch": "s72595_4483_1934",
  "rooms": [{
    "room_id": "!KrLWMLDnZAyTapqLWW:alice.com",
    "events": {
      "batch": [{
        "event_id": "$YUwRidLecu:alice.com",
        "type": "m.room.message",
        "content": {
          "body": "I am a fish",
          "msgtype": "m.text",
        },
        "origin_server_ts": 1417731086797,
        "sender": "@alice:alice.com"
      }],
    },
  }]
}

Bob sends a response to Alice's message, and his server adds his message into his copy of the room's history, linking it to the most recent unlinked object in the graph - Alice's last message.

Meanwhile, Charlie also responds to Alice's message - racing with Bob's message.

Alice, Bob and Charlie's homeservers all have different views of the message history at this point - but Matrix is designed to handle this inconsistency.

Bob's homeserver relays his message through to Alice and Charlie's servers, who accept it.

At this point Alice and Bob are in sync, but Charlie's room history has split - both messages 2 and 3 follow on from message 1. This is not a problem; Charlie's client will be told about Bob's message and can handle it however it chooses.

Charlie's homeserver relays his message through as well, at which point all 3 servers have a consistent view of history again (including the race between Bob and Charlie). All three clients have seen all three messages, and the room history is now back in sync across the participating servers.

Later on, Alice sends another message - her homeserver adds it to her history, and links it to the most recent unlinked objects in the graph: Bob and Charlie's messages.

This effectively merges the split in history and asserts the integrity of the room (or at least her view of it).

Alice's message is then relayed to the other participating servers, which accept it and update their own history with the same rules, ensuring eventual consistency and integrity of the distributed room history.