Costas Busch
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Costas Busch has a total of 48 co-authors. Here are the top co-authors by number of shared publications:
- Ramesh Adhikari
Augusta University
10 shared publications - Dariusz Rafal Kowalski
Augusta University
9 shared publications - Gokarna Sharma
Louisiana State University
7 shared publications - Gokarna Sharma
Kent State University, Kent, USA
6 shared publications - Miroslav Popovic
Faculty of Technical Sciences, University of Novi Sad
6 shared publications - Pavan Poudel
University of Houston-Clear Lake
4 shared publications
Latest Publications
- Open Access
- 6 November 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
On the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding
We consider blockchain sharding where n processing nodes are divided into s disjoint groups (shards) that can process transactions in parallel. We study dynamic scheduling problems on a shard graph G s where transactions arrive online over time and are not known in advance. Each transaction may access at most k shards, and we denote by d the worst distance between a transaction and its accessing shards. To handle different values of d , we assume a locality sensitive decomposition of G s into clusters of shards, where every cluster has a leader shard that schedules transactions for the cluster. We first examine the simpler case of the stateless model , where leaders are not aware of the current state of the transaction accounts, and we prove a \(O(d \log ^2 s \cdot \min \lbrace k, \sqrt {s}\rbrace) \) competitive ratio for latency. We then consider the stateful model , where leader shards gather the current state of accounts, and we prove a \(O(\log s\cdot \min \lbrace k, \sqrt {s}\rbrace +\log ^2 s) \) competitive ratio for latency. We show that for any ϵ > 0, approximating the optimal schedule within a \((\min \lbrace k, \sqrt {s}\rbrace)^{1 -\epsilon } \) factor is NP-hard. Hence, our bound for the stateful model is within a poly-log factor from the best possibly achievable. We also provide the simulation results of the proposed scheduling algorithms.- 6 November 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
Open AccessOn the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding
We consider blockchain sharding where n processing nodes are divided into s disjoint groups (shards) that can process transactions in parallel. We study dynamic scheduling problems on a shard graph G s where transactions arrive online over time and are not known in advance. Each transaction may access at most k shards, and we denote by d the worst distance between a transaction and its accessing shards. To handle different values of d , we assume a locality sensitive decomposition of G s into clusters of shards, where every cluster has a leader shard that schedules transactions for the cluster. We first examine the simpler case of the stateless model , where leaders are not aware of the current state of the transaction accounts, and we prove a \(O(d \log ^2 s \cdot \min \lbrace k, \sqrt {s}\rbrace) \) competitive ratio for latency. We then consider the stateful model , where leader shards gather the current state of accounts, and we prove a \(O(\log s\cdot \min \lbrace k, \sqrt {s}\rbrace +\log ^2 s) \) competitive ratio for latency. We show that for any ϵ > 0, approximating the optimal schedule within a \((\min \lbrace k, \sqrt {s}\rbrace)^{1 -\epsilon } \) factor is NP-hard. Hence, our bound for the stateful model is within a poly-log factor from the best possibly achievable. We also provide the simulation results of the proposed scheduling algorithms. - Open Access
- 19 November 2025
- Published by Association for Computing Machinery (ACM) in Distributed Ledger Technologies: Research and Practice
- Vol. 6 (1) , 1-25
Transaction Processing in Blockchain Sharding: Current Trends and Future Research Directions
Blockchain is known for its promising features, such as decentralization, fault tolerance, transparency, and immutability. Thus, it has been used in many industries and applications, including cryptocurrency, finance, smart cities, healthcare, and manufacturing. However, blockchain suffers from scalability issues and provides low transaction throughput and high latency. Sharding is used to solve these scalability and performance issues by dividing the blockchain network into smaller clusters of nodes called shards, and each shard processes transactions in parallel. However, the sharding protocol is still in its early stages and encounters multiple challenges. In this paper, we survey cutting-edge blockchain sharding papers, mainly focusing on transaction processing aspects such as intra-shard transaction processing, cross-shard communication, and cross-shard transaction processing. We also examine security vulnerabilities and attack vectors associated with sharded blockchain systems . We review existing techniques, highlight key challenges and problems, and suggest potential future research directions.
- 19 November 2025
- Published by Association for Computing Machinery (ACM) in Distributed Ledger Technologies: Research and Practice
- Vol. 6 (1) , 1-25
Open AccessTransaction Processing in Blockchain Sharding: Current Trends and Future Research Directions
Blockchain is known for its promising features, such as decentralization, fault tolerance, transparency, and immutability. Thus, it has been used in many industries and applications, including cryptocurrency, finance, smart cities, healthcare, and manufacturing. However, blockchain suffers from scalability issues and provides low transaction throughput and high latency. Sharding is used to solve these scalability and performance issues by dividing the blockchain network into smaller clusters of nodes called shards, and each shard processes transactions in parallel. However, the sharding protocol is still in its early stages and encounters multiple challenges. In this paper, we survey cutting-edge blockchain sharding papers, mainly focusing on transaction processing aspects such as intra-shard transaction processing, cross-shard communication, and cross-shard transaction processing. We also examine security vulnerabilities and attack vectors associated with sharded blockchain systems . We review existing techniques, highlight key challenges and problems, and suggest potential future research directions.
- 18 November 2025
- Published by Springer Nature
- p. 4-20
Near-Optimal Stability for Distributed Transaction Processing in Blockchain Sharding
- 18 November 2025
- Published by Springer Nature
- p. 4-20
Near-Optimal Stability for Distributed Transaction Processing in Blockchain Sharding
- 18 November 2025
- Published by Springer Nature
- p. 21-39
A Poly-log Approximation for Transaction Scheduling in Fog-Cloud Computing and Beyond
- 18 November 2025
- Published by Springer Nature
- p. 21-39
A Poly-log Approximation for Transaction Scheduling in Fog-Cloud Computing and Beyond
- Open Access
Near-Optimal Stability for Distributed Transaction Processing in Blockchain Sharding
In blockchain sharding, $n$ processing nodes are divided into $s$ shards, and each shard processes transactions in parallel. A key challenge in such a system is to ensure system stability for any ``tractable'' pattern of generated transactions; this is modeled by an adversary generating transactions with a certain rate of at most $ρ$ and burstiness $b$. This model captures worst-case scenarios and even some attacks on transactions' processing, e.g., DoS. A stable system ensures bounded transaction queue sizes and bounded transaction latency. It is known that the absolute upper bound on the maximum injection rate for which any scheduler could guarantee bounded queues and latency of transactions is $\max\left\{ \frac{2}{k+1}, \frac{2}{ \left\lfloor\sqrt{2s}\right\rfloor}\right\}$, where $k$ is the maximum number of shards that each transaction accesses. Here, we first provide a single leader scheduler that guarantees stability under injection rate $ρ\leq \max\left\{ \frac{1}{16k}, \frac{1}{16\lceil \sqrt{s} \rceil}\right\}$. Moreover, we also give a distributed scheduler with multiple leaders that guarantees stability under injection rate $ρ\leq \frac{1}{16c_1 \log D \log s}\max\left\{ \frac{1}{k}, \frac{1}{\lceil \sqrt{s} \rceil} \right\}$, where $c_1$ is some positive constant and $D$ is the diameter of shard graph $G_s$. This bound is within a poly-log factor from the optimal injection rate, and significantly improves the best previous known result for the distributed setting by Adhikari et al., SPAA 2024.Open AccessNear-Optimal Stability for Distributed Transaction Processing in Blockchain Sharding
In blockchain sharding, $n$ processing nodes are divided into $s$ shards, and each shard processes transactions in parallel. A key challenge in such a system is to ensure system stability for any ``tractable'' pattern of generated transactions; this is modeled by an adversary generating transactions with a certain rate of at most $ρ$ and burstiness $b$. This model captures worst-case scenarios and even some attacks on transactions' processing, e.g., DoS. A stable system ensures bounded transaction queue sizes and bounded transaction latency. It is known that the absolute upper bound on the maximum injection rate for which any scheduler could guarantee bounded queues and latency of transactions is $\max\left\{ \frac{2}{k+1}, \frac{2}{ \left\lfloor\sqrt{2s}\right\rfloor}\right\}$, where $k$ is the maximum number of shards that each transaction accesses. Here, we first provide a single leader scheduler that guarantees stability under injection rate $ρ\leq \max\left\{ \frac{1}{16k}, \frac{1}{16\lceil \sqrt{s} \rceil}\right\}$. Moreover, we also give a distributed scheduler with multiple leaders that guarantees stability under injection rate $ρ\leq \frac{1}{16c_1 \log D \log s}\max\left\{ \frac{1}{k}, \frac{1}{\lceil \sqrt{s} \rceil} \right\}$, where $c_1$ is some positive constant and $D$ is the diameter of shard graph $G_s$. This bound is within a poly-log factor from the optimal injection rate, and significantly improves the best previous known result for the distributed setting by Adhikari et al., SPAA 2024. - Open Access
On the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding
Sharding is a technique to speed up transaction processing in blockchains, where the $n$ processing nodes in the blockchain are divided into $s$ disjoint groups (shards) that can process transactions in parallel. We study dynamic scheduling problems on a shard graph $G_s$ where transactions arrive online over time and are not known in advance. Each transaction may access at most $k$ shards, and we denote by $d$ the worst distance between a transaction and its accessing (destination) shards (the parameter $d$ is unknown to the shards). To handle different values of $d$, we assume a locality sensitive decomposition of $G_s$ into clusters of shards, where every cluster has a leader shard that schedules transactions for the cluster. We first examine the simpler case of the stateless model, where leaders are not aware of the current state of the transaction accounts, and we prove a $O(d \log^2 s \cdot \min\{k, \sqrt{s}\})$ competitive ratio for latency. We then consider the stateful model, where leader shards gather the current state of accounts, and we prove a $O(\log s\cdot \min\{k, \sqrt{s}\}+\log^2 s)$ competitive ratio for latency. Each leader calculates the schedule in polynomial time for each transaction that it processes. We show that for any $ε> 0$, approximating the optimal schedule within a $(\min\{k, \sqrt{s}\})^{1 -ε}$ factor is NP-hard. Hence, our bound for the stateful model is within a poly-log factor from the best possibly achievable. To the best of our knowledge, this is the first work to establish provably efficient dynamic scheduling algorithms for blockchain sharding systems.Open AccessOn the Efficiency of Dynamic Transaction Scheduling in Blockchain Sharding
Sharding is a technique to speed up transaction processing in blockchains, where the $n$ processing nodes in the blockchain are divided into $s$ disjoint groups (shards) that can process transactions in parallel. We study dynamic scheduling problems on a shard graph $G_s$ where transactions arrive online over time and are not known in advance. Each transaction may access at most $k$ shards, and we denote by $d$ the worst distance between a transaction and its accessing (destination) shards (the parameter $d$ is unknown to the shards). To handle different values of $d$, we assume a locality sensitive decomposition of $G_s$ into clusters of shards, where every cluster has a leader shard that schedules transactions for the cluster. We first examine the simpler case of the stateless model, where leaders are not aware of the current state of the transaction accounts, and we prove a $O(d \log^2 s \cdot \min\{k, \sqrt{s}\})$ competitive ratio for latency. We then consider the stateful model, where leader shards gather the current state of accounts, and we prove a $O(\log s\cdot \min\{k, \sqrt{s}\}+\log^2 s)$ competitive ratio for latency. Each leader calculates the schedule in polynomial time for each transaction that it processes. We show that for any $ε> 0$, approximating the optimal schedule within a $(\min\{k, \sqrt{s}\})^{1 -ε}$ factor is NP-hard. Hence, our bound for the stateful model is within a poly-log factor from the best possibly achievable. To the best of our knowledge, this is the first work to establish provably efficient dynamic scheduling algorithms for blockchain sharding systems. - Open Access
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 451-461
Stable Blockchain Sharding under Adversarial Transaction Generation
Sharding is used to improve the scalability and performance of blockchain systems. We investigate the stability of blockchain sharding, where transactions are continuously generated by an adversarial model. The system consists of n processing nodes that are divided into s shards. Following the paradigm of classical adversarial queuing theory, transactions are continuously received at injection rate ρ ≤ 1 and burstiness b > 0. We give an absolute upper bound max{2/k+1, 2⌊√2s⌋} on the maximum injection rate for which any scheduler could guarantee bounded queues and latency of transactions, where k is the number of shards that each transaction accesses. We next give a basic distributed scheduling algorithm for uniform systems where shards are equally close to each other. To guarantee stability, the injection rate is limited to ρ ≤ max{1/18k, 1/ ⌈18√s⌉}. We then provide a fully distributed scheduling algorithm for non-uniform systems where shards are arbitrarily far from each other. By using a hierarchical clustering of the shards, stability is guaranteed with injection rate ρ ≤ 1/(c1d log2 s) ⋅ max{1/k, 1/√s}, where d is the worst distance of any transaction to the shards it will access, and c1 is some positive constant. We also conduct simulations to evaluate the algorithms and measure the average queue sizes and latency throughout the system. To our knowledge, this is the first adversarial stability analysis of sharded blockchain systems.
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 451-461
Open AccessStable Blockchain Sharding under Adversarial Transaction Generation
Sharding is used to improve the scalability and performance of blockchain systems. We investigate the stability of blockchain sharding, where transactions are continuously generated by an adversarial model. The system consists of n processing nodes that are divided into s shards. Following the paradigm of classical adversarial queuing theory, transactions are continuously received at injection rate ρ ≤ 1 and burstiness b > 0. We give an absolute upper bound max{2/k+1, 2⌊√2s⌋} on the maximum injection rate for which any scheduler could guarantee bounded queues and latency of transactions, where k is the number of shards that each transaction accesses. We next give a basic distributed scheduling algorithm for uniform systems where shards are equally close to each other. To guarantee stability, the injection rate is limited to ρ ≤ max{1/18k, 1/ ⌈18√s⌉}. We then provide a fully distributed scheduling algorithm for non-uniform systems where shards are arbitrarily far from each other. By using a hierarchical clustering of the shards, stability is guaranteed with injection rate ρ ≤ 1/(c1d log2 s) ⋅ max{1/k, 1/√s}, where d is the worst distance of any transaction to the shards it will access, and c1 is some positive constant. We also conduct simulations to evaluate the algorithms and measure the average queue sizes and latency throughout the system. To our knowledge, this is the first adversarial stability analysis of sharded blockchain systems.
- Open Access
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 383-393
Sparse Spanners with Small Distance and Congestion Stretches
Given a graph G, a classical problem in graph theory is the construction of a spanner H -- a sparse subgraph of G that closely approximates the distances between nodes in G. The distance stretch~α of H is the factor of how much the distances in H increase versus G. Here, we consider sparse spanner constructions that can also preserve the node congestion of routing problems in G. The congestion stretch β of H is the factor of how much the (smallest) congestion of a routing problem increases in H versus G. We introduce the notion of (α, β)-DC-spanner (i.e., a Distance-Congestion-spanner) that simultaneously controls the stretches for distance and congestion. We show that for expander graphs with n nodes, there is a (3, O(log n))-DC-spanner with O(n5/3) edges. We also examine Δ-regular graphs with Δ ≥ n2/3, where we show how to obtain a (3, O(√Δ ⋅ log n))-DC-spanner with O(n5/3 log2n) edges. Finally, we show that there is a graph such that any optimal size 3-distance spanner has Ω(n7/6) edges and is a (3, Ω(n1/6))-DC-spanner.
- 17 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 383-393
Open AccessSparse Spanners with Small Distance and Congestion Stretches
Given a graph G, a classical problem in graph theory is the construction of a spanner H -- a sparse subgraph of G that closely approximates the distances between nodes in G. The distance stretch~α of H is the factor of how much the distances in H increase versus G. Here, we consider sparse spanner constructions that can also preserve the node congestion of routing problems in G. The congestion stretch β of H is the factor of how much the (smallest) congestion of a routing problem increases in H versus G. We introduce the notion of (α, β)-DC-spanner (i.e., a Distance-Congestion-spanner) that simultaneously controls the stretches for distance and congestion. We show that for expander graphs with n nodes, there is a (3, O(log n))-DC-spanner with O(n5/3) edges. We also examine Δ-regular graphs with Δ ≥ n2/3, where we show how to obtain a (3, O(√Δ ⋅ log n))-DC-spanner with O(n5/3 log2n) edges. Finally, we show that there is a graph such that any optimal size 3-distance spanner has Ω(n7/6) edges and is a (3, Ω(n1/6))-DC-spanner.
- 23 May 2024
- Published by Springer Nature
- p. 262-280
Locally Balanced Allocations Under Strong Byzantine Influence
- 23 May 2024
- Published by Springer Nature
- p. 262-280
Locally Balanced Allocations Under Strong Byzantine Influence
- 23 April 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 72 (9) , 5924-5940
Novel Graph-Theoretical Multiple Access-Point/Router Deployment Approach for Full Line-of-Sight Coverage Over Arbitrary Indoor Polygonal/Prismatic Areas
Nowadays, wireless local-area networks (WLANs) are widely deployed in residential and commercial areas. The coverage quality is essential to users. The full coverage appears to be one of the most crucial problems to be considered during the network and access-point/router deployment (placement). We formulate the light-of-sight (LoS) coverage problem using the visibility-graph framework. In this work, for arbitrary multiply-connected or simply-connected polygonal/prismatic fields-of-interest subject to an arbitrary link-range restriction, we investigate how the full LoS coverage can be achieved by a minimum number of access-points/routers. Based on the new mathematical lemmas we derive, we design a novel graph-theoretical approach accordingly. Our proposed new scheme can be deemed the first-ever systematic approach to the best of our knowledge. Our proposed new approach is also evaluated in terms of the coverage efficiency, the number of access-points/routers, and the peak link-distance ratio for full LoS coverage in comparison with the existing solution to the art gallery problem.
- 23 April 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 72 (9) , 5924-5940
Novel Graph-Theoretical Multiple Access-Point/Router Deployment Approach for Full Line-of-Sight Coverage Over Arbitrary Indoor Polygonal/Prismatic Areas
Nowadays, wireless local-area networks (WLANs) are widely deployed in residential and commercial areas. The coverage quality is essential to users. The full coverage appears to be one of the most crucial problems to be considered during the network and access-point/router deployment (placement). We formulate the light-of-sight (LoS) coverage problem using the visibility-graph framework. In this work, for arbitrary multiply-connected or simply-connected polygonal/prismatic fields-of-interest subject to an arbitrary link-range restriction, we investigate how the full LoS coverage can be achieved by a minimum number of access-points/routers. Based on the new mathematical lemmas we derive, we design a novel graph-theoretical approach accordingly. Our proposed new scheme can be deemed the first-ever systematic approach to the best of our knowledge. Our proposed new approach is also evaluated in terms of the coverage efficiency, the number of access-points/routers, and the peak link-distance ratio for full LoS coverage in comparison with the existing solution to the art gallery problem.