BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Rakesh Mohanty

Rakesh Mohanty appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsOperating SystemsComputational ComplexityCryptography and SecurityDiscrete Mathematics

Catalog footprint

What is connected

19works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

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.

Published work

19 published item(s)

preprint2022arXiv

A Note on Hardness of Multiprocessor Scheduling with Scheduling Solution Space Tree

We study the computational complexity of the non-preemptive scheduling problem of a list of independent jobs on a set of identical parallel processors with a makespan minimization objective. We make a maiden attempt to explore the combinatorial structure showing the exhaustive solution space of the problem by defining the \textit{Scheduling Solution Space Tree (SSST)} data structure. The properties of the \textit{SSST} are formally defined and characterized through our analytical results. We develop a unique technique to show the problem $\mathcal{NP}$ using the SSST and the \textit{Weighted Scheduling Solution Space Tree (WSSST)} data structures. We design the first non-deterministic polynomial-time algorithm named \textit{Magic Scheduling (MS)} for the problem based on the reduction framework. We also define a new variant of multiprocessor scheduling by including the user as an additional input parameter. We formally establish the complexity class of the variant by the reduction principle. Finally, we conclude the article by exploring several interesting open problems for future research investigation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A 2-Competitive Largest Job on Least Loaded Machine Online Algorithm based on Multi Lists Scheduling Model

Online scheduling in identical machines with makespan minimization has been a well studied research problem in the literature. In online scheduling, the scheduler receives a list of jobs one by one and assigns each incoming job on the fly irrevocably to one of the machines before the arrival of the next job. In this paper, we study a variant of the online scheduling problem, where jobs are requested on the fly from k distinct sources. On simultaneous arrival of jobs from multiple sources, it is a non-trivial research challenge to ensure fairness in scheduling with respect to distinct sources, while optimizing the overall makespan of the schedule. We develop a novel Multi Lists Scheduling Model(MLS) and propose a 2-competitive deterministic online algorithm namely Largest Job on Least Loaded Machine(LJLLM) based on the MLS model to address the above mentioned research challenge.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A New Fairness Model based on User's Objective for Multi-user Multi-processor Online Scheduling

Resources of a multi-user system in multi-processor online scheduling are shared by competing users in which fairness is a major performance criterion for resource allocation. Fairness ensures equality in resource sharing among the users. According to our knowledge, fairness based on the user's objective has neither been comprehensively studied nor a formal fairness model has been well defined in the literature. This motivates us to explore and define a new model to ensure algorithmic fairness with quantitative performance measures based on optimization of the user's objective. In this paper, we propose a new model for fairness in Multi-user Multi-processor Online Scheduling Problem(MUMPOSP). We introduce and formally define quantitative fairness measures based on user's objective by optimizing makespan for individual user in our proposed fairness model. We also define the unfairness of deprived users and absolute fairness of an algorithm. We obtain lower bound results for the absolute fairness for m identical machines with equal length jobs. We show that our proposed fairness model can serve as a framework for measuring algorithmic fairness by considering various optimality criteria such as flow time and sum of completion times.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Online Scheduling with Makespan Minimization: State of the Art Results, Research Challenges and Open Problems

Online scheduling has been a well studied and challenging research problem over the last five decades since the pioneering work of Graham with immense practical significance in various applications such as interactive parallel processing, routing in communication networks, distributed data management, client-server communications, traffic management in transportation, industrial manufacturing and production. In this problem, a sequence of jobs is received one by one in order by the scheduler for scheduling over a number of machines. On arrival of a job, the scheduler assigns the job irrevocably to a machine before the availability of the next job with an objective to minimize the completion time of the scheduled jobs. This paper highlights the state of the art contributions for online scheduling of a sequence of independent jobs on identical and uniform related machines with a special focus on preemptive and non-preemptive processing formats by considering makespan minimization as the optimality criterion. We present the fundamental aspects of online scheduling from a beginner's perspective along with a background of general scheduling framework. Important competitive analysis results obtained by well-known deterministic and randomized online scheduling algorithms in the literature are presented along with research challenges and open problems. Two of the emerging recent trends such as resource augmentation and semi-online scheduling are discussed as a motivation for future research work.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Semi-online Scheduling: A Survey

