results. She navigates to each of the matched messages, one at a time, and finds that two of results have the same “epoch” field value, which violates a correctness property of the

results. She navigates to each of the matched messages, one at a time, and finds that two of the results have the same “epoch” field value, which violates a correctness property of the algorithm. Next, the developer considers the context surrounding the two contradictory messages. By studying the relative ordering of events around these two messages, she sees that one of the hosts, prior to becoming a leader, knew of the other host as the leader. She also sees that the messages preceding this host’s change of state to being a leader are “send” messages to the leader. These messages, however, never receive a reply from the current leader. This eventually causes the local host to declare itself the leader without incrementing the epoch number.

2. A developer wants to know why a replicated data storage sometimes fails to reply to client requests.

In this system, a client contacts the front-end host, which delegates the client to one of the replicated data storage hosts at random. Some clients that contact a replicated data storage system time out waiting for a reply. However, this happens rarely and non-deterministically.

The developer formulates a structured search query to find cases in the recorded execution where a client sent a request but did not receive a response. To do this, the developer uses ShiViz’s graphical interface to describe the scenario visually, as a sub-graph, shown in Figure 5 in Sec- tion 4.2. In the query sub-graph, a message from a client host reaches the front-end in the system, the request is forwarded to some data storage host, but the client does not receive a reply from the front-end within three logged events.

The search returns five locations in the execution graph where the scenario occurred. Looking over the five locations that match this scenario, the developer sees a pattern: The requests that do not receive a response are forwarded to data storage hosts that have been recently added to the storage system. This indicates that a firewall may be the root cause, preventing the storage hosts from communicating back to the front-end because the firewall configuration has not been updated to allow traffic from these hosts to reach the front-end server.

3. A developer is implementing a client library for the SMTP mail transfer protocol. During testing he learns that his implementation does not interoperate with a standard SMTP server. He wants to know how his SMTP implementation differs from other clients.

In implementing his SMTP library, the developer follows the original RFC specification [61]. In response to a test message, an SMTP server responds with 503 Bad sequence of commands and closes the connection.

The developer decides to compare his client-side implementation of the SMTP protocol to a different client-side implementation, Mozilla Thunderbird, which he knows works properly with the same SMTP server. He instruments both SMTP clients and the SMTP server with XVector. He generates an execution trace containing logs for Thunderbird and the server, and then generates an execution trace containing logs for his library and the server. He loads the two executions into ShiViz for analysis.

The developer uses the side-by-side execution comparison ShiViz feature to compare the two executions. Then, he uses the highlight differences ShiViz feature to highlight those events that appear in one execution but do not appear in the other execution. This view reveals that his library never sends the required RCPT command to the server.

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

By contrast, to resolve the issues in these three use cases without ShiViz, a developer today would (1) add logging code, such as print statements, automatically or manually to the system, and (2) study the resulting textual logs, one per node in the system. As a result, without ShiViz, the developer cannot easily understand the partial ordering of concurrent events in the system, and has to piece together what happened by scanning through the individual node logs. Section 9 considers specific tool alternatives and prior research work in more detail.

Summary. These three use cases illustrate the utility of ShiViz’s mechanisms for (1) under- standing the relative ordering of events in an execution, (2) querying for patterns of interaction between hosts in an execution, and (3) identifying structural similarities and differences between pairs of executions.

BACKGROUND: DISTRIBUTED SYSTEMS

This section overviews distributed systems concepts necessary to understand our work.

A distributed system is composed of a number of hosts, and each host generates a totally ordered sequence of events. Each event is associated with a set of attributes, such as the time the event occurred. A host trace is the set of all events generated at one host.

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.