Главная

Costas Busch

  1. Polynomial Bottleneck Congestion Games with Optimal Price of Anarchy.

    Втр, 10/26/2010 - 15:01 — SomNambul
    Authors: Costas Busch, Rajgopal Kannan, Athanasios Vasilakos
    Subjects: Computer Science and Game Theory
    Abstract

    We study {\em bottleneck congestion games} where the social cost is
    determined by the worst congestion of any resource. These games directly relate
    to network routing problems and also job-shop scheduling problems. In typical
    bottleneck congestion games, the utility costs of the players are determined by
    the worst congested resources that they use. However, the resulting Nash
    equilibria are inefficient, since the price of anarchy is proportional on the
    number of resources which can be high. Here we show that we can get smaller
    price of anarchy with the bottleneck social cost metric.

  2. A Competitive Analysis for Balanced Transactional Memory Workloads.

    Чт, 09/02/2010 - 15:01 — SomNambul
    Authors: Gokarna Sharma, Costas Busch
    Subjects: and Cluster Computing, Distributed, Parallel
    Abstract

    We consider transactional memory contention management in the context of
    balanced workloads, where if a transaction is writing, the number of write
    operations it performs is a constant fraction of its total reads and writes. We
    explore the theoretical performance boundaries of contention management in
    balanced workloads from the worst-case perspective by presenting and analyzing
    two new contention management algorithms. The first algorithm Clairvoyant is
    O(\surd s)-competitive, where s is the number of shared resources. This
    algorithm depends on explicitly knowing the conflict graph.

  3. Bottleneck Routing Games with Low Price of Anarchy.

    Ср, 03/24/2010 - 16:01 — SomNambul
    Authors: Costas Busch, Rajgopal Kannan
    Subjects: Computer Science and Game Theory
    Abstract

    We study {\em bottleneck routing games} where the social cost is determined
    by the worst congestion on any edge in the network. In the literature,
    bottleneck games assume player utility costs determined by the worst congested
    edge in their paths. However, the Nash equilibria of such games are inefficient
    since the price of anarchy can be very high and proportional to the size of the
    network. In order to obtain smaller price of anarchy we introduce {\em
    exponential bottleneck games} where the utility costs of the players are
    exponential functions of their congestions.

  4. Window-Based Greedy Contention Management for Transactional Memory.

    Втр, 02/23/2010 - 16:02 — SomNambul
    Authors: Gokarna Sharma, Brett Estrade, Costas Busch
    Subjects: and Cluster Computing, Distributed, Parallel
    Abstract

    We consider greedy contention managers for transactional memory for M x N
    execution windows of transactions with M threads and N transactions per thread.
    Assuming that each transaction conflicts with at most C other transactions
    inside the window, a trivial greedy contention manager can schedule them within
    CN time. In this paper, we show that there are much better schedules.

Math-arch

RSS-материал