In online scheduling, jobs are available one by one and each job must be scheduled irrevocably before the availability of the next job. Semi-online scheduling is a relaxed variant of online scheduling, where an additional memory in terms of buffer or an Extra Piece of Information(EPI) is provided along with input data. The EPI may include one or more of the parameter(s) such as size of the largest job, total size of all jobs, arrival sequence of the jobs, optimum makespan value or range of job's processing time. A semi-online scheduling algorithm was first introduced in 1997 by Kellerer et al. They envisioned semi-online scheduling as a practically significant model and obtained improved results for $2$-identical machine setting. This paper surveys scholarly contributions in the design of semi-online scheduling algorithms in parallel machine models such as identical and uniformly related by considering job's processing formats such as preemptive and non-preemptive with the optimality criteria such as Min-Max and Max-Min. The main focus is to present state of the art competitive analysis results of well-known semi-online scheduling algorithms in a chronological overview. The survey first introduces the online and semi-online algorithmic frameworks for the multi-processor scheduling problem with important applications and research motivation, followed by a taxonomy for semi-online scheduling. Fifteen well-known semi-online scheduling algorithms are stated. Important competitive analysis results are presented in a chronological way by highlighting the critical ideas and intuition behind the results. An evolution time-line of semi-online scheduling setups and a classification of the references based on EPI are outlined. Finally, the survey concludes with the exploration of some of the interesting research challenges and open problems.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

New Competitive Analysis Results of Online List Scheduling Algorithm

Online algorithm has been an emerging area of interest for researchers in various domains of computer science. The online $m$-machine list scheduling problem introduced by Graham has gained theoretical as well as practical significance in the development of competitive analysis as a performance measure for online algorithms. In this paper, we study and explore the performance of Graham's online \textit{list scheduling algorithm(LSA)} for independent jobs. In the literature, \textit{LSA} has already been proved to be $2-\frac{1}{m}$ competitive, where $m$ is the number of machines. We present two new upper bound results on competitive analysis of \textit{LSA}. We obtain upper bounds on the competitive ratio of $2-\frac{2}{m}$ and $2-\frac{m^2-m+1}{m^2}$ respectively for practically significant two special classes of input job sequences. Our analytical results can motivate the practitioners to design improved competitive online algorithms for the $m$-machine list scheduling problem by characterization of real life input sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Online Rainbow Coloring In Graphs

Rainbow coloring is a special case of edge coloring, where there must be at least one path between every distinct pair of vertices that consists of different color edges. Here, we may use the same color for the adjacent edges of a graph representing two different paths from a single vertex. In online rainbow coloring, we have no priori knowledge about the vertices and edges of the graph, in fact the edges are available one by one. We have to color an edge as soon as it arrives and before the arrival of the next edge. We can not revoke the coloring decision once it is made. According to our knowledge, there is no study of online rainbow coloring for graphs. In this paper, we make a first attempt to propose an online algorithm named Least Recently Used Color(LRUC) for online rainbow coloring. We analyze the performance of LRUC through competitive analysis. We show that LRUC is optimal for line graph, tree and star graph. For 1-cyclic graph, LRUC is shown to be (2-2/n)-competitive, where n>3. We obtain the competitive ratios of (n-1)/3 and n-1 for wheel and complete graphs respectively, where n is the number of vertices.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Experimental Study of A Novel Variant of Fiduccia Mattheyses(FM) Partitioning Algorithm

Partitioning is a well studied research problem in the area of VLSI physical design automation. In this problem, input is an integrated circuit and output is a set of almost equal disjoint blocks. The main objective of partitioning is to assign the components of circuit to blocks in order to minimize the numbers of inter-block connections. A partitioning algorithm using hypergraph was proposed by Fiduccia and Mattheyses with linear time complexity which has been popularly known as FM algorithm. Most of the hypergraph based partitioning algorithms proposed in the literature are variants of FM algorithm. In this paper, we have proposed a novel variant of FM algorithm by using pair wise swapping technique. We have performed a comparative experimental study of FM algorithm and our proposed algorithm using two dataset such as ISPD98 and ISPD99. Experimental results show that performance of our proposed algorithm is better than the FM algorithm using the above dataset.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

TRANS outperforms MTF for two special types of request sequences without locality of reference

