Group buying offers products at significantly reduced prices on the condition that a pre-specified number of buyers would make the purchase. Given the ever-increasing popularity of mobile devices and applications coupled with the typically high price-sensitivity of a significant percentage of users, group buying in mobile environments has the potential to attain dramatically increasing popularity. However, existing solutions for group buying typically involve web-based portals, which are not capable of handling user mobility. Hence, this work proposes an end-to-end mobile group-buying system that can be used for targeted decentralized advertisement and discovery of group buying deals, and group formation to avail a deal. The key contributions are three-fold. First, it proposes an ILP (Integer Linear Programming)-based optimal algorithm for the problem of efficiently forming groups of buyers with the objective of maximizing the overall utility of the solution. Second, it proposes a greedy algorithm for the same problem since solving ILP can take significant time for some problem instances. The greedy algorithm takes an input parameter, which can be tweaked to trade-off its optimality with its running time. Third, performance study shows that the proposed algorithms exhibit good performance in terms of the number of groups formed w.r.t. The requests in the system. Notably, the greedy algorithm provides near-optimal solution and runs significantly faster than the ILP-based optimal algorithm.

We consider the problem of fair resource allocation for tasks where a resource can be assigned to at most one task, without any fractional allocation. The system is heterogeneous: capacity and cost may vary across resources, and different tasks may have different resource demand. Due to heterogeneity of resources, the cost of allocating a task in isolation, without any other competing task, may differ significantly from its allocation cost when the task is allocated along with other tasks. In this context, we consider the problem of allocating resource to tasks, while ensuring that the cost is distributed fairly across the tasks, namely, the ratio of allocation cost of a task to its isolation cost is minimized over all tasks. We show that this fair resource allocation problem is strongly NP-Hard even when the resources are of unit size by a reduction from 3-partition. Our central results are an LP rounding based algorithm with an approximation ratio of 2+ O(ϵ) for the problem when resources are of unit size, and a near-optimal greedy algorithm for a more restricted version. The above fair allocation problem arises for resource allocation in various context, such as, allocating computing resources for reservations requests from tenants in a data centre, allocating resources to computing tasks in grid computing, or allocating personnel for tasks in service delivery organizations.

Information about resident involvement in reporting various city-related events (e.g., Potholes, traffic jams) via mobile apps is critical to key stakeholders for effective city management. While existing efforts have primarily focused on event data collection in space, they are not capable of performing efficient retrieval of information about resident involvement in event reporting across different spatial regions and at different spatial granularities. Hence, this work makes the following contributions. First, we present CRIS, a scalable system for efficient retrieval of resident involvement and event information across different spatial regions and at varying spatial granularities. Second, we propose the euR-tree, a novel R-tree-based index augmented with (a) a hash-based array for indexing events in space, and (b) fixed-length arrays for indexing resident involvement information in reporting events in space. The euR-tree is integrated into CRIS to realize efficient retrieval. Third, our performance study indicates that the euR-tree is indeed effective in performing such retrieval with reduced query response times and disk I/Os.

Awareness of dynamically changing road conditions is crucial for a safe and quality driving experience, as well as, in augmenting trip planning. This work addresses the problem of keeping users informed in a timely and personalized manner about road conditions arising from both scheduled and ad hoc events. We propose Road Eye, a system for personalized retrieval of dynamic road conditions. The key contribution of Road Eye is the psi R-tree, which is a novel R-tree-based index augmented with linked lists for facilitating quick and personalized retrieval of user-queried road conditions. Our performance study indicates that the psi R-tree is indeed effective in retrieving dynamic road conditions with reduced query response times and disk I/Os.

A detailed examination of evolving traffic characteristics, operator requirements, and network technology trends suggests a move away from nonblocking interconnects in data center networks (DCNs). As a result, recent efforts have advocated oversubscribed networks with the capability to adapt to traffic requirements on-demand. In this paper, we present the design, implementation, and evaluation of OSA, a novel Optical Switching Architecture for DCNs. Leveraging runtime reconfigurable optical devices, OSA dynamically changes its topology and link capacities, thereby achieving unprecedented flexibility to adapt to dynamic traffic patterns. Extensive analytical simulations using both real and synthetic traffic patterns demonstrate that OSA can deliver high bisection bandwidth (60%-100% of the nonblocking architecture). Implementation and evaluation of a small-scale functional prototype further demonstrate the feasibility of OSA.

