Efficient Algorithms for Anonymous Byzantine Agreement

This paper considers the Byzantine agreement problem in a completely connected network of anonymous processors. In this network model the processors have no identifiers and can only detect the link through which a message is delivered. We present a polynomial-time agreement algorithm that requires 3⌊(n−t)t/(n−2t)⌋+4 rounds, where n>3t is the number of processors and t is the maximal number of faulty processors that the algorithm can tolerate. We also present an early-stopping variant of the algorithm.     

Bayes networks for estimating the number of solutions of constraint networks

The problem of counting the number of solutions to a constraint network (CN) (also called constraint satisfaction problems, CSPs) is rephrased in terms of probability updating in Bayes networks. Approximating the probabilities in Bayes networks is a problem which has been studied for a while, and may well provide a good approximation to counting the number of solutions. We use a simple approximation based on independence, and show that it is correct for tree‐structured CNs. For other CNs, it is less optimistic than a spanning‐tree approximation suggested in prior work. Experiments show that the Bayes nets estimation is more accurate on the average, compared to competing methods (the spanning‐tree, as well as a scheme based on a product of all compatible pairs of values). We present empirical evidence that our approximation may also be a useful (value ordering) search heuristic for finding a single solution to a constraint satisfaction problem. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the Evolution Complexity of Design Patterns

Software co-evolution can be characterised as a way to “adjust” any given software implementation to a change (“shift”) in the software requirements. In this paper, we propose a formal definition of evolution complexity to precisely quantify the cost of adjusting a particular implementation to a change (“shift”) in the requirements. As a validation, we show that this definition formalises intuition about the evolvability of design patterns.     

A new approach for approximating node deletion problems

We present a new approach for approximating node deletion problems by combining the local ratio and the greedy multicovering algorithms. For a function , our approach allows to design a 2+max_v∈V(G)logf(v) approximation algorithm for the problem of deleting a minimum number of nodes so that the degree of each node v in the remaining graph is at most f(v). This approximation ratio is shown to be asymptotically optimal. The new method is also used to design a 1+(log2)(k−1) approximation algorithm for the problem of deleting a minimum number of nodes so that the remaining graph contains no k-bicliques.     

Impact of safety belt use on road accident injury and injury type in Kuwait

The enactment of Kuwait's seat belt law in January 1994 provided an opportunity to examine the impact of seat belt use on road accident fatalities and injury types in this affluent Persian Gulf nation. Via a structured data form, the results of injurious/fatal road accidents for more than 1200 accident victims were gathered from the files of the six major government hospitals which treat most traffic accident victims. Statistical analysis of the data showed that seat belt use has had a positive effect in reducing both road traffic fatalities and multiple injuries in Kuwait. The use of seat belts has also affected the nature of the injuries resulting from road traffic accidents. Non-users of belts experienced higher frequencies of head, face, abdominal and limb injuries. Users of belts, on the other hand, suffered higher frequencies of neck and chest injuries. The interrelationship between the victim, his age, and the type of injuries resulting from road traffic accidents is also investigated.     

Experimental model aid for planar design of transistor characteristics in integrated circuits

A two-transistor lumped model is used to describe the main features of transistors' two dimensional action. The model provides a first order correction to the ideal one dimensional transistor gain due to the effect of the emitter periphery. The correction is given in terms of a single parameter which can be experimentally evaluated for a fixed diffusion process. This makes the model a practical tool in I.C. transistor layout design. Experimental virification of the model is presented. Finally, implication to gain and cutoff frequency falloff due to lateral injection at high current is suggested.     

Message delay and DisCSP search algorithms

Distributed constraint satisfaction problems (DisCSPs) are composed of agents, each holding its own variables, that are connected by constraints to variables of other agents. Due to the distributed nature of the problem, message delay can have unexpected effects on the behavior of distributed search algorithms on DisCSPs. This has been recently shown in experimental studies of asynchronous backtracking algorithms (Bejar et al., Artif. Intell., 161:117–148, 2005; Silaghi and Faltings, Artif. Intell., 161:25–54, 2005). To evaluate the impact of message delay on the run of DisCSP search algorithms, a model for distributed performance measures is presented. The model counts the number of non concurrent constraints checks, to arrive at a solution, as a non concurrent measure of distributed computation. A simpler version measures distributed computation cost by the non-concurrent number of steps of computation. An algorithm for computing these distributed measures of computational effort is described. The realization of the model for measuring performance of distributed search algorithms is a simulator which includes the cost of message delays. Two families of distributed search algorithms on DisCSPs are investigated. Algorithms that run a single search process, and multiple search processes algorithms. The two families of algorithms are described and associated with existing algorithms. The performance of three representative algorithms of these two families is measured on randomly generated instances of DisCSPs with delayed messages. The delay of messages is found to have a strong negative effect on single search process algorithms, whether synchronous or asynchronous. Multi search process algorithms, on the other hand, are affected very lightly by message delay.