The last few years have witnessed a spate of data protection regulations in conjunction with an ever-growing appetite for data usage in large businesses, which presents significant challenges for businesses to maintain compliance. To address this conflict, we present Data Guard - a fine-grained, purpose-based access control system for large data warehouses. Data Guard enables authoring policies based on semantic descriptions of data and purpose of data access. Data Guard then translates these policies into SQL views that mask data from the underlying warehouse tables. At access time, Data Guard ensures compliance by transparently routing each table access to the appropriate data-masking view based on the purpose of the access, thus minimizing the effort of adopting Data Guard in existing applications. Our enforcement solution allows masking data at much finer granularities than what traditional solutions allow. In addition to row and column level data masking, Data Guard can mask data at the sub-cell level for columns with non-atomic data types such as structs, arrays, and maps. This fine-grained masking allows Data Guard to preserve data utility for consumers while ensuring compliance. We implemented a number of performance optimizations to minimize the overhead of data masking operations. We perform numerous experiments to identify the key factors that influence the data masking overhead and demonstrate the efficiency of our implementation. Data Guard is deployed inside LinkedIn's production data warehouses and ensures compliance of more than 20,000 table accesses each day across different data processing engines.

Neighbor discovery is a fundamental problem in wireless networks. In this paper, we study asynchronous neighbor discovery on duty-cycled mobile devices. Most existing studies develop integer schedules where time proceeds in discrete slots and a node is awake or asleep for an entire slot duration. We show that integer schedules can lead to significant waste of resources, and develop a generalized non-integer model, where time is continuous and a node may become awake or asleep at any point of time (subject to a few constraints) so that the resultant schedules can be significantly more efficient than integer schedules. In addition, we provide a reduction that transforms any schedule in the integer model to a corresponding schedule in the generalized non-integer model while reducing the discovery latency by up to a factor of two. Applying this reduction, an optimal schedule in the integer model becomes an optimal schedule in the non-integer model. We further demonstrate the practicality of non-integer schedules in a testbed, and compare the worst-case discovery latency of several existing schemes under both integer and non-integer models. Last, we establish a family of lower bounds for the best achievable latency guarantee. These lower bounds are applicable to both integer and non-integer models, covering both symmetric and asymmetric settings, and encompassing the existing lower bounds that are only for a subset of settings as special cases.

Neighbor discovery is a fundamental problem in wireless networks. In this paper, we study asynchronous neighbor discovery between duty-cycled mobile devices. Each node is duty-cycled, i.e., its radio may only be active for a small fraction of the time. The duty cycles of the nodes can be the same or different, leading to symmetric or asymmetric cases of the neighbor discovery problem. In addition, the setting is asynchronous, i.e., clocks of different nodes may not be synchronized. Most existing studies assume an integer model (where time proceeds in discrete steps); two recent studies break away from this assumption, which allows them to develop significantly more efficient schemes. Our study improves the state-of-the-art in three main fronts. Firstly, we develop a generalized non-integer model (where time is continuous) that permits unified treatment of the assumptions in existing studies. We also provide a reduction that transforms any schedule in the basic integer model to a corresponding schedule in the generalized non-integer model while improving the performance by a factor of two. Applying this reduction, an optimal schedule in the integer model becomes an optimal schedule in the non-integer model. Thirdly, we establish a new family of lower bounds for the best achievable latency guarantee in the non-integer model. They are applicable to both symmetric and asymmetric settings, and encompass the lower bounds for the integer model as special cases. Finally, we develop a novel optimal construction based on Sidon sets for the symmetric setting. Our approach differs from the approaches taken by all existing studies, and provides a new direction for constructing neighbor discovery schedules.

We present an argument in favor of forming coalitions of peers in a data swarming system consisting of peers with heterogeneous upload capacities. In this paper, a coalition refers to a set of peers that explicitly cooperate with other peers inside the coalition via choking, piece selection, and capacity allocation strategies. Furthermore, each peer in a coalition exchanges data with peers outside its coalition via distinct choking, piece selection, and capacity allocation strategies. We first propose a simple Random Choking strategy for peers inside a coalition and develop an analytical model for studying its performance. Our model accurately predicts a coalition's performance and shows that the proposed strategy helps a coalition achieve near-optimal performance. Furthermore, our model can be easily adapted to model a BitTorrent-like swarm. We show that our Random Choking strategy significantly outperforms Tit-for-Tat and Unchoke-All strategies proposed in prior work. We also introduce a simple piece selection strategy, which significantly improves data availability within a coalition as compared to Rarest-First strategy employed in BitTorrent systems. Using cooperative game theory, we prove the existence of stable coalitions when peer population is fixed and each peer has complete information of other peers' actions and payoffs. When peers are allowed to freely join or leave coalitions, we propose a Cooperation-Aware Better Response strategy that achieves convergence of the dynamic coalition formation process. Finally, using extensive simulations, we demonstrate that forming coalitions results in significant improvements in the overall performance of a data swarm.

