Order is an important property of a distributed execution. Events are ordered in two ways. First, the host ordering orders every pair of events at the same host, but does not order events that occur at different hosts. Second, the interaction ordering orders dependent events at different hosts; for example, if two hosts use message passing to communicate, a send message event is ordered before the receive message event for the same message. Taken together, the host and interaction ordering generate a partial ordering over all events in the execution. The partial ordering is known as the happens-before relation [68]. Understanding this partial order is central to most tasks that a distributed system developer performs.

Figure 1 is a time-space diagram, which is the standard visualization of the happens-before relation in a distributed system [66]. (ShiViz displays distributed system executions as time-space diagrams; see Figure 2.) The time-space diagram expresses happens-before relations as directed edges between events. (This ordering is transitive, but for clarity, the diagram omits transitive edges.) For example, in the diagram, the tx prepare event at TX Manager occurs before the abort event at Replica 1 (there is an edge from tx prepare to abort). In a time-space diagram, two events are concurrent if the time-space diagram lacks a directed path between them. For example, in Figure 1 there is no directed path between the concurrent events abort at Replica 1 and commit at Replica 2.

One way to represent partial order in a system trace is to associate a vector clock timestamp with each event. These timestamps make explicit the partial order of events in the system trace. The remainder of this section briefly explains vector time and an algorithm to record vector timestamps in a distributed system [36, 80]. Though more efficient vector clock mechanisms exist [4, 6], we believe that vector timestamps [36, 80] are practical for debugging: short time periods on large systems, or during development and testing.

For concreteness, our explanation below assumes that the distributed system uses message passing, but vector timestamps are equally applicable to a system that uses other mechanisms for inter-host communication, such as shared memory.

ACM Transactions on Software Engineering and Methodology, Vol. 29, No. 2, Article 9. Pub. date: March 2020.

Fig. 1. Time-space diagram illustrating an execution of the two-phase commit protocol [8] with one transaction manager and two replicas. The vertical lines represent the host ordering, and the diagonal lines represent the interaction ordering. Each event has an associated vector timestamp. For conciseness, this time-space diagram does not explicitly include message send and receive events.

Ordering Events with Vector Time

In a distributed system of h hosts, each host maintains a local logical time. In addition, each host maintains a vector clock, which is an underestimate of the logical time at all hosts. A vector clock = is an array of monotonically increasing clocks C [c 0, c 1, . . . ,c h1], where c j represents the local logical time at host j. C denotes the vector clock at host i and C [j] represents its current knowledge about the local logical time at j.

The hosts update their clocks to reflect the execution of events in the system by following:

(  ) Each host starts with an initial vector clock [ , . . . , ].
(  ) After a host i generates an event, it increments its own clock value (at index i) by , i.e., ++ C [i] . Sending and receiving a message are each considered an event.
(  ) Every message sent by a host i includes the value of its vector clock C. Upon receiving the message,Software Engineering and Methodology, Vol. 29, No. 2, Article 9. Pub. date: March 2020.

The execution graph in ShiViz is accessible in the left panel and is linked to the execution graph through visual cues. Hovering over an event or clicking on an event in the graph highlights the background of the corresponding log line in the left panel. This informative feedback supports the developer's mental model that the execution graph is a more structured representation of the log. For example, the selected event in Figure 2 corresponds to the highlighted log line "Closed, exiting". Likewise, clicking on a log line on the left highlights "The log lines are positioned to horizontally align with their corresponding events to strengthen the association". However, this also means that the log lines may appear in an order different from the order of log lines in the input log but always one consistent with the partial order and one that could have been generated by the same execution.

4.1.2 Associating Log Lines with Hosts

To make it easy to spot the lines in the log associated with a specific host, each host in the execution graph is associated with a color that is used for its host box, event circles, and log lines. This color-coding works best when displaying few enough hosts to allow ShiViz not to reuse host colors.

4.1.3 Graph Transformations

The execution graph may contain a large number of events, including ones that are not relevant to a developer's task. ShiViz includes three graph transformations shown in Figure 3 to help developers focus on relevant behavior in the execution.

Transformation 1: collapse local events