Abstract

We consider the problem of probabilistic reliable communication (PRC) over synchronous networks modeled as directed graphs in the presence of a Byzantine adversary when players’ knowledge of the network topology is not complete. We show that possibility of PRC is extremely sensitive to the changes in players’ knowledge of the topology. This is in complete contrast with earlier known results on the possibility of perfectly reliable communication over undirected graphs where the case of each player knowing only its neighbours gives the same result as the case where players have complete knowledge of the network. Specifically, in either case,(2t+ 1)-vertex connectivity is necessary and sufficient, where t is the number of nodes that can be corrupted by the adversary [DDWY93, SKR+05]. We introduce a novel model for quantifying players’ knowledge of network topology, denoted by T K. Given a directed graph G, influenced by a Byzantine adversary that can corrupt up to any t players, we give a necessary and sufficient condition for possibility of PRC over G for any arbitrary topology knowledge T K. It follows from our main characterization theorem that knowledge of up to d=⌊ n− 2t

Abstract

We present a method for finding reduced time coverage paths of multiple UAVs (Unmanned Air Vehicles) monitoring a 3D terrain represented as height fields. A novel metric based on per time visibility is used that couples visibility gained at a terrain point with the time spent to reach the point. This coupled metric is utilized to form reduced time paths by maximizing the visibility gained per unit time at every step. We compare the results of this approach with an approach that covers the terrain based on a per distance visibility metric, which reduces the sum, over distances covered by each UAV path. The comparisons show that the current method gives substantially time reduced paths albeit with an expected increase in sum over distances of UAV paths. We also show that time taken to cover the terrain based on the current metric is far less than prevalent methods that try to decompose the terrain based on visibility followed by time or time followed by visibility in a decoupled fashion. The method is further extended to provide for fault tolerance on a hostile terrain. Each terrain point is guaranteed to be seen by at-least one UAV that has not been damaged due to any calamity, shot or otherwise.

Abstract

We present a method for finding paths for multiple unmanned air vehicles (UAVs) such that the sum over their lengths is minimum as they cover a 3D terrain (represented as height fields). The paths are constrained to lie beneath an exposure surface to ensure stealth from enemy outposts. The exposure surface is also computed as a height field. The algorithm greedily clusters the terrain such that gain in visibility per distance would be higher for intra-cluster points than points across clusters. Paths generated on clusters formed by such a per distance visibility metric are reduced by more than 25% over other related decoupled methods. The method is extended to cover terrains with partial visibilities. The advantage of the coupled metric extends under constrained visibility also. We again show performance gain by comparing with an existing decoupled algorithm that solves a similar problem of minimum distance terrain coverage with constrained visibility. The paper reveals that decomposing the terrain based on visibility first and then distance is always better than the other way round to cover the terrain in shorter distances.

Abstract

The growth of Internet has opened up new avenues for business and corporate model. Information sharing over Internet can help business houses in better cooperative strategic planning and growth. However despite such an impact, business houses are quite reluctant to share information because of the fear of information leakage. In this paper we study and propose an elegant, simple and practical solution for the problem of how can one party avail the data clustering service of another party without affecting each other's privacy. In our solution, we introduce the following two problems: (a) Secure multiparty computation of a depth of a query point, (b) Secure multiparty computation of whether a query point is a hull vertex. To the best of our knowledge this is the first time in literature that the aforementioned problems have been considered in privacy preserving framework.

Abstract

This work deals with the problem of fault-tolerant communication over networks, some of whose nodes are corrupted by a centralized byzantine adversary. The extant literature’s perspective of the problem of reliable communication, especially in networks whose topology is known, is that of a simple problem to which even some naive solutions (like message-flooding etc.) turn out to be reasonably efficient. In this paper, we give an example of a directed graph and a non threshold adversary structure, which will require every protocol for perfect reliable unicast to transmit exponential number of bits in order to reliably transmit a single bit.

Abstract

In the perfectly secure message transmission (PSMT) problem, two synchronized non-faulty players (or processors), the Sender S and the Receiver R are connected by n wires (each of which facilitates 2-way communication); S has a message, represented by a sequence oft elements from a finite field, that he wishes to send to R; after exchanging messages in phases R should correctly obtain S 's message, while an adversary listening on and actively controlling any set of t (or less) wires should have no information about S 's message. Similarly, in the problem of perfect reliable message transmission (PRMT), the receiver R should correctly obtain S's message, in spite of the adversary actively controlling any set oft (or less) wires.

Abstract

Shortest path computation has always been a subject of study and research in the history of computer science. In this paper we introduce and initiate the study of the problem of finding the shortest path in a privacy preserving manner, in presence of single convex polygonal obstacle. We also propose an efficient, elegant and simple solution for the problem.

Abstract

This paper considers the problem of unicasting in wireless ad hoc networks. Unicasting is the problem of finding a route between a source and a destination and forwarding the message from the source to the destination. In theory, models that have been used oversimplify the problem of route discovery in ad hoc networks. The achievement of this paper is threefold. First we use a more general model in which nodes can have different transmission and interference ranges and we present a new routing algorithm for wireless ad hoc networks that has several nice features. We then combine our algorithm with that of known greedy algorithms to arrive at an average case efficient routing algorithm in the situation that GPS information is available. Finally we show how to schedule unicast traffic between a set of source-destination pairs by providing a proper vertex coloring of the nodes in the wireless ad hoc network. Our coloring algorithm achieves a O(Δ)–coloring that is locally distinct within the 2-hop neighborhood of any node.

Abstract

In this paper, we study the problem of perfectly reliable message transmission(PRMT) and perfectly secure message transmission(PSMT) between a sender S and a receiver R in a synchronous network, where S and R are connected by n vertex disjoint paths called wires, each of which facilitates bidirectional communication. We assume that atmost t of these wires are under the control of adversary. We present two-phase-bit optimal PRMT protocol considering Byzantine adversary as well as mixed adversary. We also present a three phase PRMT protocol which reliably sends a message containing l field elements by overall communicating O(l) field elements. This is a significant improvement over the PRMT protocol proposed in [10] to achieve the same task which takes log(t) phases. We also present a three-phase-bit-optimal PSMT protocol which securely sends a message consisting of t field elements by communicating O(t 2) field elements.

Abstract

We consider the problem of reliable message transmission between two synchronous players connected by n wires, some t< n 2 of which may be faulty. We show how to get reliability “for free”—reliable transmission of b bits involves a total communication of only O (b) bits, when b is large enough. We also construct an efficient Perfectly Secure Message Transmission Protocol.