Source author record

Sunil Shende

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

ResearcherUnclaimed source record

Data Structures and Algorithms Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Search on a Line by Byzantine Robots

We consider the problem of fault-tolerant parallel search on an infinite line by $n$ robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed $1$ and can communicate in wireless mode among themselves. However, among the $n$ robots, there are $f$ robots that exhibit {\em byzantine faults}. A faulty robot can fail to report the target even after reaching it, or it can make malicious claims about having found the target when in fact it has not. Given the presence of such faulty robots, the search for the target can only be concluded when the non-faulty robots have sufficient verification that the target has been found. We aim to design algorithms that minimize the value of $S_d(n,f)$ , the time to find a target at a distance $d$ from the origin by $n$ robots among which $f$ are faulty. We give several different algorithms whose running time depends on the ratio $f/n$ , the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.

preprint2012arXiv

Encoding 2-D Range Maximum Queries

We consider the \emph{two-dimensional range maximum query (2D-RMQ)} problem: given an array $A$ of ordered values, to pre-process it so that we can find the position of the smallest element in the sub-matrix defined by a (user-specified) range of rows and range of columns. We focus on determining the \emph{effective} entropy of 2D-RMQ, i.e., how many bits are needed to encode $A$ so that 2D-RMQ queries can be answered \emph{without} access to $A$ . We give tight upper and lower bounds on the expected effective entropy for the case when $A$ contains independent identically-distributed random values, and new upper and lower bounds for arbitrary $A$ , for the case when $A$ contains few rows. The latter results improve upon previous upper and lower bounds by Brodal et al. (ESA 2010). In some cases we also give data structures whose space usage is close to the effective entropy and answer 2D-RMQ queries rapidly.

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.