Abstract

Finding the biconnected components of a graph has a large number of applications in many other graph problems including planarity testing, computing the centrality metrics, finding the (weighted) vertex cover, coloring, and the like. Recent years saw the design of efficient algorithms for this problem across sequential and parallel computational models. However, current algorithms do not work in the setting where the underlying graph changes over time in a dynamic manner via the insertion or deletion of edges. Dynamic algorithms in the sequential setting that obtain the biconnected components of a graph upon insertion or deletion of a single edge are known from over two decades ago. Parallel algorithms for this problem are not heavily studied. In this paper, we design shared-memory parallel algorithms that obtain the biconnected components of a graph subsequent to the insertion or deletion of a batch of edges

Abstract

2022 IEEE International Conference on Blockchain (Blockchain) BLOC KVAC: A Un iversally Acceptable and Ideal Vaccination System on Blockchain Manik a Sharma Center for Securit y, Theory, and Algorithmic Research Intern ationa l Institute of Inform ation Technology, Hyderabad Gach ibowli, Hyderabad, India 500 032 manik a.sharm a @research.iiit.ac.in Kishore Kothap alli Cent er for Securit y, Theo ry, and Algorithmic Research Interna tional Institute of Information Technology, Hyderabad Gachibowli, Hyderabad , Indi a 500 032 kisho re @iiit.ac .in Sujit Gujar Machin e Learning Lab International Institute of Information Technology, Hyderabad Gachib owli, Hyderabad , India 500 032 suj it.gujar @iiit.ac.in Abstract-Vaccines are essential in pro tecting indivi dua ls and commun ities from the risk of ha rmful an d fatal diseases. The wor ld is migra ting towards the digitization of vacci nation docu- mentation. Still, the current digita l vacci nation is a centra lized mode l, lacking a nnive rsal acceptance. A Universally Acceptable an d Id eal Vacci nat ion System (UAIVS ) sho nld possess (a) a sta ndard vaccination cert ificate ver ificat ion algorithm, (h) p r i- vacy to per sonal in form a tion, (c) sca lab ilit y, (d) s npport lor all vacci nat ions, (e) acco u ntab ility for vaccination information access, and (f) a sco pe for scientific researc h a nd d evelopm en t. Blockc ha in tec hno logy int ro dnces d ecentr alizat ion, immn tability, acco unta bility, per sistence, and liveliness. T hese pro per ties ma ke block cha in an ideal can di da te to solve the existing pro blems in digital vacci nat ion. In this pa per, we prop ose a novel blockchain- base d syste m, n am ely BLO CKVAC, to implem ent a UA IVS . F urt her more , o ur wor k provi des a way to track an individ nal's an d fa mily's vacc ination histo ry, which is esse ntial for sc ient ific research a nd developm ent . BLOCKVAC is highly modular, sca l- a ble, an d cost -efficien t, pr oviding eno ugh roo m for fnt n re feature addi tio ns. The c urre nt works lack cost and sca lab ility ana lysis. WI' show thc scalability of o ur system t hro ugh a th oron gh a nalys is. O ur impl em entation shows t hat add ing one vacc inati on re cor d costs 7 . l(j ~2 ~ x 10- 6 ETH ( ~ U.U26US D) for reg istratio n, 2.5089 x 10- 5 ETH ( ~ 0.07 8USD) for vaccina tion, a nd th e syste m ca n easi ly han dl e np to 20K vaccinations per hon r. Ind ex Terms- B1ockc ha in, Eth ere um, Sm art Contrac ts, Public Acco unta bility, Sca lab ilit y I. I N TR O D UC TI O N The vaccination process, also known as imm unization , was introduced in the late 18th century by the British physician Edward Jenn er against the deadly smallpox virus [ I]. Since then. it has become an inevitab le medical proc edur e, protecting individuals and communities from harmful and fatal diseases. The World Hea lth Organi zation (WHO) estimates that vac- cination saves around 2.5 millio n child lives every year [2]. A record of vacci nation details massively aid s in providing qualit y health care to individuals [3]. Whi le secure storage and verificat ion of vaccination details are challenges even within a country, it is tediou s to merge them from across all the countries [4 ]. Moreover. a definitive process is the need of the hour to verify the required vaccinati on certification for travelers when they enter a country. We wou ld like to than k MeitY and Ripp le for fundin g this research . O ver view of existing vac cina tion mod els: Traditional paper- based vaccination records [5] are prone to challenges such as the possibil ity of losing, damaging, or forging the records without any accountability. Digital solutions replace the need for paper, provide an immutable card, and reduc e manual labor [6]. However, the current vacci nation systems follow a centralized model, where the users need to trust the cent ral autho rity. Further. these sys tems are prone to single-point failures and jeopardize data security P 1. Moreover, current vaccination portal s mainly deal with just slot bookings and issuin g non -verifiab le vaccination certificates. Mo tiva tion: Th e Covid-19 pandemic has caused a digital revolution in vaccination data managem ent. Countri es are shifting towards a digital solution to secure vaccination data ami issue certificates. However, such a system should be universally acceptabl e. We identi fy the properties requ ired for such a sys tem and call it a Universally Acceptable and Ideal Vaccination System (UA IVS). We furt her categorize the proper- ties of UAIVS into two subcategories: Universally Acceptable Vaccination System and Ideal Va ccination System. A Universally Acce ptable Vaccination System co

