Abstract

The use of predefined phrase patterns like: N-grams (N>=2), longest common sub sequences or pre defined linguistic patterns etc do not give any credit to non-matching/smaller-size useful patterns and thus, may result in loss of information. Next, the use of 1-gram based model results in several noisy matches. Additionally, due to presence of more than one topic with different levels of importance in summary, we consider summarization evaluation task as topic based evaluation of information content. Means at first stage, we identify the topics covered in given model/reference summary and calculate their importance. At the next stage, we calculate the information coverage in test / machine generated summary, w.r.t. every identified topic. We introduce a graph based mapping scheme and the concept of closeness centrality measure to calculate the information depth and sense of the co-occurring words in every identified topic. Our experimental results show that devised system is better than/comparable with best results of TAC 2011 AESOP dataset.

Abstract

The problem of Authenticated Byzantine Generals (ABG) aims to simulate a virtual reliable broadcast channel from the General to all the players via a protocol over a real (point-to-point) network in the presence of faults. We propose a new model to study the self-composition of ABG protocols. The central dogma of our approach can be phrased as follows: Consider a player who diligently executes (only) the delegated protocol but the adversary steals some private information from him. Should such a player be considered faulty? With respect to ABG protocols, we argue that the answer has to be no. In the new model we show that in spite of using unique session identifiers, if , there cannot exist any ABG protocol that composes in parallel even twice. Further, for , we design ABG protocols that compose for any number of parallel executions. Besides investigating the composition of ABG under a new light, our work also brings out several new insights into Canetti's Universal Composability framework. Specifically, we show that there are several undesirable effects if one deviates from our dogma. This provides further evidence as to why our dogma is the right framework to study the composition of ABG protocols.

Abstract

Perfectly reliable message transmission (PRMT) is one of the fundamental problems in distributed computing. It allows a sender to reliably transmit a message to a receiver in an unreliable network, even in the presence of a computationally unbounded adversary. In this article, we study the inherent trade-off between the three important parameters of the PRMT protocols, namely, the network connectivity (n), the round complexity (r), and the communication complexity by considering the following generic question (which can be considered as the holy grail problem) in the context of the PRMT protocols. Given an n-connected network, a message of size ℓ (to be reliably communicated) and a limit c for the total communication allowed between the sender and the receiver, what is the minimum number of communication rounds required by a PRMT protocol to send the message, such that the communication complexity of the protocol is O(c)? We answer this interesting question by deriving a nontrivial lower bound on the round complexity. Moreover, we show that the lower bound is tight in the amortized sense, by designing a PRMT protocol whose round complexity matches the lower bound. The lower bound is the first of its kind, that simultaneously captures the inherent tradeoff between the three important parameters of a PRMT protocol.

Abstract

In this work, we study the problem of reporting and counting maximal points in a query rectangle for a set of n integer points that lie on an n×n grid. A point is said to be maximal inside a query rectangle if it is not dominated by any other point inside the query rectangle. Our model of computation is unit-cost RAM model with word size of O(logn) bits. For the reporting version of the problem, we present a data structure of size words and support querying in time where k is the size of the output. For the counting version, we present a data structure of size words which supports querying in . Both the data structures are static in nature. The reporting version of the problem has been studied in [1] and [5]. To the best of our knowledge, this is the first sub-logarithmic result for the reporting version and the first work for the counting version of the problem.

Abstract

We study the problem of secure message transmission (SMT) in asynchronous directed graphs, where an unbounded Byzantine adversary can corrupt some subset of nodes specified via an adversary structure. We focus on the particular variant (0, δ)-SMT, where the message remains perfectly private, but there is a small chance that the receiver R may not obtain it. This variant can be of two kinds: Monte Carlo - where R may output an incorrect message with small probability; and Las Vegas - where R never outputs an incorrect message. For a Monte Carlo (0, δ)-SMT protocol to exist in an asynchronous directed graph, we show that the minimum connectivity required in the network does not decrease even when privacy of the message being transmitted is not required. In the case of Las Vegas (0, δ)-SMT, we show that the minimum connectivity required matches exactly with the minimum connectivity requirements of the zero-error variant of SMT – (0, 0)-SMT. For a network that meets the minimum connectivity requirements, we provide a protocol efficient in the size of the graph and the adversary structure. We also provide a protocol efficient in the size of the graph for an important family of graphs, when the adversary structure is threshold.

Abstract

