Distributed Placement of Service Facilities in Large-Scale Networks

The effectiveness of service provisioning in largescale networks is highly dependent on the number and location of service facilities deployed at various hosts. The classical, centralized approach to determining the latter would amount to formulating and solving the uncapacitated k-median (UKM) problem (if the requested number of facilities is fixed), or the uncapacitated facility location (UFL) problem (if the number of facilities is also to be optimized). Clearly, such centralized approaches require knowledge of global topological and demand information, and thus do not scale and are not practical for large networks. The key question posed and answered in this paper is the following: "How can we determine in a distributed and scalable manner the number and location of service facilities?" We propose an innovative approach in which topology and demand information is limited to neighborhoods, or balls of small radius around selected facilities, whereas demand information is captured implicitly for the remaining (remote) clients outside these neighborhoods, by mapping them to clients on the edge of the neighborhood; the ball radius regulates the trade-off between scalability and performance. We develop a scalable, distributed approach that answers our key question through an iterative reoptimization of the location and the number of facilities within such balls. We show that even for small values of the radius (1 or 2), our distributed approach achieves performance under various synthetic and real Internet topologies that is comparable to that of optimal, centralized approaches requiring full topology and demand information.

Implications of Selfish Neighbor Selection in Overlay Networks

In a typical overlay network for routing or content sharing, each node must select a fixed number of immediate overlay neighbors for routing traffic or content queries. A selfish node entering such a network would select neighbors so as to minimize the weighted sum of expected access costs to all its destinations. Previous work on selfish neighbor selection has built intuition with simple models where edges are undirected, access costs are modeled by hop-counts, and nodes have potentially unbounded degrees. However, in practice, important constraints not captured by these models lead to richer games with substantively and fundamentally different outcomes. Our work models neighbor selection as a game involving directed links, constraints on the number of allowed neighbors, and costs reflecting both network latency and node preference. We express a node's "best response" wiring strategy as a k-median problem on asymmetric distance, and use this formulation to obtain pure Nash equilibria. We experimentally examine the properties of such stable wirings on synthetic topologies, as well as on real topologies and maps constructed from PlanetLab and AS-level Internet measurements. Our results indicate that selfish nodes can reap substantial performance benefits when connecting to overlay networks composed of non-selfish nodes. On the other hand, in overlays that are dominated by selfish nodes, the resulting stable wirings are optimized to such great extent that even non-selfish newcomers can extract near-optimal performance through naive wiring strategies.

Christian Witness on the Plateau Vivarais-Lignon: Narrative, Nonviolence, and the Formation of Character

This dissertation analyzes the theological and ethical convictions that led the people of the Plateau Vivarais-Lignon to shelter thousands of refugees between 1939 and 1945. It does so by examining the themes of narrative identity, hospitality, character formation, nonviolence, and the contextual witness of church tradition. Though a number of studies have been published about the rescue activity in this region of France during World War II, none have thoroughly analyzed the theological nature of this activity. Using the Plateau Vivarais-Lignon as a case study in theological ethics, the dissertation draws on historical sources as well as the work of contemporary theologians and ethicists to understand, interpret, and analyze the witness of this community. After situating its rescue and resistance work within the Huguenot narrative of persecution and exile, I examine the theological convictions of the Reformed pastor of Le Chambon-sur-Lignon, André Trocmé, who played a key role in making the Plateau a place of refuge during the Holocaust. The study highlights the importance of narrative in the actions of this community and discusses the relationship between narrative, character, and ethics. It then examines the nonviolent commitments of key leaders of the rescue effort, using this analysis as a springboard to engage in broader theological reflection about the ethics of nonviolence. After examining the radical hospitality practiced on the Plateau in light of biblical narratives and Reformed history, I investigate the counter-cultural nature of Christian hospitality. The study concludes by analyzing the nature and witness of the church in light of the legacy of the Plateau Vivarais-Lignon. The dissertation suggests that increased academic and ecclesial attention be given to the relationship between narrative and character, the counter-cultural shape of Christian hospitality, and the active nature of nonviolence. It presents an in-depth analysis of the theological and ethical convictions of the people of the Plateau Vivarais-Lignon, arguing that their witness has ongoing significance for communities of faith as they grapple with how to form disciples, relate to the wider society, welcome strangers, and communicate God's shalom in a world of violence.

Distributed Selfish Coaching

Although cooperation generally increases the amount of resources available to a community of nodes, thus improving individual and collective performance, it also allows for the appearance of potential mistreatment problems through the exposition of one node's resources to others. We study such concerns by considering a group of independent, rational, self-aware nodes that cooperate using on-line caching algorithms, where the exposed resource is the storage at each node. Motivated by content networking applications -- including web caching, CDNs, and P2P -- this paper extends our previous work on the on-line version of the problem, which was conducted under a game-theoretic framework, and limited to object replication. We identify and investigate two causes of mistreatment: (1) cache state interactions (due to the cooperative servicing of requests) and (2) the adoption of a common scheme for cache management policies. Using analytic models, numerical solutions of these models, as well as simulation experiments, we show that on-line cooperation schemes using caching are fairly robust to mistreatment caused by state interactions. To appear in a substantial manner, the interaction through the exchange of miss-streams has to be very intense, making it feasible for the mistreated nodes to detect and react to exploitation. This robustness ceases to exist when nodes fetch and store objects in response to remote requests, i.e., when they operate as Level-2 caches (or proxies) for other nodes. Regarding mistreatment due to a common scheme, we show that this can easily take place when the "outlier" characteristics of some of the nodes get overlooked. This finding underscores the importance of allowing cooperative caching nodes the flexibility of choosing from a diverse set of schemes to fit the peculiarities of individual nodes. To that end, we outline an emulation-based framework for the development of mistreatment-resilient distributed selfish caching schemes. Our framework utilizes a simple control-theoretic approach to dynamically parameterize the cache management scheme. We show performance evaluation results that quantify the benefits from instantiating such a framework, which could be substantial under skewed demand profiles.