Auditability: An Approach to Ease Debugging of Reliable Distributed Systems There are various means of providing dependability, one of which is fault removal and debugging is one popular example of a fault removal technique. During debugging, the system is executed, and execution data is collected, to be analysed later, to determine if the execution has satisfied the system specification. In a distributed system, the data collection is done centrally via a monitor, and the assumption typically is that all the nodes are correct. However, in open distributed systems such as the Internet of Things (IoT), there is no central authority to enforce this assumption and nodes may behave arbitrarily by violating protocol steps, making processes such as debugging very challenging. We call the data collection process for such processes auditing and a program that reliably records such data as being auditable. In this context, we make the following novel contributions towards auditability enforcement: (i) we define the auditability problem and (ii) identify a necessary condition for a program to be auditable. We then provide examples of auditable programs. Subsequently, (iii) we show an impossibility result for strong auditability. To circumvent this impossibility, we study a weaker problem and discuss the ramifications of certain implementations. Finally, we show that auditability is at least as difficult as the problem of fair exchange. This is the first formal work towards the design of reliable systems through audibility.

Using Weaker Consistency Models with Monitoring and Recovery for Improving Performance of KeyValue Stores Limitations of the CAP theorem imply that if availability is desired in the presence of faults xe2x80x93 especially that create network partitions (or substantial delays), one must sacrifice sequential consistency, a consistency model that is more natural for system design. We focus on the problem of what a designer should do if heshe has an algorithm that works correctly with sequential consistency but is faced with an underlying keyvalue store that provides a weaker (e.g., eventual or causal) consistency. We propose a detectrollback based approach: The designer identifies a correctness predicate, say P, and continues to run the protocol, as our system monitors P. If P is violated (because the underlying keyvalue store provides a weaker consistency), the system rolls back and resumes the computation at a state where P holds. We evaluate this approach with practical graph applications running on the Voldemort keyvalue store. Our experiments, deployed on Amazon AWS EC2 instances, show that using eventual consistency with monitoring can provide a 50 xe2x80x93 80% increase in throughput when compared with sequential consistency. We also show that the overhead of the monitoring itself is low (typically less than 4%) and the latency of detecting violations is small. In particular, more than 99.9% of violations are detected in less than 50 milliseconds in regional AWS networks, and in less than 5 seconds in global AWS networks. In turn, this makes it possible to provide efficient recovery from such faults with a minimal amount of work wasted due to rollbacks.