  Matrix is a new kind of decentralized, topic-based publish-subscribe
middleware for communication and data storage that is getting popular
particularly as a basis for secure instant messaging. In comparison to
traditional decentralized communication systems, Matrix replaces pure message
passing with a replicated data structure. This data structure, which we extract
and call the Matrix Event Graph (MEG), depicts the causal history of messages.
We show that this MEG represents an interesting and important replicated data
type for general decentralized applications that are based on causal histories
of publish-subscribe events: we show that a MEG possesses strong properties
with respect to consistency, byzantine attackers, and scalability. First, we
show that the MEG provides Strong Eventual Consistency (SEC), and that it is
available under partition, by proving that the MEG is a Conflict-Free
Replicated Data Type for causal histories. While strong consistency is
impossible here as shown by the famous CAP theorem, SEC is among the best known
achievable trade-offs. Second, we discuss the implications of byzantine
attackers on the data type's properties. We note that the MEG, as it does not
strive for consensus, can cope with $n > f$ environments with $n$ total
participants of which $f$ show byzantine faults. Furthermore, we analyze
scalability: Using Markov chains we study the width of the MEG, defined as the
number of forward extremities, over time and observe an almost optimal
evolution. We conjecture that this property is inherent to the underlying
spatially inhomogeneous random walk.
