Peer-to-peer (P2P) streaming has recently received much research attention, with successful commercial systems showing its viability in the Internet. Despite the remarkable popularity in real-world systems, the fundamental properties and limitations are not yet well understood from a theoretical perspective, as there exists a significant gap between the fundamental limits and the performance achieved in practice. In this thesis, we seek to provide an in-depth analytical understanding of fundamental properties and limitations of P2P streaming systems, with a particular spotlight on the performance gap. We first identify the major problem in existing streaming protocols and show that this problem accounts for most of the gap separating the actual and optimal performances of the streaming systems. We then propose a remedy based on network coding to address this problem and show that the gap to the fundamental limits can be significantly reduced.

The growth of wireless telecommunications has stipulated the interest for anywhere-anytime computing. The synergy between networking and mobility will engender new collaborative applications with mobile devices on heterogeneous platforms. One such middleware is “SYSTEM ON MOBILE DEVICES”, SYD developed by the Yamacraw Embedded Systems research team. This type of middleware is an opening step towards Peer-to-Peer mobile networks. This project envisioned collaborative applications among mobile devices and PDAs were used as servers. This thesis studies various existing architectures in mobile computing and their scalability issues. We also proposed new scalable flexible thick client proxy system FTCPS, an architecture suitable for mobile Peer-to-Peer networks. Our empirical study showed that FTCPS has low response time compared to other architectures.

Peer-to-peer (P2P) streaming has recently received much research attention, with successful commercial systems showing its viability in the Internet. Despite the remarkable popularity in real-world systems, the fundamental properties and limitations are not yet well understood from a theoretical perspective, as there exists a significant gap between the fundamental limits and the performance achieved in practice. In this thesis, we seek to provide an in-depth analytical understanding of fundamental properties and limitations of P2P streaming systems, with a particular spotlight on the performance gap. We first identify the major problem in existing streaming protocols and show that this problem accounts for most of the gap separating the actual and optimal performances of the streaming systems. We then propose a remedy based on network coding to address this problem and show that the gap to the fundamental limits can be significantly reduced.

No description available.

