Steward: Scaling Byzantine Fault-Tolerant Replication to Wide Area Networks

This paper presents the first hierarchical Byzantine fault-tolerant replication architecture suitable to systems that span multiple wide-area sites. The architecture confines the effects of any malicious replica to its local site, reduces message complexity of wide-area communication, and allows read-only queries to be performed locally within a site for the price of additional standard hardware. We present proofs that our algorithm provides safety and liveness properties. A prototype implementation is evaluated over several network topologies and is compared with a flat Byzantine fault-tolerant approach. The experimental results show considerable improvement over flat Byzantine replication algorithms, bringing the performance of Byzantine replication closer to existing benign fault-tolerant replication techniques over wide area networks.     

Task Switching After Cerebellar Damage.

The authors of this study investigated task switching following cerebellar damage. The study group consisted of 7 children and adolescents (M age = 13.8 years) who underwent surgical removal of a benign posterior fossa tumor. They were tested at a sufficient interval after surgery (M lag = 6.13 years) for restoration of normal cognitive skills and intelligence. Although all showed normal learning of the task compared with control participants, when rapid behavioral changes were required (short preparation time), they exhibited behavioral rigidity manifested by enhanced switching cost. These results are in line with another study on serial reaction time with the same patients (A. Berger et al., in press). They have important implications for our understanding of the cognitive sequelae of early cerebellar damage as well as the involvement of the cerebellum in task switching. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

Communication adaptive self-stabilizing group membership service

This paper presents the first (randomized) algorithm for implementing self-stabilizing group communication services in an asynchronous system. Our algorithm converges rapidly to legal behavior and is communication adaptive, namely, the communication volume is high when the system recovers from the occurrence of faults and is low once a legal state is reached. Communication adaptability is achieved by a new technique that combines transient fault detectors.     

Dynamic attribute based vehicle authentication

Modern vehicles are proficient in establishing a spontaneous connection over a wireless radio channel, synchronizing actions and information. Security infrastructure is most important in such a sensitive scope of vehicle communication for coordinating actions and avoiding accidents on the road. One of the first security issues that need to be established is authentication via IEEE 1609.2 security infrastructure. According to our preliminary work, vehicle owners are bound to preprocess a certificate from the certificate authority. The certificate carries vehicle static attributes (e.g., licence number, brand and color) certified together with the vehicle public key in a monolithic manner. Nevertheless, a malicious vehicle might clone the static attributes to impersonate a specific vehicle. Therefore, in this paper we consider a resource expensive attack scenario involving multiple malicious vehicles with identical visual static attributes. Apparently, dynamic attributes (e.g., location and direction) can uniquely define a vehicle and can be utilized to resolve the true identity of the vehicle. However, unlike static attributes, dynamic attributes cannot be signed by a trusted authority beforehand. We propose an approach to verify the coupling between non-certified dynamic attributes and certified static attributes on an auxiliary communication channel, for example, a modulated laser beam. Furthermore, we illustrate that the proposed approach can be used to facilitate the usage of existing authentication protocols such as NAXOS, in the new scope of ad-hoc vehicle networks. We use BAN logic to verify the security claims of the protocol against the passive and active interception.     

Optical solution for hard on average #P-complete instances (using exponential space for solving instances of the permanent)

Optical architectures that use exponential space for solving instances of the (non-necessarily-binary) permanent are presented. This is the first work to specifically focus on such hard on average problems. Two architectures are suggested the first is based on programmable masks, and the second on preprepared fixed number of masks.     

Choice coordination with limited failure

The Choice Coordination Problem requiresn asynchronous processes to reach a common choice of one out ofk possible alternatives. Processes communicate viak shared variables. Up tot, t, of the processes may fail to operate by suddenly quitting the protocol. Rabin (1982) presented lower and upper bounds for the extreme caset=n–1. We present deterministic and randomized algorithms for arbitraryt using an alphabet of sizeO(t ²). A semi-synchronous model is also studied. A reduction to a consensus problem proves the necessity to assume some powerful atomic shared-memory operations.     

Analyzing expected time by scheduler-luck games

We introduce a novel technique, the scheduler luck game (in short sl-game) for analyzing the performance of randomized distributed protocols. We apply it in studying uniform self-stabilizing protocols for leader election under read/write atomicity. We present two protocols for the case where each processor in the system can communicate with all other processors and analyze their performance using the sl-game technique     

Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement

We describe several new algorithms for Byzantine agreement. The first of these is a simplification of the original exponential-time Byzantine agreement algorithm due to Pease, Shostak, and Lamport, and is of comparable complexity to their algorithm. However, its proof is very intuitively appealing. A technique of shifting between algorithms for solving the Byzantine agreement problem is then studied. We present two families of algorithms obtained by applying a shift operator to our first algorithm. These families obtain the same rounds to message length trade-off as do Coan's families but do not require the exponential local computation time (and space) of his algorithms. We also describe a modification of an -resilient algorithm for Byzantine agreement of Dolev, Reischuk, and Strong. Finally, we obtain a hybrid algorithm that dominates all our others, by beginning execution of an algorithm in one family, first shifting into an algorithm of the second family, and finally shifting into an execution of the adaptation of the Dolev, Reischuk, and Strong algorithm.