Abstract

Welcome to virtual HiPC 2021, the 28th edition of the IEEE International Conference on High Performance Computing, Data, and Analytics. It serves as a forum to present current work by accomplished HPC researchers from around the globe, to explore developing topics in the field, and to highlight related activities in Asia.

Abstract

— Centrality measures on graphs have found applications in a large number of domains including modeling the spread of an infection/disease, social network analysis, and transportation networks. As a result, parallel algorithms for computing various centrality metrics on graphs are gaining significant research attention in recent years. In this paper, we study parallel algorithms for the percolation centrality measure which extends the betweenness-centrality measure by incorporating a time dependent state variable with every node. We present parallel algorithms that compute the source-based and source-destination variants of the percolation centrality values of nodes in a network. Our algorithms extend the algorithm of Brandes, introduce optimizations aimed at exploiting the structural properties of graphs, and extend the algorithmic techniques introduced by Sariyuce et al. [26] in the context of centrality computation. Experimental studies of our algorithms on an Intel Xeon(R) Silver 4116 CPU and an Nvidia Tesla V100 GPU on a collection of 12 real-world graphs indicate that our algorithmic techniques offer a significant speedup.

Abstract

Centrality measures on graphs have found appli- cations in a large number of domains including modeling the spread of an infection/disease, social network analysis, and transportation networks. As a result, parallel algorithms for computing various centrality metrics on graphs are gaining significant research attention in recent years. In this paper, we study parallel algorithms for the percolation centrality measure which extends the betweenness-centrality measure by incorporating a time dependent state variable with every node. We present parallel algorithms that compute the source-based and source-destination variants of the percolation centrality values of nodes in a network. Our algorithms extend the algorithm of Brandes, introduce optimizations aimed at exploiting the structural properties of graphs, and extend the algorithmic techniques introduced by Sariyuce et al. [26] in the context of centrality computation. Experimental studies of our algorithms on an Intel Xeon(R) Silver 4116 CPU and an Nvidia Tesla V100 GPU on a collection of 12 real-world graphs indicate that our algorithmic techniques offer a significant speedup.

Abstract

— The effect of adjusting damping factor α and tolerance τ on iterations needed for PageRank computation is studied here. Relative performance of PageRank computation with L1, L2, and L∞ norms used as convergence check, are also compared with six possible mean ratios. It is observed that increasing the damping factor α linearly increases the iterations needed almost exponentially. On the other hand, decreasing the tolerance τ exponentially decreases the iterations needed almost exponentially. On average, PageRank with L∞ norm as convergence check is the fastest, quickly followed by L2 norm, and then L1 norm. For large graphs, above certain tolerance τ values, convergence can occur in a single iteration. On the contrary, below certain tolerance τ values, sensitivity issues can begin to appear, causing computation to halt at maximum iteration limit without convergence. The six mean ratios for relative performance comparison are based on arithmetic, geometric, and harmonic mean, as well as the order of ratio calculation. Among them GM-RATIO, geometric mean followed by ratio calculation, is found to be most stable, followed by AM-RATIO.