En el artículo "NP-completeness in Hedonic Games", identificamos algunas limitaciones significativas de los modelos estándar de juegos cooperativos: A menudo, es imposible alcanzar una organización estable de una sociedad en una cantidad de tiempo razonable. Las implicaciones básicas de estos resultados son las siguientes, Primero, desde un punto de vista positivo, las sociedades están "condenadas" a evolucionar constantemente, más que a alcanzar un estadio de equilibrio en el corto plazo. Segundo, desde una perspectiva normativa, un hipotético organizador de la sociedad debería tomar en consideración las limitaciones prácticas de tiempo a la hora de implementar un orden social estable.Para obtener nuestros resultados, utilizamos el concepto de NP-completitud, que es un modelo bien establecido de complejidad temporal en Ciencias de la Computación. En concreto, nos concentramos en estabilidad grupal y estabilidad individual en juegos hedónicos. Los juegos hedónicos son una clase simple de juegos cooperativos en los que la utilidad de cada individuo viene totalmente determinada por el grupo laboral al que pertenece. Nuestros resultados referentes a la complejidad, expresados en términos de NP-completitud, cubren un amplio espectro de dominios de las preferencias individuales, incluyendo preferencias estrictas, indiferencias en las preferencias o preferencias libres sobre el tamaño de los grupos. Dichos resultados también se cumplen si nos restringimos al caso en el que el tamaño máximo de los grupos es pequeño (dos o tres jugadores)En el artículo "Who is Who in Networks. Wanted: The Key Player" (junto con Antoni Calvó Armengol e Yves Zenou), analizamos un modelo de efectos de grupo en el que los agentes interactúan en un juego de influencias bilaterales. Los juegos no cooperativos con población finita y utilidades linales-cuadráticas, en los cuales cada jugador decide cuánto esfuerzo ejercer, pueden ser interpretados como juegos en red con complementariedades en los pagos, junto con un componente de susitucion global y uniforme, y un efecto de concavidad propia.Para dichos juegos, la acción de cada jugador en un equilibrio de Nash es proporcional a su centralidad de Bonacich en la red de complementariedades, estableciendo así un puente con la literatura de redes sociales. Dicho vínculo entre Bonacich y Nash implica que el equilibrio agregado aumenta con el tamaño y la densidad de la red. También analizamos una política que consiste en seleccionar al jugador clave, ésto es, el jugador que, una vez eliminado del juego, induce un cambio óptimo en la actividad agregada. Proveemos una caracterización geométrica del jugador clave, identificada con una medida de inter-centralidad, la cual toma en cuenta tanto la centralidad de cada jugador como su contribución a la centralidad de los otros.En el artículo "Optimal Targets in Peer Networks" (junto con Antoni Calvó Armengol e Yves Zenou), nos centramos en las consecuencias y limitaciones prácticas que se derivan del modelo de decisiones sobre delincuencia. Las principales metas que aborda el trabajo son las siguientes. Primero, la elección se extiende el concepto de delincuente clave en una red al de grupo clave. En dicha situación se trata de seleccionar de modo óptimo al conjunto de delincuentes a eliminar/neutralizar, dadas las restricciones presupuestarias para aplicar medidas. Dicho problema presenta una inherente complejidad computacional que solo puede salvarse mediante el uso de procedimientos aproximados, "voraces" o probabilísticos. Por otro lado, tratamos el problema del delincuente clave en el contexto de redes dinámicas, en las que, inicialmente, los individuos deciden acerca de su futuro como delincuentes o como ciudadanos que obtienen un salario fijo en el mercado. En dicha situación, la elección del delincuente clave es más compleja, ya que el objetivo de disminuir la delincuencia debe tener en cuenta los efectos en cadena que pueda traer consigo la desaparición de uno o varios delincuentes. Por último, estudiamos la complejidad computacional del problema de elección óptima y explotamos la propiedad de submodularidad de la intercentralidad de grupo, lo cual nos permite acotar el error relativo de la aproximación basada en un algoritmo voraz. / The aim of this thesis work is to contribute to the analysis of the interaction of agents in social networks and groups.In the chapter "NP-completeness in Hedonic Games", we identify some significant limitations in standard models of cooperation in games: It is often impossible to achieve a stable organization of a society in a reasonable amount of time. The main implications of these results are the following. First, from a positive point of view, societies are bound to evolve permanently, rather than reach a steady state configuration rapidly. Second, from a normative perspective, a planner should take into account practical time limitations in order to implement a stable social order.In order to obtain our results, we use the notion of NP-completeness, a well-established model of time complexity in Computer Science. In particular, we concentrate on group stability and individual stability in hedonic games. Hedonic games are a simple class of cooperative games in which each individual's utility is entirely determined by her group. Our complexity results, phrased in terms of NP-completeness, cover a wide spectrum of preference domains, including strict preferences, indifference in preferences or undemanding preferences over sizes of groups. They also hold if we restrict the maximum size of groups to be very small (two or three players).The last two chapters deal with the interaction of agents in the social setting. It focuses on games played by agents who interact among them. The actions of each player generate consequences that spread to all other players throughout a complex pattern of bilateral influences. In "Who is Who in Networks. Wanted: The Key Player" (joint with Antoni Calvó-Armengol and Yves Zenou), we analyze a model peer effects where agents interact in a game of bilateral influences. Finite population non-cooperative games with linear-quadratic utilities, where each player decides how much action she exerts, can be interpreted as a network game with local payoff complementarities, together with a globally uniform payoff substitutability component and an own-concavity effect.For these games, the Nash equilibrium action of each player is proportional to her Bonacich centrality in the network of local complementarities, thus establishing a bridge with the sociology literature on social networks. This Bonacich-Nash linkage implies that aggregate equilibrium increases with network size and density. We then analyze a policy that consists in targeting the key player, that is, the player who, once removed, leads to the optimal change in aggregate activity. We provide a geometric characterization of the key player identified with an inter-centrality measure, which takes into account both a player's centrality and her contribution to the centrality of the others.Finally, in the last chapter, "Optimal Targets in Peer Networks" (joint with Antoni Calvó-Armengol and Yves Zenou), we analyze the previous model in depth and study the properties and the applicability of network design policies.In particular, the key group is the optimal choice for a planner who wishes to maximally reduce aggregate activity. We show that this problem is computationally hard and that a simple greedy algorithm used for maximizing submodular set functions can be used to find an approximation. We also endogeneize the participation in the game and describe some of the properties of the key group. The use of greedy heuristics can be extended to other related problems, like the removal or addition of new links in the network.

