jtmoulia


Distributed Sequence Diagram Syntax

At Spatch we're planning towards a federated system which uses operational transform (OT) for conflict resolution. Part of that process is brainstorming edge or corner cases for challenging our assumptions. I'd like to be able to record these cases in a human-readable format -- suites of tests for our ideas.

Academic Figures

Academic OT papers often feature figures similar to Fig 1. In these diagrams, operations are created at one site, and then shipped to other sites.

cherif_2011_fig3.png

Figure 1: Cherif, 2011

These diagrams are a great way to explore causality in a distributed system. They'd be useful to illustrate the edge cases, but how do you draw them?

UML Sequence Diagrams

I first tried to figure out the name of the diagram. Some brief googling took me to plantuml and its fellow UML tools.

The UML sequence diagram is clearly heading in the right direction visually, and the plantuml syntax is effortless. The catch is that the diagram restricts messages to being delivered instantly -- the signals are fixed to the horizontal:

Messages, written with horizontal arrows with the message name written above them, display interaction

You can hack around it, but the hacks are visual and distracting:

activate A
activate B
A -> B
B -> C
B -> A
A -> C
deactivate A
deactivate B

plantuml_example.png

Figure 2: Hacking at concurrent ops with plantuml

mscgen

Next I found out about message sequence charts: a category of diagrams that encompasses UML sequence diagrams.

mscgen is an fantastically simple executable (despite a X11 dep) for drawing a subset of message sequence charts. It supports delaying the delivery of messages with the arcskip option, but not altering when a message is sent: message n is sent at time n.

Though on the right track, mscgen isn't expressive enough.

msc {
  A,B,C;
  A -> B [ arcskip = "4" ];
  B -> C;
  B -> A;
  A -> C [ arcskip = "3" ];
}

mscgen_example.png

Figure 3: mscgen: simple, but not expressive enough

mscpackage

mscpackage is a LaTeX package for drawing message sequence charts. As usual around LaTeX, mscpackage overcomes its LaTeX dependency and syntax by being the most expressive option. In fact, it's the only option so far which can draw the reference diagram:

\begin{msc}{Classic Example}

\declinst{s1}{Site 1}{abc}
\declinst{s2}{Site 2}{abc}

\msccomment[l]{A = Ins(0, x)}{s1}
\mess{A}{s1}[0.1]{s2}[3]

\msccomment[r]{B = Del(2)}{s2}
\mess{B}{s2}[0.1]{s1}[3]

\nextlevel
\action{xabc}{s1}
\action{ab}{s2}

\nextlevel

\nextlevel
\msccomment[l]{IT(B, A)}{s1}
\msccomment[r]{IT(A, B)}{s2}

\nextlevel
\action{xab}{s1}
\action{xab}{s2}

\end{msc}

mscpackage_example.png

Summary

For my use case, mscpackage is both the winner and only contestant. While it strikes a decent balance between simplicity and power, I think that plantuml's simple syntax could be easily extended to support the control over messages which I need. Food for thought.

Written by

Tags:

Published:

Modified: