Abstract

Distance bounding protocols are used by nodes in wireless networks to calculate upper bounds on their distances to other nodes. However, dishonest nodes in the network can turn the calculations both illegitimate and inaccurate when they participate in protocol executions. It is important to analyze protocols for the possibility of such violations. Past efforts to analyze distance bounding protocols have only been manual. However, automated approaches are important since they are quite likely to find flaws that manual approaches cannot, as witnessed in literature for analysis pertaining to key establishment protocols. In this paper, we use the constraint solver tool to automatically analyze distance bounding protocols. We first formulate a new trace property called Secure Distance Bounding (SDB) that protocol executions must satisfy. We then classify the scenarios in which these protocols can operate considering the (dis) honesty of nodes and location of the attacker in the network. Finally, we extend the constraint solver so that it can be used to test protocols for violations of SDB in these scenarios and illustrate our technique on some published protocols.

Abstract

Graphics processing units provide a large compu-tational power at a very low price which position them as an ubiquitous accelerator. General purpose programming on the graphics processing units (GPGPU) is best suited for regular data parallel algorithms. They are not directly amenable for algorithms which have irregular data access patterns such as list ranking, and finding the connected components of a graph, and the like. In this work, we present a GPU-optimized implementation for finding the connected components of a given graph. Our implementation tries to minimize the impact of irregularity, both at the data level and functional level. Our implementation achieves a speed up of 9 to 12 times over the best sequential CPU implementation. For instance, our implementation finds connected components of a graph of 10 million nodes and 60 million edges in about 500 milliseconds on a GPU, given a random edge list. We also draw interesting observations on why PRAM algorithms, such as the Shiloach-Vishkin algorithm may not be a good fit for the GPU and how they should be modified.

Abstract

One important challenge in wireless ad hoc networks is to achieve collision free communication. Many MAC layer protocols have been proposed by considering various communication models of the ad hoc networks. One such protocol is TDMA, which provides for interference free communication while providing some bound on the packet delay. However, most proposed TDMA schemes can perform scheduling transmissions among nodes that are within transmission range. This is due to the simplistic modeling of the underlying network. Recently, more practical network models and overlay construction algorithms have been proposed that consider the interference among nodes as well. Existing TDMA protocols are unsuitable for such models as they will have to consider the interference range of the nodes as well. This requires that the TDMA protocol operate in a global perspective while working as a local-control algorithm. In this work, we describe a novel TDMA protocol that is suitable for such realistic and practical network models. We also extend the TDMA protocol to handle other difficulties such as membership changes within transmission range and interference range. Some networks also have to deal with sleeping nodes that wake up periodically. Our TDMA scheme employs a simple control phase and a data phase to handle such tasks. Some of the benefits of our solution are that no knowledge of the network parameters such as the size or an estimate of the size are used. The overhead of our scheme is also very low and (control) messages exchanged are of small size. Our solution will also be self-stabilizing which is an important property for distributed systems. To the best of our knowledge, our TDMA protocol is the first MAC layer protocol for such realistic network models. Additionally, we report some experimental results of our scheme.

Abstract

Symmetry breaking is a fundamental operation in distributed computing. It has applications to important problems such as graph vertex and edge coloring, maximal independent sets, and the like. Deterministic algorithms for symmetry breaking that run in a polylogarithmic number of rounds are not known. However, randomized algorithms that run in poly-logarithmic number of rounds are known starting from Luby's algorithm. Recently, orientation on edges was considered and it was shown that an O(Δ) coloring of the vertices of a given oriented graph can be arrived at using essentially O(log Δ + √log n) bits of communication. In this paper we further demonstrate the power of orientation on edges in symmetry-breaking. We present efficient algorithms to construct fractional independent sets in constant degree graphs using very low order communication between the vertices. For instance, we show that in bounded degree graphs and planar graphs, it is possible to construct a fractional independent set by exchanging O(1) bits. Further, we present algorithms to construct maximal independent sets in bounded degree graphs and oriented trees. Our algorithm for constructing an MIS of an oriented tree uses only O(log n) bits of communication.

Abstract

Graphics Processing Units (GPU) are application specific accelerators which provide high performance to cost ratio and are widely available and used, hence places them as a ubiquitous accelerator. A computing paradigm based on the same is the general purpose computing on the GPU (GPGPU) model. The GPU due to its graphics lineage is better suited for the data-parallel, data-regular algorithms. The hardware architecture of the GPU is not suitable for the data parallel but data irregular algorithms such as graph connected components and list ranking. In this paper, we present results that show how to use GPUs efficiently for graph algorithms which are known to have irregular data access patterns. We consider two fundamental graph problems: finding the connected components and finding a spanning tree. These two problems find applications in several graph theoretical problems. In this paper we arrive at efficient GPU implementations for the above two problems. The algorithms focus on minimising irregularity at both algorithmic and implementation level. Our implementation achieves a speedup of 11-16 times over a corresponding best sequential implementation.