Peer-to-peer (P2P) has become a modern distributed computing architecture that supports massively large-scale data management and query processing. Complex query operators such as range operator and join operator are needed by various distributed applications, including content distribution, locality-aware services, computing resource sharing, and many others. This dissertation tackles a number of problems related to range and join query processing in P2P systems: fault-tolerant range query processing under structured P2P architecture, distributed range caching under unstructured P2P architecture, and integration of heterogeneous data under unstructured P2P architecture. To support fault-tolerant range query processing so as to provide strong performance guarantees in the presence of network churn, effective replication schemes are developed at either the overlay network level or the query processing level. To facilitate range query processing, a prefetch-based caching approach is proposed to eliminate the performance bottlenecks incurred by those data items that are not well cached in the network. Finally, a purely decentralized partition-based join query operator is devised to realize bandwidth-efficient join query processing under unstructured P2P architecture. Theoretical analysis and experimental simulations demonstrate the effectiveness of the proposed approaches.

Peer-to-peer (P2P) has become a modern distributed computing architecture that supports massively large-scale data management and query processing. Complex query operators such as range operator and join operator are needed by various distributed applications, including content distribution, locality-aware services, computing resource sharing, and many others. This dissertation tackles a number of problems related to range and join query processing in P2P systems: fault-tolerant range query processing under structured P2P architecture, distributed range caching under unstructured P2P architecture, and integration of heterogeneous data under unstructured P2P architecture. To support fault-tolerant range query processing so as to provide strong performance guarantees in the presence of network churn, effective replication schemes are developed at either the overlay network level or the query processing level. To facilitate range query processing, a prefetch-based caching approach is proposed to eliminate the performance bottlenecks incurred by those data items that are not well cached in the network. Finally, a purely decentralized partition-based join query operator is devised to realize bandwidth-efficient join query processing under unstructured P2P architecture. Theoretical analysis and experimental simulations demonstrate the effectiveness of the proposed approaches.

This dissertation presents algorithms for achieving communication in the presence of adversarial attacks in large, decentralized, resource-constrained networks. We consider abstract single-hop communication settings where a set of senders 𝙎 wishes to directly communicate with a set of receivers 𝙍. These results are then extended to provide resource-efficient, multi-hop communication in wireless sensor networks (WSNs), where energy is critically scarce, and peer-to-peer (P2P) networks, where bandwidth and computational power are limited. Our algorithms are provably correct in the face of attacks by a computationally bounded adversary who seeks to disrupt communication between correct participants. The first major result in this dissertation addresses a general scenario involving single-hop communication in a time-slotted network where a single sender in 𝙎 wishes to transmit a message 𝘮 to a single receiver in 𝙍. The two players share a communication channel; however, there exists an adversary who aims to prevent the transmission of 𝘮 by periodically blocking this channel. There are costs to send, receive or block 𝘮 on the channel, and we ask: How much do the two players need to spend relative to the adversary in order to guarantee transmission of the message? This problem abstracts many types of conflict in information networks, and the associated costs represent an expenditure of network resources. We show that it is significantly more costly for the adversary to block 𝘮 than for the two players to achieve communication. Specifically, if the cost to send, receive and block 𝘮 in a slot are fixed constants, and the adversary spends a total of 𝘉 slots to try to block the message, then both the sender and receiver must be active in only O(𝘉ᵠ⁻¹ + 1) slots in expectation to transmit 𝘮, where φ = (1+ √5)/2 is the golden ratio. Surprisingly, this result holds even if (1) the value of 𝘉 is unknown to either player; (2) the adversary knows the algorithms of both players, but not their random bits; and (3) the adversary is able to launch attacks using total knowledge of past actions of both players. Finally, these results are applied to two concrete problems. First, we consider jamming attacks in WSNs and address the fundamental task of propagating 𝘮 from a single device to all others in a WSN in the presence of faults; this is the problem of reliable broadcast. Second, we examine how our algorithms can mitigate application-level distributed denial-of-service attacks in wired client-server scenarios. The second major result deals with a single-hop communication problem where now 𝙎 consists of multiple senders and there is still a single receiver who wishes to obtain a message 𝘮. However, many of the senders (strictly less than half) can be faulty, failing to send 𝘮 or sending incorrect messages. While the majority of the senders possess 𝘮, rather than listening to all of 𝙎 and majority filtering on the received data, we desire an algorithm that allows the single receiver to decide on 𝘮 in a more efficient manner. To investigate this scenario, we define and devise algorithms for a new data streaming problem called the Bad Santa problem which models the selection dilemma faced by the receiver. With our results for the Bad Santa problem, we consider the problem of energy-efficient reliable broadcast. All previous results on reliable broadcast require devices to spend significant time in the energy-expensive receiving state which is a critical problem in WSNs where devices are typically battery powered. In a popular WSN model, we give a reliable broadcast protocol that achieves optimal fault tolerance (i.e., tolerates the maximum number of faults in this WSN model) and improves over previous results by achieving an expected quadratic decrease in the cost to each device. For the case where the number of faults is within a (1-∊)-factor of the optimal fault tolerance, for any constant ∊>0, we give a reliable broadcast protocol that improves further by achieving an expected (roughly) exponential decrease in the cost to each device. The third and final major result of this dissertation addresses single-hop communication where 𝙎 and 𝙍 both consist of multiple peers that need to communicate in an attack-resistant P2P network. There are several analytical results on P2P networks that can tolerate an adversary who controls a large number of peers and uses them to disrupt network functionality. Unfortunately, in such systems, operations such as data retrieval and message sending incur significant communication costs. Here, we employ cryptographic techniques to define two protocols both of which are more efficient than existing solutions. For a network of 𝘯 peers, our first protocol is deterministic with O(log²𝘯) message complexity and our second protocol is randomized with expected O(log 𝘯) message complexity; both improve over all previous results. The hidden constants and setup costs for our protocols are small and no trusted third party is required. Finally, we present an analysis showing that our protocols are practical for deployment under significant churn and adversarial behaviour.

