Abstract

We aim at an empirical analysis of distributed vertex coloring algorithms. To this end, we compare the empirical performance of a recently proposed distributed vertex coloring algorithm [8] with that of Luby's algorithm. To get a good coverage we look at the cycle graph on n vertices, cliques, and random graphs from the family G(n, p) by controlling n, p and np. The results of our experiments fairly demonstrate the improvement in the bit complexity of the algorithm proposed in [8]. Our results also match those of the experiments of Panconesi et. al. [3] on Luby's algorithm.

Abstract

Scenarios such as online banking, mobile payment systems, stock trading, selling merchandise, and a host of other applications that need a high level of security have moved from the research domain to real world. Moreover, the nature of clients has been changing from traditional desktops to mobile and handheld devices. Protocols like SSL, SSH are the present standard for establishing secure channels. However, the drawback in these protocols is that both the server and the client need to perform computationally expensive public-key operations for secure channel establishment. In this paper, we present simple constructions that spread the cost of secure channel establishment over several sessions. Our constructions are incrementally deployable and can operate with existing protocols such as SSL and SSH. Experimental results indicate that our constructions are practical and efficient in reducing the computational load at the server as well as the client side.

Abstract

In this paper, we address the security of routing protocols. Internet routing protocols are subject to attacks in the control plane as well as the data plane. In the control plane, a routing protocol, e.g., BGP, OSPF, exchanges routing state updates and enables routers to compute the best paths towards various destinations. During this phase, an attacker can modify or inject malicious control messages leading to incorrect computation of routing paths. In the data plane, the routers forward the data along the paths computed in the control plane. Even if an attacker is not successful during the control phase, he can choose not to use the correct routing paths and forward data along routes that benefit him. Research shows that, attacks on the control plane can be mitigated by ensuring message integrity and, attacks on the data plane can be mitigated by ensuring route integrity. Earlier works have addressed these two problems independently with many interesting solutions. However, due to the nature of these solutions, network architects cannot deploy security at both planes without increasing the overhead on the network. In this paper, we focus on an integrated approach and propose the use of symmetric key protocols for addressing the security at both the control and data planes. We describe approaches that enable the reuse of the symmetric key protocols thereby eliminating the need for separate solutions at different planes. We used symmetric key protocols as they are efficient and scalable. Our experimental results show that our approaches are practical and can be incrementally deployed as well.

Abstract

people volunteer their time and energy and work in a dedicated fashion to pull everything together each year, including our very supportive Steering Comm-tee members led by Sukumar Ghosh. However, the success of ICDCN is mainly due to the hard work of all those people who submit papers and/or attend the conference. We thank you all. January 2009 Prasad Jayanti Andrew T. Campbell Message from the Technical Program Chairs Welcome to the proceedings of the 10thInternationalConferenceon Distributed Computing and Networking (ICDCN) 2009. As ICDCN celebrates its 10th-niversary, ithasbecomeanimportantforumfordisseminatingthelatestresearch results in distributed computing and networking. We received 179 submissions from all over the world, including Algeria, A-tralia, Canada, China, Egypt, France, Germany, Hong Kong, Iran, Italy, Japan, Malaysia, The Netherlands, Poland, Singapore, South Korea, Taiwan, and the USA, besides India, the host country. The submissions were read and evaluated by the Program Committee, which consisted of 25 members for the Distributed Computing Track and 28 members for the Networking Track, with the ad-tional help of external reviewers. The Program Committee selected 20 regular papers and 32 short papers for inclusion in the proceedings and presentation at the conference. We were fortunate to have several distinguished scientists as keynote speakers. Andrew Campbell (Dartmouth College, USA), Maurice Herlihy (Brown University, USA), and PR Kumar (University of of Illinois, Urbana-Champaign) delivered the keynote address. Krithi Ramamritham from IIT Bombay, India

Abstract

General purpose programming on the graphics processing units (GPGPU) has received a lot of attention in the parallel computing community as it promises to offer the highest performance per dollar. The GPUs have been used extensively on regular problems that can be easily parallelized. In this paper, we describe two implementations of List Ranking, a traditional irregular algorithm that is difficult to parallelize on such massively multi-threaded hardware. We first present an implementation of Wyllie's algorithm based on pointer jumping. This technique does not scale well to large lists due to the suboptimal work done. We then present a GPU-optimized, Recursive Helman-JaJa (RHJ) algorithm. Our RHJ implementation can rank a random list of 32 million elements in about a second and achieves a speedup of about 8-9 over a CPU implementation as well as a speedup of 3-4 over the best reported implementation on the Cell Broadband engine. We also discuss the practical issues relating to the implementation of irregular algorithms on massively multi-threaded architectures like that of the GPU. Regular or coalesced memory accesses pattern and balanced load are critical to achieve good performance on the GPU.

Abstract

An acyclic vertex coloring of a graph is a proper vertex coloring such that there are no bichromatic cycles. The acyclic chromatic number of G, denoted a (G), is the minimum number of colors required for acyclic vertex coloring of graph G=(V, E). In this paper we show that for any graph G with maximum degree∆, a (G)≤ 3∆ 2+ 4∆+ 8

Abstract

The significant growth in computational power of modern Graphics Processing Units (GPUs) coupled with the advent of general purpose programming environments like NVIDIA's CUDA, has seen GPUs emerging as a very popular parallel computing platform. Till recently, there has not been a performance model for GPGPUs. The absence of such a model makes it difficult to definitively assess the suitability of the GPU for solving a particular problem and is a significant impediment to the mainstream adoption of GPUs as a massively parallel (super)computing platform. In this paper we present a performance prediction model for the CUDA GPGPU platform. This model encompasses the various facets of the GPU architecture like scheduling, memory hierarchy, and pipelining among others. We also perform experiments that demonstrate the effects of various memory access strategies. The proposed model can be used to analyze pseudo code for a CUDA kernel to obtain a performance estimate, in a way that is similar to performing asymptotic analysis. We illustrate the usage of our model and its accuracy with three case studies: matrix multiplication, list ranking, and histogram generation.

Abstract

In this paper, we discuss the numerical modeling of infinite media using transmitting boundary condition. This is done for simulating the propagation of elastic waves in soil media. Wave interaction with different kinds of boundaries is discussed explaining the numerical modeling procedure. Wave propagation in different directions is studied while calculating the velocities in different soil domain. For investigating the above-mentioned objectives, we used newly developed numerical model, viz., Applied Element Method and compared our results with Finite Element Method (FEM).

Abstract

Earthquake problems in India need no introduction. Some of the great earthquakes of the world occurred in India and neighborhood areas. During past two decades, India has witnessed 7 moderate earthquakes which caused large number of casualties and innumerable property loss. Most of these losses are due to poor quality of construction and generally low level of awareness of the earthquake hazard prevalent in the country. In this regard, there is a need for coordinated and sustained effort towards earthquake risk reduction in the country. This can be achieved through education and awareness building.

Abstract

Pipelines are common transportation means for oil and natural gas, which act as an important lifeline facility for any nation. Often the design of these pipelines is a difficult task because they commonly are installed underground passing through different types of soil media. Many of these existing pipelines run through the faulted area, which continuously exposed to considerable risk of failure due to movement along the fault. Installation and maintenance costs of these pipelines directly depend on the total length of the pipelines. Furthermore ideal alignment for any pipeline as a straight line between the source and destination point is not that easy in the area where fault are present. It becomes necessary to divert the alignment about fault line which increases the length and subsequently operational and installation costs of pipeline. Common problems seen in the pipeline crossing the fault are change of alignment due to movement along the fault.