Raymond P.L. Buse, Westley Weimer. A Metric for Software Readability. To appear in International Symposium on Software Testing and Analysis (ISSTA) 2008.

Several recent research results describe how to design Distributed Hash Tables (DHTs) that are robust to adversarial attack via Byzantine faults. Unfortunately, all of these results require a significant blowup in communication costs over standard DHTs. For example, to perform a lookup operation, all such robust DHTs of which we are aware require sending O(log³n) messages while standard DHTs require sending only O(log n), where n is the number of nodes in the network. In this paper, we describe protocols to reduce the communication costs of all such robust DHTs. In particular, we give a protocol to reduce the number of messages sent to perform a lookup operation from O(log³n) to O(log² n) in expectation. Moreover, we also give a protocol for sending a large (i.e. containing Ω(log⁴n) bits) message securely through a robust DHT that requires, in expectation, only a constant blowup in the total number of bits sent compared with performing the same operation in a standard DHT. This is an improvement over the O(log²n) bit blowup that is required to perform such an operation in all current robust DHTs. Both of our protocols are robust against an adaptive adversary.

Reducing Communication Costs in Robust Peer-to-Peer Networks. Jared Saia and Maxwell Young. In Information Processing Letters (IPL), 2008.

Power is one of the most critical resources in battery-operated devices. In this paper, we address the problem of minimizing power consumption when performing reliable broadcast on a radio network. We consider the following popular model of a radio network. Each node in the network is located on a point in a two dimensional grid, and whenever a node sends a message, all awake nodes within L∞ distance r, for some fixed r, receive the message...

Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks, Valerie King, Cynthia Phillips, Jared Saian and Maxwell Young, Principles of Distributed Computing (PODC), 2008

We resolve two long-standing open problems in distributed computation by describing polylogarithmic protocols for Byzantine agreement and leader election in the asynchronous full information model with a non-adaptive malicious adversary. All past protocols for asynchronous Byzantine Agreement had been exponential, and no protocol for asynchronous leader election had been known. Our protocols tolerate up to n/(6+ǫ) faulty processors, for any positive constant ǫ. They are Monte Carlo, succeeding with probability 1 − o(1) for Byzantine agreement, and constant probability for leader election. A key technical contribution of our paper is a new approach for emulating Feige’s lightest bin protocol, even with adversarial message scheduling.

Fast Asynchronous Byzantine Agreement and Leader Election with Full Information, Bruce Kapron, David Kempe, Valerie King, Jared Saia and Vishal Sanwalani. In Symposium on Discrete Algorithms (SODA), 2008.