Various list accessing algorithms have been proposed in the literature and their performances have been analyzed theoretically and experimentally. Move-To-Front (MTF) and Transpose (TRANS) are two well known primitive list accessing algorithms. MTF has been proved to be the best performing online algorithm till date in the literature for real life inputs and practical applications with locality of reference. It has been shown that when storage space is extremely limited and pointers for lists cannot be used, then array implementation of TRANS gives efficient reorganization. Use of MTF is extensive in the literature whereas, the use of TRANS is rare. As mentioned as an open problem in literature, direct bounds on the behavior and performance of various list accessing algorithms are needed to allow realistic comparisons. Since it has been shown that no single optimal permutation algorithm exists, it becomes necessary to characterize the circumstances that indicate the advantage in using a particular list accessing algorithm. Motivated by above challenging research issue, in this paper we have made an analytical study for evaluating the performance of TRANS list accessing algorithm using two special types of request sequences without locality of reference. We have compared the performance of TRANS with MTF and observed that TRANS outperforms MTF for these considered types of request sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Performance Evaluation of A Proposed Variant of Frequency Count (VFC) List Accessing Algorithm

Frequency Count (FC) algorithm is considered as the static optimal algorithm for the list accessing problem. In this paper, we have made a study of FC algorithm and explore its limitation. Using the concept of weak look ahead, we have proposed a novel Variant of Frequency Count (VFC) list accessing algorithm. We have evaluated the performance of FC and our proposed VFC algorithm experimentally using input data set from Calgary Corpus. Our experiments show that for all request sequences and list generated from the above data set VFC performs better than FC.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Some Novel Results From Analysis of Move To Front (MTF) List Accessing Algorithm

List accessing problem has been studied as a problem of significant theoretical and practical interest in the context of linear search. Various list accessing algorithms have been proposed in the literature and their performances have been analyzed theoretically and experimentally. Move-To-Front(MTF),Transpose (TRANS) and Frequency Count (FC) are the three primitive and widely used list accessing algorithms. Most of the other list accessing algorithms are the variants of these three algorithms. As mentioned in the literature as an open problem, direct bounds on the behavior and performance of these list accessing algorithms are needed to allow realistic comparisons. MTF has been proved to be the best performing online algorithm till date in the literature for real life inputs with locality of reference. Motivated by the above challenging research issue, in this paper, we have generated four types of input request sequences corresponding to real life inputs without locality of reference. Using these types of request sequences, we have made an analytical study for evaluating the performance of MTF list accessing algorithm to obtain some novel and interesting theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A New Proposed Cost Model for List Accessing Problem using Buffering

There are many existing well known cost models for the list accessing problem. The standard cost model developed by Sleator and Tarjan is most widely used. In this paper, we have made a comprehensive study of the existing cost models and proposed a new cost model for the list accessing problem. In our proposed cost model, for calculating the processing cost of request sequence using a singly linked list, we consider the access cost, matching cost and replacement cost. The cost of processing a request sequence is the sum of access cost, matching cost and replacement cost. We have proposed a novel method for processing the request sequence which does not consider the rearrangement of the list and uses the concept of buffering, matching, look ahead and flag bit.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A New Proposed Dynamic Quantum with Re-Adjusted Round Robin Scheduling Algorithm and Its Performance Analysis

Scheduling is the central concept used frequently in Operating System. It helps in choosing the processes for execution. Round Robin (RR) is one of the most widely used CPU scheduling algorithm. But, its performance degrades with respect to context switching, which is an overhead and it occurs during each scheduling. Overall performance of the system depends on choice of an optimal time quantum, so that context switching can be reduced. In this paper, we have proposed a new variant of RR scheduling algorithm, known as Dynamic Quantum with Readjusted Round Robin (DQRRR) algorithm. We have experimentally shown that performance of DQRRR is better than RR by reducing number of context switching, average waiting time and average turn around time.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

An Improved Move-To-Front(IMTF) Off-line Algorithm for the List Accessing Problem

For the List Accessing Problem, Move-To-Front(MTF) algorithm has been proved to be the best performing online list accessing algorithm till date in the literature[10]. In this paper, we have made a comprehensive analysis of MTF algorithm and developed an Improved-MTF (IMTF) offline algorithm. We have generated two new types of data set and devise a new method of experimental analysis for our proposed algorithm. Our experimental analysis shows that IMTF is performing better than MTF algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Characterization of Request Sequences for List Accessing Problem and New Theoretical Results for MTF Algorithm