Content distribution is the primary function of the Internet today. Technologies like multicast and peer-to-peer networks hold the potential to serve content to large populations in a scalable manner. While multicast provides an efficient transport mechanism for one-to-many and many-to-many delivery of data in an Internet environment, the peer-to-peer networks allow scalable content location and retrieval among large groups of users in the Internet. Incorporating quality-consciousness in these technologies is necessary to enhance the overall experience of clients. This dissertation focuses on the architectures and mechanisms to enhance multicast and peer-to-peer content distribution through quality-consciousness. In particular, the following aspects of quality-consciousness are addressed: 1) client latency, 2) service differentiation, and 3) content quality. Data analysis shows that the existing multicast scheduling algorithms behave unfairly when the access conditions for the popular files changes. They favor the popular files while penalizing the files whose access conditions have not changed. To maintain the client latency for all files under dynamic access conditions we develop a novel multicast scheduling algorithm that requires no change in server provisioning. Service differentiation is a desirable functionality for both multicast and peer-to-peer networks. For multicast, we design a scalable and low overhead service differentiation architecture. For peer-to-peer networks, we focus on a protocol to provide different levels of service to peers based on their contributions in the system. The ability to associate reliable reputations with peers in a peer-to-peer network is a useful feature of these networks. Reliable reputations can help establish trust in these networks and hence improve content quality. They can also be used as a substrate for a service differentiation scheme for these networks. This dissertation develops two methods of tracking peer reputations with varying degrees of reliability and overheads.

This dissertation presents a novel modeling framework for understanding the dynamics of peer-to-peer (P2P) networks under churn (i.e., random user arrival/departure) and designing systems more resilient against node failure. The proposed models are applicable to general distributed systems under a variety of conditions on graph construction and user lifetimes. The foundation of this work is a new churn model that describes user arrival and departure as a superposition of many periodic (renewal) processes. It not only allows general (non-exponential) user lifetime distributions, but also captures heterogeneous behavior of peers. We utilize this model to analyze link dynamics and the ability of the system to stay connected under churn. Our results offers exact computation of user-isolation and graph-partitioning probabilities for any monotone lifetime distribution, including heavy-tailed cases found in real systems. We also propose an age-proportional random-walk algorithm for creating links in unstructured P2P networks that achieves zero isolation probability as system size becomes infinite. We additionally obtain many insightful results on the transient distribution of in-degree, edge arrival process, system size, and lifetimes of live users as simple functions of the aggregate lifetime distribution. The second half of this work studies churn in structured P2P networks that are usually built upon distributed hash tables (DHTs). Users in DHTs maintain two types of neighbor sets: routing tables and successor/leaf sets. The former tables determine link lifetimes and routing performance of the system, while the latter are built for ensuring DHT consistency and connectivity. Our first result in this area proves that robustness of DHTs is mainly determined by zone size of selected neighbors, which leads us to propose a min-zone algorithm that significantly reduces link churn in DHTs. Our second result uses the Chen-Stein method to understand concurrent failures among strongly dependent successor sets of many DHTs and finds an optimal stabilization strategy for keeping Chord connected under churn.