Abstract

The effect of adjusting damping factor α, from a small initial value α0 to the final desired αf value, upon then iterations needed for PageRank computation is observed. Adjustment of the damping factor is done in one or more steps. Results show no improvement in performance over a fixed damping factor based PageRank.

Abstract

We study several fundamental problems in the kmachine model, a message-passing model for large-scale distributed computations where k 2 machines jointly perform computations on a large input of size N, (typically, N k). The input is initially partitioned (randomly or in a balanced fashion) among the k machines, a common implementation in many real-world systems. Communication is point-to-point, and the goal is to minimize the number of communication rounds of the computation. Our main result is a general technique for designing efficient deterministic distributed algorithms in the k-machine model using PRAM algorithms. Our technique works by efficiently simulating PRAM algorithms in the k-machine model in a deterministic way. This simulation allows us to arrive at new algorithms in the k-machine model for some problems for which no efficient k-machine algorithms are known before and also improve on existing results in the k-machine model for some problems. While our simulation allows us to obtain k-machine algorithms for any problem with a known PRAM algorithm, we mainly focus on graph problems. For an input graph on n vertices and m edges, we obtain O˜(m/k2) round4 algorithms for various graph problems such as r–connectivity for r = 1, 2, 3, 4, minimum spanning tree (MST), maximal independent set (MIS), (Δ+1)-coloring, maximal matching, ear decomposition, and spanners under the assumption that the edges of the input graph are partitioned (randomly, or in an arbitrary, but balanced, fashion) among the k machines. For problems such as connectivity and MST, the above bound is (essentially) the best possible (up to logarithmic factors). Our simulation technique allows us to obtain the first known efficient deterministic algorithms in the k-machine model for other problems with known deterministic PRAM algorithms.

Abstract

Motivated by recent progress on symmetry breaking problems such as maximal independent set (MIS) and maximal matching in the low-memory Massively Parallel Computation (MPC) model (e.g., Behnezhad et al.~PODC 2019; Ghaffari-Uitto SODA 2019), we investigate the complexity of ruling set problems in this model. The MPC model has become very popular as a model for large-scale distributed computing and it comes with the constraint that the memory-per-machine is strongly sublinear in the input size. For graph problems, extremely fast MPC algorithms have been designed assuming Ω~(n) memory-per-machine, where n is the number of nodes in the graph (e.g., the O(loglogn) MIS algorithm of Ghaffari et al., PODC 2018). However, it has proven much more difficult to design fast MPC algorithms for graph problems in the low-memory MPC model, where the memory-per-machine is restricted to being strongly sublinear in the number of nodes, i.e., $O(n^eps)$ for $0 < eps < 1$. In this paper, we present an algorithm for the 2-ruling set problem, running in O~(log1/6Δ) rounds whp, in the low-memory MPC model. We then extend this result to β-ruling sets for any integer β>1. Specifically, we show that a β-ruling set can be computed in the low-memory MPC model with $O(n^eps)$ memory-per-machine in O~(β⋅log1/(2β+1−2)Δ) rounds, whp. From this it immediately follows that a β-ruling set for β=Ω(logloglogΔ)-ruling set can be computed in in just O(βloglogn) rounds whp. The above results assume a total memory of $tilde{O}(m + n^{1+eps})$. We also present algorithms for β-ruling sets in the low-memory MPC model assuming that the total memory over all machines is restricted to O~(m).

Abstract

Finding the centrality measures of nodes in a graph is a problem of fundamental importance due to various applications from social networks, biological networks, and transportation networks. Given the large size of such graphs, it is natural to use parallelism as a recourse. There have been several studies that show how to compute the various centrality measures of nodes in a graph on parallel architectures, including multi-core systems and GPUs. However, as these graphs evolve and change, it is pertinent to study how to update the centrality measures on changes to the underlying graph. In this paper, we show novel parallel algorithms for updating the betweenness- and closeness-centrality values of nodes in a dynamic graph. Our algorithms process a batch of updates in parallel by extending the approach of handling a single update for etweennessand closeness-centrality by Jamour et al. [16] and Sarıyüce et al. [27], respectively. Besides, our algorithms incorporate mechanisms to exploit the structural properties of graphs for enhanced performance.