In this paper, we give approximate algorithms for privacy preserving distance based outlier detection for both horizontal and vertical distributions, which scale well to large datasets of high dimensionality in comparison with the existing techniques. In order to achieve efficient private algorithms, we introduce an approximate outlier detection scheme for the centralized setting which is based on the idea of Locality Sensitive Hashing. We also give theoretical and empirical bounds on the level of approximation of the proposed algorithms.

Abstract

We consider AESOP Task as Topic based evaluation of information content. Means at first stage, we identify the topics covered in given model/reference summary and calculate their importance. At the next stage, we calculate the information coverage in test/machine generated summary, wrt every identified topic. We use the local importance of words in calculation of importance of topics. From experiments it is clear that use of different methods for identification of topics and calculation of information coverage in test documents wrt every identified topic, have different effect on the result. It is important to note that our devised system do not require any linguistic support or learning or training in entire execution of the system.

Abstract

In this paper, we give an approximate algorithm for distance based outlier detection using Locality Sensitive Hashing (LSH) technique. We propose an algorithm for the centralized case wherein the entire dataset is locally available for processing. However, in case of very large datasets collected from various input sources, often the data is distributed across the network. Accordingly, we show that our algorithm can be effectively extended to a constant round protocol with low communication costs, in a distributed setting with horizontal partitioning.

Abstract

Three decades ago, Pease et al. introduced the problem of Byzantine Agreement [PSL 80] where nodes need to maintain a consistent view of the world in spite of the challenge posed by Byzantine faults. Subsequently, it is well known that Byzantine agreement over a completely connected synchronous network of n nodes tolerating up to t faults is (efficiently) possible if and only if t < n/3. Pease et al. further empowered the nodes with the ability to authenticate themselves and their messages and proved that agreement in this new model (popularly known as authenticated Byzantine agreement (ABA)) is possible if and only if t < n. (which is a huge improvement over the bound of t < n/3 in the absence of authentication for the same functionality). To understand the utility, potential and limitations of using authentication in distributed protocols for agreement, Gupta et al. [GGBS10] studied ABA in new light. They generalize the existing models and thus, attempt to give a unified theory of agreements over the authenticated and non-authenticated domains. In this paper we extend their results to synchronous (undirected) networks and give a complete characterization of agreement protocols. As a corollary, we show that agreement can be strictly easier than all-pair point-to-point communication. It is well known that in a synchronous network over n nodes of which up to any t are corrupted by a Byzantine adversary, BA is possible only if all pair point-to-point reliable communication is possible [Dol82, DDWY93]. Thus, a folklore in the area is that maintaining global consistency (agreement) is at least as hard as the problem of all pair point-to-point communication. Equivalently, it is widely believed that protocols for BA over incomplete networks exist only if it is possible to simulate an overlay-ed complete network. Surprisingly, we show that the folklore is not always true. Thus, it seems that agreement protocols may be more fundamental to distributed computing than reliable communication.

Abstract

In the Perfectly Secure Message Transmission (PSMT) problem, a sender S and a receiver R are part of a distributed network and connected through node disjoint paths, also called as wires, among which at most wires are controlled by a static, Byzantine adversary , having unbounded computing power. S has a message , which S intends to send to R. The challenge is to design a protocol, such that at the end of the protocol, R should correctly output without any error (perfect reliability) and should not get any information about , whatsoever, in information theoretic sense (perfect security). The problem of Statistically Secure Message Transmission (SSMT) is same as PSMT, except that R should correctly output with very high probability. Sayeed and Abu-Amara (1995) [37] have given a PSMT protocol in an asynchronous network tolerating , where S and R are connected by wires. However, we show that their protocol does not provide perfect security. We then prove that in an asynchronous network, if all the wires are directed from S to R, then any PSMT protocol tolerating is possible iff . Surprisingly, we also prove that even if all the wires are bi-directional, then any PSMT protocol in asynchronous network tolerating is possible iff . This is quite surprising because for synchronous networks, by the results of Dolev et al. (1993) [16], if all the wires are unidirectional (directed from S to R), then PSMT tolerating is possible iff , where as if all the wires are bi-directional then PSMT tolerating is possible iff . This shows that asynchrony of the network demands higher connectivity of the network for the existence of PSMT protocols. Interestingly, we further show that wires are necessary and sufficient for the existence of any SSMT protocol in asynchronous network tolerating , irrespective of whether the wires are unidirectional from S to R or the wires are bi-directional. By the results of Franklin and Wright (2000) [18] and Kurosawa and Suzuki (2009) [22], wires are necessary and sufficient for the existence of SSMT in synchronous networks, irrespective of whether the wires are unidirectional from S to R or the wires are bi-directional. This shows that asynchrony of the network does not demand higher connectivity of the network for SSMT protocols.