Neighbor discovery is one of the first steps in configuring and managing a wireless network. Most existing studies on neighbor discovery assume a single-packet reception model where only a single packet can be received successfully at a receiver. In this paper, motivated by the increasing prevalence of multipacket reception (MPR) technologies such as CDMA and MIMO, we study neighbor discovery in MPR networks that allow packets from multiple simultaneous transmitters to be received successfully at a receiver. Starting with a clique of n nodes, we first analyze a simple Aloha-like algorithm and show that it takes Θ((n ln n)/k) time to discover all neighbors with high probability when allowing up to k simultaneous transmissions. We then design two adaptive neighbor discovery algorithms that dynamically adjust the transmission probability for each node. We show that the adaptive algorithms yield a Θ(ln n) improvement over the Aloha-like scheme for a clique with n nodes and are thus order-optimal. Finally, we analyze our algorithms in a general multi-hop network setting. We show an upper bound of O((Δ ln n)/k) for the Aloha-like algorithm when the maximum node degree is Δ, which is at most a factor ln n worse than the optimal. In addition, when Δ is large, we show that the adaptive algorithms are orderoptimal, i.e., have a running time of O(Δ/k) which matches the lower bound for the problem.

Neighbor discovery is an important first step in the initialization of a wireless ad hoc network. In this paper, we design and analyze several algorithms for neighbor discovery in wireless networks. Starting with a single-hop wireless network ofnnodes, we propose a Θ(nlnn) ALOHA-like neighbor discovery algorithm when nodes cannot detect collisions, and an order-optimal Θ(n) receiver feedback-based algorithm when nodes can detect collisions. Our algorithms neither require nodes to have a priori estimates of the number of neighbors nor synchronization between nodes. Our algorithms allow nodes to begin execution at different time instants and to terminate neighbor discovery upon discovering all their neighbors. We finally show that receiver feedback can be used to achieve a Θ(n) running time, even when nodes cannot detect collisions. We then analyze neighbor discovery in a general multihop setting. We establish an upper bound ofO(Δlnn) on the running time of the ALOHA-like algorithm, where Δ denotes the maximum node degree in the network andnthe total number of nodes. We also establish a lower bound of Ω(Δ+lnn) on the running time of any randomized neighbor discovery algorithm. Our result thus implies that the ALOHA-like algorithm is at most a factor min(Δ,lnn) worse than optimal.

We design and analyze a mechanism for forming coalitions of peers in a data swarming system where peers have heterogeneous upload capacities. A coalition is a set of peers that explicitly cooperate with other peers inside the coalition via choking, data replication, and capacity allocation strategies. Further, each peer interacts with other peers outside its coalition via potentially distinct choking, data replication, and capacity allocation strategies. Following on our preliminary work in [14] that demonstrated significant performance benefits of coalitions, we present here a comprehensive analysis of the choking strategy for coalitions. We first develop an analytical model to understand a simple random choking strategy as a within-coalition strategy and show that it accurately predicts a coalition's performance. Our model shows that the random choking strategy can help a coalition achieve near-optimal performance by optimally choosing the re-choking interval lengths and the number of unchoke slots. Further, our analytical model can be easily adapted to model a BitTorrent-like swarm. Using extensive simulations, we demonstrate improvements in the performance of a swarming system due to coalition formation.

We present an argument in favor of forming coalitions of peers in a data swarming system consisting of peers with different upload capacities. A coalition is a set of peers with the same upload capacity that explicitly cooperate with other peers inside the coalition via choking and capacity allocation strategies. Further, each peer interacts with other peers outside its coalition via potentially distinct choking and capacity allocation strategies. This paper focuses on the efficiency of different choking strategies, assuming that peers do not share data with other peers outside their coalitions. We first develop an analytical model that accurately predicts the performance of a coalition of peers adopting BitTorrent's Tit-for-Tat choking strategy. Our model highlights a number of inefficiencies of Tit-for-Tat strategy. Accordingly, we propose a random choking strategy, and show that it can help a coalition achieve near-optimal performance and it significantly outperforms not only Tit-for-Tat strategy but also unchoke-all strategy. Using cooperative game theory, we prove the existence of stable coalitions, and demonstrate the convergence of the dynamic coalition formation process when peers use our cooperation-aware better response strategy. Using extensive simulations, we demonstrate significant performance benefits due to coalition formation.

Neighbor discovery is one of the first steps in configuring and managing a wireless network. Most existing studies on neighbor discovery assume a single-packet reception model where only a single packet can be received successfully at a receiver. In this paper, motivated by the increasing prevalence of multipacket reception (MPR) technologies such as CDMA and MIMO, we study neighbor discovery in MPR networks that allow multiple packets to be received successfully at a receiver. More specifically, we design and analyze a series of randomized algorithms for neighbor discovery in MPR networks. We start with a simple Aloha-like algorithm that assumes synchronous node transmissions and the number of neighbors, n, is known. We show that the time for all the nodes to discover their respective neighbors is Θ(ln n) in an idealized MPR network that allows an arbitrary number of nodes to transmit simultaneously. In a more realistic scenario, in which no more than k nodes can transmit simultaneously, we show that the time to discover all neighbors is Θ(n ln n/k). When a node knows whether its transmission is successful or not (e.g., based on feedbacks from other nodes), we design an adaptive Aloha-like algorithm that dynamically determines the transmission probability for each node, and show that it yields a ln n improvement over the simple Aloha-like scheme. Last, we extend our schemes to take into account a number of practical considerations, such as lack of knowledge of the number of neighbors and asynchronous algorithm operation, while resulting in only a constant or log n factor slowdown in algorithm performance.