Abstract

Graphics processing units provide a large computational power at a very low price which position them as an ubiquitous accelerator. Efficient primitives that can expand the r ange of operations performed on the GPU are thus important. Discrete Range Searching(DRS) is one such primitive with direct applications to string processing, document and text retrieval systems, and least common ancestor queries. In this work, we present a GPU specific implementation of DRS with an optimal space-time trade off. Toward this end, we also present GPU amenable succinct representations and discuss limitations on the GPU. Our method uses 7.5 bits of additional space per element. The speedup achieved by our method is in the range of 20-25 for preprocessing, and 25-35 for batch querying over a sequential implementation. Compared to an 8-threaded implementation, our methods obtain a speedup of 6-8. We study applications of the DRS on the GPU. Also, we suggest that most graph algorithms which focus on using least common ancestor, can easily be enabled on the GPU based on range minima primitive. Beyond this, we show applications of DRS in string querying and tree queries, and suggest how DRS can be helpful in implementing tree based graph algorithms on the GPU.

Abstract

Heritage structures bears a valuable testimony of ancient cultural heritage of any country. Among these structures statues, iconic emblems plays significant role. In the proposed to study the vulnerability of monolithic statues to earthquake ground motions. Initially we used the equations developed by Housner for studying the dynamics of rigid blocks. Parametric study was conducted to study the inuence of size of the block and input parameters such as amplitude and frequency on the behaviour of the block. The study was extended to generate safe surface for the block of given dimensions. This surface gives the information that with any combination of parameters such as amplitude of vibration, frequency of vibration and duration of vibration, if the point lies outside the surface then block overturns otherwise it is safe. To verify the above formulation we selected four statues, viz, Gomateswara statue, Christ the Redeemer, Statue of Liberty, Guinyin Statue for case study. Initially all the statues were idealized like rigid blocks and later safe surfaces were developed for each statue. Since each statue is having different dimensions, surfaces were are also of different nature. Later, eighteen earthquake records were selected and strong ground motion parameters were estimated. Finally every statue was tested for the safety during the earthquake events. It was found that as the height of the statue is increasing its vulnerability is increasing. However, for all the given ground motions, none of the statue overturned.

Abstract

Many countries have become victims of terrorism on a large scale. Bombs have exploded in and around buildings in many countries causing civilian causalities and structural damage. A bomb explosion with in or around a building can have catastrophic effects, damaging and destroying internal or external portions of the building. Bomb damage to buildings depends on the type and layout of the structure, material used, range of the located explosive device and the charge weight. The impact from the blast causes debris, fire and smoke and hence can result in injury and death of occupants. Escape of the occupants and protection of the valuable documents, equipments, property is possible only when there is minimum damage to structures. This may be achieved by designing the building structures for blast loading. This attempt gives basic idea to all the consultants in estimating the blast loads over the building structures.

Abstract

The amplification of ground motion is being observed during major earthquake events all over the world and is highly dependent on the local geological, topography and geotechnical conditions. In view of this there is a great need to study the local site effects in a seismically active region. In this paper, the numerical modeling of infinite media is carried out by using transmitting boundary condition. Wave interaction with different kinds of boundaries like fixed and viscous boundary is discussed. The heterogeneities in the soil media are taken into account by considering the soft clay and the rock inside the half-space. Peak ground acceleration at the surface is plotted and local amplification of soils is studied by giving Elcentro ground motion as input at the bed rock for both the cases. In the half-space where clay is present, PGA is amplified by a factor of 2.5 with respect to input. More energy is concentrated in the half-space where clay is present. In the half-space where rock is present the area adjacent to the rock is getting amplified as energy is concentrated around the rock.

Abstract

In the case of foundations of bridges, transmission towers, offshore structures and for other type of huge structures, piles are also subjected to lateral loads. This lateral load resistance of pile foundations is critically important in the design of structures under dynamic loading. Load carrying capacity and load deformation behavior of a single pile and group of piles subjected to lateral load is obtained using nonlinear finite element method of analysis. According to Poulos and Davis (1980) the maximum deflection of the pile is the major criterion in its design and made the initial attempts to study the lateral behavior of piles included twodimensional finite element models in the horizontal plane. Several investigations have attempted to study the behavior of pile under lateral load using 3D finite element analysis. In this paper a detailed study on the piles subjected to lateral loads are investigated.