Person:
Ng, Chaki

Profile Picture

Email Address

AA Acceptance Date

Birth Date

Research Projects

Organizational Units

Job Title

Last Name

Ng

First Name

Chaki

Name

Ng, Chaki

Filters

2003 - 20097

Settings

Author's Publications: search.filters.isAuthorOfPublication.ae57f695-81e2-41c8-9435-1a01b85fb297

Search Results

Now showing 1 - 7 of 7
  • Thumbnail Image
    Publication
    Concatenated Codes for Deletion Channels
    (2003) Chen, Johnny; Mitzenmacher, Michael; Ng, Chaki; Varnica, Nedeljko
    We design concatenated codes suitable for the deletion channel. The inner code is a combination of a single deletion correcting Varshamov-Tenengolts block code and a marker code. The outer code is a low-density parity-check (LDPC) code. The inner decoder detects the synchronizing points in the receive symbol sequence and feeds the outer LPDC decoder with soft information. Even using regular LPC codes as outer odes our results are promising. Our simulation results demonstrate that bit error rates of 10^-6 can be obtained at rate 0.21 when the probability of deletion is 8%.
  • Thumbnail Image
    Publication
    Egg: An Extensible and Economics-Inspired Open Grid Computing Platform
    (World Scientific Publishing, 2006) Brunelle, John A; Hurst, Peter; Huth, John; Kang, Laura; Ng, Chaki; Parkes, David; Seltzer, Margo; Shank, Jim; Youssef, Saul
    The Egg project provides a vision and implementation of how heterogeneous computational requirements will be supported within a single grid and a compelling reason to explain why computational grids will thrive. Environment computing, which allows a user to specify properties that a compute environment must satisfy in order to support the user’s computation, provides a how. Economic principles, allowing resource owners, users, and other stakeholders to make value and policy statements, provides a why. The Egg project introduces a language for defining software environments (egg shell), a general type for grid objects (the cache), and a currency (the egg). The Egg platform resembles an economically driven Internetwide Unix system with egg shell playing the role of a scripting language and caches playing the role of a global file system, including an initial collection of devices.
  • Thumbnail Image
    Publication
    Strategyproof Computing: Systems Infrastructures for Self-Interested Parties
    (2003) Ng, Chaki; Parkes, David; Seltzer, Margo
    The widespread deployment of high-speed internet access is ushering in a new era of distributed computing, in which parties both contribute to a global pool of shared resources and access the pooled resources to support their own computing needs. We argue that system designers must explicitly address the self-interest of individual parties if these next-generation computing systems are to flourish. We propose strategyproof computing, a vision for an open computing infrastructure in which resource allocation and negotiation schemes are incentive-compatible, and individual parties can treat other resources as their own. In this paper we outline key guiding principles for the vision of strategyproof computing, define the strategyproof computing paradigm, and lay out a systems-related research agenda.
  • Thumbnail Image
    Publication
    Why Markets Could (But Don't Currently) Solve Resource Allocation Problems in Systems
    (USENIX, 2005) Shneidman, Jeffery; Ng, Chaki; Parkes, David; Young, Alvin Au; Snoeren, Alex C.; Vahdat, Amin; Chun, Brent
    Using market mechanisms for resource allocation in distributed systems is not a new idea, nor is it one that has caught on in practice or with a large body of computer science research. Yet, projects that use markets for distributed resource allocation recur every few years [1, 2, 3], and a new generation of research is exploring market-based resource allocation mechanisms [4, 5, 6, 7, 8] for distributed environments such as Planetlab, Netbed, and computational grids. This paper has three goals. The first goal is to explore why markets can be appropriate to use for allocation, when simpler allocation mechanisms exist. The second goal is to demonstrate why a new look at markets for allocation could be timely, and not a re-hash of previous research. The third goal is to point out some of the thorny problems inherent in market deployment and to suggest action items both for market designers and for the greater research community. We are optimistic about the power of market design, but we also believe that key challenges exist for a markets/systems integration that must be overcome for market-based computer resource allocation systems to succeed.
  • Thumbnail Image
    Publication
    Mirage: A Microeconomic Resource Allocation System for Sensornet Testbeds
    (Institute of Electrical and Electronics Engineers, 2005) Chun, Brent N.; Buonadonna, Philip; AuYoung, Alvin; Ng, Chaki; Parkes, David; Shneidman, Jeffery; Snoeren, Alex C.; Vahdat, Amin
    In this paper, we argue that a microeconomic resource allocation scheme, specifically the combinatorial auction, is well suited to testbed resource management. To demonstrate this, we present the Mirage resource allocation system. In Mirage, testbed resources are allocated using a repeated combinatorial auction within a closed virtual currency environment. Users compete for testbed resources by submitting bids which specify resource combinations of interest in space/time (e.g., "any 32 MICA2 motes for 8 hours anytime in the next three days") along with a maximum value amount the user is willing to pay. A combinatorial auction is then periodically run to determine the winning bids based on supply and demand while maximizing aggregate utility delivered to users. We have implemented a fully functional and secure prototype of Mirage and have been operating it in daily use for approximately four months on Intel Research Berkeley's 148-mote sensornet testbed.
  • Thumbnail Image
    Publication
    Virtual Worlds: Fast and Strategyproof Auctions for Dynamic Resource Allocation
    (Association for Computing Machinery, 2003) Ng, Chaki; Parkes, David; Seltzer, Margo
    We consider the problem of designing fast and strategyproof exchanges for dynamic resource allocation problems in distributed systems. The exchange is implemented as a sequence of auctions, with dynamically arriving requests from agents matched with each auction. Each auction is associated with some consignment of the resources from a single seller. We provide a simple Virtual Worlds (VW) construction, that extends a fast and strategyproof mechanism for a single auction to apply to this sequence-of-auctions setting. Rather than match each buyer with a single auction, the VW mechanism allows buyers to be considered for multiple auctions while retaining strategyproofness.
  • Thumbnail Image
    Publication
    Two Auction-Based Resource Allocation Environments: Design and Experience
    (Wiley, 2009) AuYoung, Alvin; Buonadonna, Phil; Chun, Brent N.; Ng, Chaki; Parkes, David; Shneidman, Jeffrey; Snoeren, Alex C.; Vahdat, Amin
    Many computer systems have reached the point where the goal of resource allocation is no longer to maximize utilization; instead, when demand exceeds supply and not all needs can be met, one needs a policy to guide resource allocation decisions. One natural policy is to seek efficient usage, which allocates resources to the set of users who have the highest utility for the use of the resources. Researchers have frequently proposed market-based mechanisms to provide such a goal-oriented way to allocate resources among competing interests while maximizing overall utility of the users.