The secure transmission of information in wireless networks without knowledge of eavesdropper channels or locations is considered. Two key mechanisms are employed: artificial noise generation from system nodes other than the transmitter and receiver, and a form of multi-user diversity that allows message reception in the presence of the artificial noise. We determine the maximum number of independently-operating and uniformly distributed eavesdroppers that can be present while the desired secrecy is achieved with high probability in the limit of a large number of system nodes. While our main motivation is considering eavesdroppers of unknown location, we first consider the case where the path-loss is identical between all pairs of nodes. In this case, a number of eavesdroppers that is exponential in the number of systems nodes can be tolerated. In the case of uniformly distributed eavesdroppers of unknown location, any number of eavesdroppers whose growth is sub-linear in the number of system nodes can be tolerated. The proposed approach significantly outperforms a power control approach based on standard multi-user diversity.

We investigate the scalability of a class of algorithms that exploit the dynamics of wireless fading channels to achieve secret communication in a large wireless network of n randomly located nodes. We describe a construction in which nodes transmit artificial noise to suppress eavesdroppers whose locations are unknown and ensure secrecy of messages transported across the network. Under a model in which eavesdroppers operate independently and under appropriate conditions on the achievable per-node throughput Ψ(n), we show that the network can tolerate Ω((1⁄√n(n))2c) eavesdroppers while ensuring that the aggregate rate at which eavesdroppers intercept packets goes to 0, where c is a constant such that 0 0. We also establish sufficient conditions on the number of eavesdroppers to achieve a non-zero throughput in our construction.

Neighbor discovery is one of the first steps in the initialization of a wireless ad hoc network. In this paper, we design and analyze practical algorithms for neighbor discovery in wireless networks. We first consider an ALOHA-like neighbor discovery algorithm in a synchronous system, proposed in an earlier work. When nodes do not have a collision detection mechanism, we show that this algorithm reduces to the classical {\em Coupon Collector's Problem}. Consequently, we show that each node discovers all its $n$ neighbors in an expected time equal to $ne (\ln n + c)$, for some constant $c$. When nodes have a collision detection mechanism, we propose an algorithm based on receiver status feedback which yields a $\ln n$ improvement over the ALOHA-like algorithm. Our algorithms do not require nodes to have any estimate of the number of neighbors. In particular, we show that not knowing $n$ results in no more than a factor of two slowdown in the algorithm performance. In the absence of node synchronization, we develop asynchronous neighbor discovery algorithms that are only a factor of two slower than their synchronous counterparts. We show that our algorithms can achieve neighbor discovery despite allowing nodes to begin execution at different time instants. Furthermore, our algorithms allow each node to detect when to terminate the neighbor discovery phase.

2517-2527

We consider the problem of neighbor discovery in static wireless ad hoc networks with directional antennas. We propose several probabilistic algorithms in which nodes perform random, independent transmissions to discover their one-hop neighbors. Our neighbor discovery algorithms are classified into two groups, viz. Direct-Discovery Algorithms in which nodes discover their neighbors only upon receiving a transmission from their neighbors and Gossip-based algorithms in which nodes gossip about their neighbors' location information to enable faster discovery. We first consider the operation of these algorithms in a slotted, synchronous system and mathematically derive their optimal parameter settings. We show how to extend these algorithms for an asynchronous system and describe their optimal design. Analysis and simulation of the algorithms show that nodes discover their neighbors much faster using gossip-based algorithms than using direct-discovery algorithms. Furthermore, the performance of gossip-based algorithms is insensitive to an increase in node density. The efficiency of a neighbor discovery algorithm also depends on the choice of antenna beamwidth. We discuss in detail how the choice of beamwidth impacts the performance of the discovery process and provide insights into how nodes can configure their beamwidths.

Leader election is a very important problem, not only in wired networks, but in mobile, ad hoc networks as well. Existing solutions to leader election do not handle frequent topology changes and dynamic nature of mobile networks. We present a leader election algorithm that is highly adaptive to arbitrary (possibly concurrent) topological changes and is therefore well-suited for use in mobile ad hoc networks. The algorithm is based on finding an extrema and uses diffusing computations for this purpose. We show, using linear-time temporal logic, that the algorithm is "weakly" self-stabilizing and terminating. We also simulate the algorithm in a mobile ad hoc setting. Through our simulation study, we elaborate on several important issues that can significantly impact performance of such a protocol for mobile ad hoc networks such as choice of signaling, broadcast nature of wireless medium etc. Our simulation study shows that our algorithm is quite effective in that each node has a leader approximately 97-99% of the time in a variety of operating conditions.