RNRakesh Nagi

Rakesh Nagi

*This is an algorithmically generated author record based on publicly available information.

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


Rakesh Nagi has a total of 56 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Cloud-native Workflow Scheduling using a Hybrid Priority Rule, Dynamic Resource Allocation, and Dynamic Task Partition

    by Jungeun Shin, Diana Arroyo, Asser Tantawi, Chen Wang, Alaa Youssef, Rakesh Nagi

    As cloud-native workflow orchestration tools become increasingly important for complex data science workloads, there is a growing need for more efficient scheduling. Existing cloud schedulers rely on basic heuristics and user choice for task partitioning for parallel computing, leading to under-utilization of cluster resources and prolonged job completion times. To address this, we propose a novel workflow scheduling algorithm that leverages workflow characteristics to enhance resource utilization and reduce weighted job completion time. The algorithm combines three sub-algorithms, each reflecting a distinct aspect of the scheduling strategy: 1) Hybrid Maximum Children (MC) -Weighted Shortest Critical Path Time (WSCPT) rule alternates between two heuristics, MC and WSCPT, which prioritize jobs based on workflow structure and critical path, respectively. The choice between these heuristics is dynamically adjusted according to the cluster queue size. 2) Dynamic Resource Allocation (DRA), which dynamically adjusts the number of executors assigned to each workflow, and 3) Dynamic Task Partition (DTP), which autonomously determines the task parallelism level. We tested our algorithm with extensive experiments on various workflow types using Spark-imitated simulation. Our algorithm outperformed other schedulers, including learning-based models, by reducing 21-47% of the combined performance of average job completion time and makespan for unweighted workflows and reducing at least 50% of weighted job completion time for weighted workflows.


  • Open Access

    Robust Task Allocations by Distributing the Risk Among Agents: Theory and Algorithms

    by Raunak Sengupta, Rakesh Nagi, Ramavarapu S. Sreenivas

    We address the problem of generating robust solutions for the makespan minimization problem on identical agents (parallel machines), under the assumption that only interval bounds of processing times are known. While there are various concepts of robustness in the literature, we prove using pathological examples that any of these criteria may result in allocations with undesirable characteristics. We identify key properties that must be satisfied for a solution to be considered truly robust. Given a set of jobs with associated loads and uncertainties, it is shown that an allocation that balances loads and uncertainties simultaneously is extremely robust and satisfies multiple other existing criteria of robustness within an acceptable approximation factor. Thus, robustness is achieved by distributing the uncertainty/risk among the agents along with the load. The problem of finding a robust allocation is reduced to a bi-criteria two-dimensional load balancing problem, with the two dimensions being the load and the uncertainty. We prove that for the case with 2 agents, an allocation that satisfies a 1.5-approximation on both dimensions simultaneously always exists and can be found efficiently, and is also the best possible guarantee. For the general case with any number of agents, we prove that an allocation that satisfies a 2-approximation on one dimension and a 2.5-approximation on the other always exists and can be found in pseudo-polynomial time. The approximation algorithms presented in this paper are complemented by interesting existential and structural results and contribute to the vector scheduling literature for two dimensions as well. Finally, an extensive numerical analysis is presented, where we demonstrate our algorithms’ near-optimal performance and ability to generate allocations that satisfy multiple criteria of robustness simultaneously in a short amount of time. Note to Practitioners —This paper introduces a simple and provably effective methodology for generating robust allocations in the context of the makespan minimization problem, a critical challenge in operational management that significantly impacts the efficiency and productivity of various industries. We demonstrate using counter-examples that traditional concepts of robustness such as worst-case makespan and min-max regret can lead to overly conservative and practically inefficient allocations, even when solved optimally. Following this, it is shown that an allocation that balances loads and uncertainties simultaneously is extremely robust and satisfies multiple other existing criteria of robustness within an acceptable approximation factor. This leads to a more attractive and practical concept of robustness. Efficient, fast, and provably good algorithms are presented that solve a 2D Load Balancing problem and generate allocations that are balanced with respect to both the loads as well as uncertainties for a large percentage of the possible scenarios. Numerical results provide practitioners confidence in our approach. The algorithm further classifies the jobs as critical and non-critical based on their completion times and uncertainties in a way that leads to provably good allocations. This classification can be further used to obtain intuition about the problem, thus providing managerial insights.


  • Open Access

    Limited-Trust in Social Network Games

    by Timothy Murray, Jugal Garg, Rakesh Nagi

    We consider agents in a social network competing to be selected as partners in collaborative, mutually beneficial activities. We study this through a model in which an agent i can initiate a limited number k_i>0 of games and selects the ideal partners from its one-hop neighborhood. On the flip side it can accept as many games offered from its neighbors. Each game signifies a productive joint economic activity, and players attempt to maximize their individual utilities. Unsurprisingly, more trustworthy agents are more desirable as partners. Trustworthiness is measured by the game theoretic concept of Limited-Trust, which quantifies the maximum cost an agent is willing to incur in order to improve the net utility of all agents. Agents learn about their neighbors' trustworthiness through interactions and their behaviors evolve in response. Empirical trials performed on realistic social networks show that when given the option, many agents become highly trustworthy; most or all become highly trustworthy when knowledge of their neighbors' trustworthiness is based on past interactions rather than known a priori. This trustworthiness is not the result of altruism, instead agents are intrinsically motivated to become trustworthy partners by competition. Two insights are presented: first, trustworthy behavior drives an increase in the utility of all agents, where maintaining a relatively modest level of trustworthiness may easily improve net utility by as much as 14.5%. If only one agent exhibits modest trust among self-centered ones, it can increase its average utility by up to 25% in certain cases! Second, and counter-intuitively, when partnership opportunities are abundant agents become less trustworthy.


  • Special issue in memory of Dr. Jean-Marie Proth (7.12.1938–17.06.2021)

    by Chengbin Chu, Feng Chu, Alexandre Dolgui, Rakesh Nagi, Xiaolan Xie


  • Determining optimal channel partition for 2:4 fine grained structured sparsity

    by Mohit Mahajan, Wen-Mei Hwu, Rakesh Nagi


  • Open Access

    Parallelizing Maximal Clique Enumeration on GPUs

    by Mohammad Almasri, Yen-Hsiang Chang, Izzat El Hajj, Rakesh Nagi, Jinjun Xiong, Wen-Mei Hwu

    We present a GPU solution for exact maximal clique enumeration (MCE) that performs a search tree traversal following the Bron-Kerbosch algorithm. Prior works on parallelizing MCE on GPUs perform a breadth-first traversal of the tree, which has limited scalability because of the explosion in the number of tree nodes at deep levels. We propose to parallelize MCE on GPUs by performing depth-first traversal of independent subtrees in parallel. Since MCE suffers from high load imbalance and memory capacity requirements, we propose a worker list for dynamic load balancing, as well as partial induced subgraphs and a compact representation of excluded vertex sets to regulate memory consumption. Our evaluation shows that our GPU implementation on a single GPU outperforms the state-of-the-art parallel CPU implementation by a geometric mean of 4.9x (up to 16.7x), and scales efficiently to multiple GPUs. Our code has been open-sourced to enable further research on accelerating MCE.


  • Limited-Trust in Diffusion of Competing Alternatives Over Social Networks

    by Vincent Leon, S. Rasoul Etesami, Rakesh Nagi

    We consider the diffusion of two alternatives in social networks using a game-theoretic approach. Each individual plays a coordination game with its neighbors repeatedly and decides which to adopt. As products are used in conjunction with others and through repeated interactions, individuals are more interested in their long-term benefits and tend to show trust to others to maximize their long-term utility by choosing a suboptimal option with respect to instantaneous payoff. To capture such trust behavior, we deploy limited-trust equilibrium (LTE) in diffusion process. We analyze the convergence of emerging dynamics to equilibrium points using mean-field approximation and study the equilibrium state and the convergence rate of diffusion using absorption probability and expected absorption time of a reduced-size absorbing Markov chain. We also show that the diffusion model on LTE under the best-response strategy can be converted to the well-known linear threshold model. Simulation results show that when agents behave trustworthy, their long-term utility will increase significantly compared to the case when they are solely self-interested. Moreover, the Markov chain analysis provides a good estimate of convergence properties over random networks.


  • Open Access

    BEEP: Balanced Efficient subgraph Enumeration in Parallel

    by Samiran Kawtikwar, Mohammad Almasri, Wen-Mei Hwu, Rakesh Nagi, Jinjun Xiong