List Accessing Problem is a well studied research problem in the context of linear search. Input to the list accessing problem is an unsorted linear list of distinct elements along with a sequence of requests, where each request is an access operation on an element of the list. A list accessing algorithm reorganizes the list while processing a request sequence on the list in order to minimize the access cost. Move-To-Front algorithm has been proved to be the best performing list accessing online algorithm till date in the literature. Characterization of the input request sequences corresponding to practical real life situations is a big challenge for the list accessing problem. As far as our knowledge is concerned, no characterization for the request sequences has been done in the literature till date for the list accessing problem. In this paper, we have characterized the request sequences for the list accessing problem based on several factors such as size of the list, size of the request sequence, ordering of elements and frequency of occurrence of elements in the request sequence. We have made a comprehensive study of MTF list accessing algorithm and obtained new theoretical results for our characterized special class of request sequences. Our characterization will open up a new direction of research for empirical analysis of list accessing algorithms for real life inputs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Comparative performance analysis of multi dynamic time quantum Round Robin(MDTQRR) algorithm with arrival time

CPU being considered a primary computer resource, its scheduling is central to operating-system design. A thorough performance evaluation of various scheduling algorithms manifests that Round Robin Algorithm is considered as optimal in time shared environment because the static time is equally shared among the processes. We have proposed an efficient technique in the process scheduling algorithm by using dynamic time quantum in Round Robin. Our approach is based on the calculation of time quantum twice in single round robin cycle. Taking into consideration the arrival time, we implement the algorithm. Experimental analysis shows better performance of this improved algorithm over the Round Robin algorithm and the Shortest Remaining Burst Round Robin algorithm. It minimizes the overall number of context switches, average waiting time and average turn-around time. Consequently the throughput and CPU utilization is better.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Design and Performance Evaluation of A New Proposed Fittest Job First Dynamic Round Robin(FJFDRR) Scheduling Algorithm

In this paper, we have proposed a new variant of Round Robin scheduling algorithm by executing the processes according to the new calculated Fit Factor f and using the concept of dynamic time quantum. We have compared the performance of our proposed Fittest Job First Dynamic Round Robin(FJFDRR) algorithm with the Priority Based Static Round Robin(PBSRR) algorithm. Experimental results show that our proposed algorithm performs better than PBSRR in terms of reducing the number of context switches, average waiting time and average turnaround time.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Priority Based Dynamic Round Robin (PBDRR) Algorithm with Intelligent Time Slice for Soft Real Time Systems

In this paper, a new variant of Round Robin (RR) algorithm is proposed which is suitable for soft real time systems. RR algorithm performs optimally in timeshared systems, but it is not suitable for soft real time systems. Because it gives more number of context switches, larger waiting time and larger response time. We have proposed a novel algorithm, known as Priority Based Dynamic Round Robin Algorithm(PBDRR),which calculates intelligent time slice for individual processes and changes after every round of execution. The proposed scheduling algorithm is developed by taking dynamic time quantum concept into account. Our experimental results show that our proposed algorithm performs better than algorithm in [8] in terms of reducing the number of context switches, average waiting time and average turnaround time.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A secured Cryptographic Hashing Algorithm

Cryptographic hash functions for calculating the message digest of a message has been in practical use as an effective measure to maintain message integrity since a few decades. This message digest is unique, irreversible and avoids all types of collisions for any given input string. The message digest calculated from this algorithm is propagated in the communication medium along with the original message from the sender side and on the receiver side integrity of the message can be verified by recalculating the message digest of the received message and comparing the two digest values. In this paper we have designed and developed a new algorithm for calculating the message digest of any message and implemented t using a high level programming language. An experimental analysis and comparison with the existing MD5 hashing algorithm, which is predominantly being used as a cryptographic hashing tool, shows this algorithm to provide more randomness and greater strength from intrusion attacks. In this algorithm the plaintext message string is converted into binary string and fragmented into blocks of 128 bits after being padded with user defined padding bits. Then using a pseudo random number generator a key is generated for each block and operated with the respective block by a bitwise operator. This process is terated for the whole message and finally a fixed length message digest is obtained.

0 citations0 reviewsNo code linkedOpen access