Source author record

Saad Quader

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

3works
7topics
2close collaborators

Published work

3 publications

preprint2020arXiv

Consistency of Proof-of-Stake Blockchains with Concurrent Honest Slot Leaders

We improve the fundamental security threshold of eventual consensus Proof-of-Stake (PoS) blockchain protocols under the longest-chain rule by showing, for the first time, the positive effect of rounds with concurrent honest leaders. Current security analyses reduce consistency to the dynamics of an abstract, round-based block creation process that is determined by three events associated with a round: (i) event AA: at least one adversarial leader, (ii) event SS: a single honest leader, and (iii) event MM: multiple, but honest, leaders. We present an asymptotically optimal consistency analysis assuming that an honest round is more likely than an adversarial round (i.e., Pr⁡[S]+Pr⁡[M]>Pr⁡[A]\Pr[S] + \Pr[M] > \Pr[A]); this threshold is optimal. This is a first in the literature and can be applied to both the simple synchronous communication as well as communication with bounded delays. In all existing consistency analyses, event MM is either penalized or treated neutrally. Specifically, the consistency analyses in Ouroboros Praos (Eurocrypt 2018) and Genesis (CCS 2018) assume that Pr⁡[S]−Pr⁡[M]>Pr⁡[A]\Pr[S] - \Pr[M] > \Pr[A]; the analyses in Sleepy Consensus (Asiacrypt 2017) and Snow White (Fin. Crypto 2019) assume that Pr⁡[S]>Pr⁡[A]\Pr[S] > \Pr[A]. Moreover, all existing analyses completely break down when Pr⁡[S]<Pr⁡[A]\Pr[S] < \Pr[A]. These thresholds determine the critical trade-off between the honest majority, network delays, and consistency error. Our new results can be directly applied to improve the security guarantees of the existing protocols. We also provide an efficient algorithm to explicitly calculate these error probabilities in the synchronous setting. Furthermore, we complement these results by analyzing the setting where SS is rare, even allowing Pr⁡[S]=0\Pr[S] = 0, under the added assumption that honest players adopt a consistent chain selection rule.

preprint2014arXiv

A (Somewhat Dated) Comparative Study of Betweenness Centrality Algorithms on GPU

The problem of computing the Betweenness Centrality (BC) is important in analyzing graphs in many practical applications like social networks, biological networks, transportation networks, electrical circuits, etc. Since this problem is computation intensive, researchers have been developing algorithms using high performance computing resources like supercomputers, clusters, and Graphics Processing Units (GPUs). Current GPU algorithms for computing BC employ Brandes' sequential algorithm with different trade-offs for thread scheduling, data structures, and atomic operations. In this paper, we study three GPU algorithms for computing BC of unweighted, directed, scale-free networks. We discuss and measure the trade-offs of their design choices about balanced thread scheduling, atomic operations, synchronizations and latency hiding. Our program is written in NVIDIA CUDA C and was tested on an NVIDIA Tesla M2050 GPU.

preprint2012arXiv

A Beginner's Guide to Counting Spanning Trees in a Graph

(DRAFT VERSION) In this article we present a proof of the famous Kirchoff's Matrix-Tree theorem, which relates the number of spanning trees in a connected graph with the cofactors (and eigenvalues) of its combinatorial Laplacian matrix. This is a 165 year old result in graph theory and the proof is conceptually simple. However, the elegance of this result is it connects many apparently unrelated concepts in linear algebra and graph theory. Our motivation behind this work was to make the proof accessible to anyone with beginner\slash intermediate grasp of linear algebra. Therefore in this paper we present proof of every single argument leading to the final result. For example, we prove the elementary properties of determinants, relationship between the roots of characteristic polynomial (that is, eigenvalues) and the minors, the Cauchy-Binet formula, the Laplace expansion of determinant, etc.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.