Full-bandwidth connectivity between all servers of a data center may be necessary for all-to-all traffic patterns, but such interconnects suffer from high cost, complexity, and energy consumption. Recent work has argued that if all-to-all traffic is uncommon, oversubscribed network architectures that can adapt the topology to meet traffic demands, are sufficient. In line with this work, we propose Proteus, an all-optical architecture targeting unprecedented topology-flexibility, lower complexity and higher energy efficiency.

Abstract Development of distributed systems is a difficult task. Declarative programming techniques hold a promising potential for effectively supporting programmer in this challenge. While Datalog-based languages have been actively explored for programming distributed systems, Prolog received relatively little attention in this application area so far. In this paper we present a Prolog-based programming system, called DAHL, for the declarative development of distributed systems. DAHL extends Prolog with an event-driven control mechanism and built-in networking procedures. Our experimental evaluation using a distributed hash-table data structure, a protocol for achieving Byzantine fault tolerance, and a distributed software model checker—all implemented in DAHL—indicates the viability of the approach.

Clustering involves arranging a P2P overlay network's topology so that peers having certain characteristics are grouped together as neighbors. Clustering can be used to organize a P2P overlay network so that requests are routed more efficiently. The peers lack of a global awareness of the overlay network's topology in a P2P network makes it difficult to develop algorithms for clustering peers. This paper presents two decentralized algorithms for clustering peers. The algorithms are concrete realizations of of an algorithm called the abstract Schelling's algorithm (based on a model from sociology by Thomas Schelling) that can be used to create a family of self-* topology adaptation algorithms for P2P overlay networks. The proposed clustering algorithms are easy to implement, are not designed for clustering on a specific criteria and do not require separate algorithms to handle the flux of peers on the overlay network. The paper presents simulation results for applying the algorithm on random small-world topologies.

Distributed systems are hard to build, profile, debug, and test. Monitoring a distributed system - to detect and analyze bugs, test for regressions, identify fault-tolerance problems or security compromises - can be difficult and error-prone. In this paper we argue that declarative development of distributed systems is well suited to tackle these tasks. We present an application logging, monitoring, and debugging facility that we have built on top of the P2 system, comprising an introspection model, an execution tracing component, and a distributed query processor. We use this facility to demonstrate a range of on-line distributed diagnosis tools that range from simple, local state assertions to sophisticated global property detectors on consistent snapshots. These tools are small, simple, and can be deployed piecemeal on-line at any point during a system's life cycle. Our evaluation suggests that the overhead of our approach to improving and monitoring running distributed systems continuously is well in tune with its benefits.

Abstract — Overlay networks are widely used to deploy functionality at edge nodes without changing network routers. Each node in an overlay network maintains connections with a number of peers, forming a graph upon which a distributed application or service is implemented. In an “Eclipse ” attack, a set of malicious, colluding overlay nodes arranges for a correct node to peer only with members of the coalition. If successful, the attacker can mediate most or all communication to and from the victim. Furthermore, by supplying biased neighbor information during normal overlay maintenance, a modest number of malicious nodes can eclipse a large number of correct victim nodes. This paper studies the impact of Eclipse attacks on structured overlays and shows the limitations of known defenses. We then present the design, implementation, and evaluation of a new defense, in which nodes anonymously audit each other’s connectivity. The key observation is that a node that mounts an Eclipse attack must have a higher than average node degree. We show that enforcing a node degree limit by auditing is an effective defense against Eclipse attacks. Furthermore, unlike most existing defenses, our defense leaves flexibility in the selection of neighboring nodes, thus permitting important overlay optimizations like proximity neighbor selection (PNS). I.

In tree-based multicast systems, a relatively small number of interior nodes carry the load of forwarding multicast messages. This works well when the interior nodes are highly-available, dedicated infrastructure routers but it poses a problem for application-level multicast in peer-to-peer systems. SplitStream addresses this problem by striping the content across a forest of interior-node-disjoint multicast trees that distributes the forwarding load among all participating peers. For example, it is possible to construct efficient SplitStream forests in which each peer contributes only as much forwarding bandwidth as it receives. Furthermore, with appropriate content encodings, SplitStream is highly robust to failures because a node failure causes the loss of a single stripe on average. We present the design and implementation of SplitStream and show experimental results obtained on an Internet testbed and via large-scale network simulation. The results show that SplitStream distributes the forwarding load among all peers and can accommodate peers with different bandwidth capacities while imposing low overhead for forest construction and maintenance.