Decentralization Items
December 11, 2004

Newswire: Cornell’s decentralized news network (“zNN”)

Decentralization By: ams

Newswire – Collaborative real-time content delivery

Why Newswire? Newswire is a peer-to-peer, fully decentralized system that brings news to your desktop, within seconds after it is published.  This technology gives the community the power to weave a collaborative infrastructure for the delivery of essential information to individuals in a robust, scalable and secure way. Newswire is a survivable system which will deliver news to subscribers even if large parts of the infrastructure are under attack or stress.

The development of Newswire followed discussions after the 9/11 attacks when flash-crowd effects made it impossible for many to reach essential news sites. Email and weblogs proved more effective technologies in that situation, although both still suffer from the centralized risks of overload and single-point-of-failure. A more robust approach is to use a peer-to-peer structuring of the system and provide strong incentives for people to collaborate on the delivery of information to everyone by giving up a bit of bandwidth and CPU cycles.

Newswire has the additional effect that it can significantly reduce the load on the websites carrying real-time news information by providing hints about when information has changed. This would change the frequent redundant poll behavior seen by many news sites into more effective visits.

The Newswire Technology What is the technology that makes Newswire so special? At the core is epidemic communication and state management to maintain distributed knowledge about  subscriptions, participant network capabilities and forwarding load. The epidemic technology was first developed by Alan Demers and friends at PARC, but has been completely revised at Cornell in the past years

The structuring into zones and virtual hierarchies is based on the small worlds phenomenon. When you organize participants into  small groups of local participants with some knowledge of other remote nodes you can construct very effective routes in a decentralized, autonomous manner.

These technologies are used to build a loosely coupled, dynamic overlay network, that continuously monitors network load and capacities to achieve a fair load.

Subscription information stored in Bloom Filters is aggregated such that simple forwarding decisions can be made anywhere in the network based on the location of the publication and the direction where possible subscriber are localed.

Vogels pointed to half a dozen really great papers in All Things Distributed: Epidemic Computing at Cornell

… that having to scale up your system is no longer a burden, but it becomes an advantage and you can deliver on the true promise of scale-out: more nodes means a more robust system.

Also, he noted: All Things Distributed: Wired on the Scalability of Feed Aggregators

We have had some legal issues with the deployment of the newswire beta, and a new core communication component is being developed. But I would be happy to break open the ideas in the system and work with others to see whether this can be a good experimentation platform.

December 11, 2004

The Supremes Learn About Sharing

Decentralization By: ams

[NYT] Justices to Hear Case on Sharing of Music Files

The Ninth Circuit had found Napster liable because the company itself maintained and controlled the servers that searched for the digital files its users wanted to download. Grokster and StreamCast, by contrast, operate decentralized systems that allow users to find each other over the Internet and then exchange files directly. Consequently, the appeals court said, the two services did not exercise the kind of control that could lead to legal liability for infringing uses.

December 8, 2004

Decentralizing BitTorrent

Decentralization By: ams

Courtesy of zLab Associate Kevin Hughes’ KevsNews:

Slashdot | Decentralizing Bittorrent
… “Exeem is a new file-sharing application being developed by the folks at SuprNova.org. Exeem is a decentralized BitTorrent network that basically makes everyone a Tracker. Individuals will share Torrents, and seed shared files to the network. At this time, details and the full potential of this project are being kept very quiet. However it appears this P2P application will completely replace SuprNova.org; no more web mirrors, no more bottle necks and no more slow downs. Exeem will marry the best features of a decentralized network, the easy searchability of an indexing server and the swarming powers of the BitTorrent network into one program. Currently, the network is in beta testing and already has 5,000 users (the beta testing is closed.) Once this program goes public, its potential is enormous. “

December 1, 2004

Beyond Web of Trust: Enabling P2P e-Commerce

Decentralization By: ams

Beyond “web of trust”: Enabling P2P E-commerce:

The long-term goal would be to design a fully functional decentralized system which resembles eBay without eBay’s dedicated, centralized infrastructure. Since security (authenticity, non-repudiation, trust, etc.) is key to any e-commerce infrastructure, our envisioned P2P e-commerce platform has to address this adequately. As the first step in this direction we present an approach for a completely decentralized P2P public key infrastructure (PKI) which can serve as the basis for higher-level security service. In contrast to other systems in this area, such as PGP which uses a “web of trust” concept, we use a statistical approach which allows us to provide an analytical model with provable guarantees, and quantify the behavior and specific properties of the PKI. To justify our claims we provide a first-order analysis and discuss its resilience against various known threats and attack scenarios.

In support of our belief that C2C E-commerce is one of the potential killer applications of the emerging structured P2P systems, we provide a layered model for P2P E-commerce, demonstrating the dependencies of various security related issues that can be built on top of a decentralized PKI.

November 29, 2004

MapReduce for decentralized computation

Decentralization By: ams

I just added a technical note to our Wiki extending the work of Dean and Ghemawat on MapReduce, a support library for programs that take advantage of large clusters such as those at Google. The fundamental problems of writing distributed systems like these — latency, naming (or memory access), partial failures, and concurrency are toy versions of most of the key problems of decentralized systems. (Agency conflict is the one problem that distinguishes decentralized systems from distributed systems, and it dramatically worsens the other four.)

It occurred to me that MapReduce has the capability to handle some of the agency problems of decentralized systems, particularly those that affect reliability, in a remarkably simple way:

In the usual case, where these functions are deterministic, they can be executed on two administratively-independent servers, and the results (which, in the Google case, are merely files) can be compared. If they differ, the same results can be recomputed on more administratively-independent servers to see which ones were correct.

November 28, 2004

Jim Youll’s Thesis: The Atomic Market

Decentralization By: ams

The Atomic Market:

Today’s electronic marketplaces are closed, centralized and inflexible.

We propose a new type of electronic marketplace, which we refer to as an “atomic market.” Atomic markets differ from today’s electronic marketplaces in that they are (1) open-ended, (2) decentralized and (3) component-based. The atomic market supports short-lived markets created around the individual components of everyday transactions. The traders in an atomic market are agents, software that acts as a proxy for an actual buyer and seller.

The atomic market allows expressive interactions among trading agents, leading to productive, automated agent-based transactions. The focus is on the technical infrastructure for atomic marketplaces, specifically the use of logic as a basis for the decomposition of transactions and the negotiations between the different agents.

The Atomic Market

S.M. Thesis, submitted August, 2001 to the Program in Media Arts and Sciences:
Peer to Peer Transactions in Agent-mediated Electronic Commerce (1.7mb PDF)

November 26, 2004

Benchmarking Competition for Trading Agents

Decentralization By: ams

Found this linking from Vorobeychik, a student of the current sigecom chair, M. Wellman. He wrote a *great* survey 5-pager at http://www.eecs.umich.edu/~yvorobey/2002/YABackground.pdf

http://www.eecs.umich.edu/~yvorobey/professional.htm#projects

http://www.eecs.umich.edu/~yvorobey/

http://ai.eecs.umich.edu/people/wellman/research/group.html

PhD Graduates

(Chronological order)

name (defense date) [current affiliation]

thesis title

John Cheng (Jan 1998) [Capital Networks]

Essays on Designing Economic Mechanisms
co-advised with Carl Simon

Chao-Lin Liu (May 1998) [Taiwan Nat’l Chengchi University]

State-Space Abstraction Methods for Approximate Evaluation of Bayesian Networks

Tracy Mullen (Jan 1999) [Pennsylvania State University]

The Design of Computational Markets for Network Information Services

David Pynadath (Jan 1999) [USC Information Sciences Institute]

Probabilistic Grammars for Plan Recognition

Junling Hu (Jun 1999) [Talkai, Inc.]

Learning in Dynamic Noncooperative Multiagent Systems

Peter Wurman (Jul 1999) [North Carolina State University]

Market Structure and Multidimensional Auction Design for Computational Economies

David Pennock (Sep 1999) [Overture]

Aggregating Probabilistic Beliefs: Market Mechanisms and Graphical Representations

William Walsh (May 2001) [IBM Research]

Market Protocols for Decentralized Supply Chain Formation

Trading Agent Competition – TAC Classic – Game Description

In the TAC shopping game, each “agent” (an entrant to the competition) is a travel agent, with the goal of assembling travel packages (from TACtown to Tampa, during a notional 5-day period). Each agent is acting on behalf of eight clients, who express their preferences for various aspects of the trip. The objective of the travel agent is to maximize the total satisfaction of its clients (the sum of the client utilities).

Travel packages consist of the following:
A round-trip flight,

A hotel reservation, and

Tickets to some of the following entertainment events

Alligator wrestling

Amusement park

Museum

Illustration of the environment a TAC agent operates within. To the left are its eight clients and their preferences, in the middle all its competitors lined up (7 competitors/game), and to its right are all the auctions (28 simultaneous auctions of three different types).

There are obvious interdependencies, as the traveler needs a hotel for every night between arrival and departure of the flight, and can attend entertainment events only during that interval. In addition, the clients have individual preferences over which days they are in Tampa, the type of hotel, and which entertainment they want. All three types of goods (flights, hotels, entertainment) are traded in separate markets with different rules.

A run of the game is called an instance. Several instances of the game are played during each round of the competition in order to evaluate each agent’s average performance and to smooth the variations in client preferences.

November 16, 2004

Real Names

Decentralization By: ams

John Battelle points out that RealNames has relaunched. Founder Keith Teare writes:

The problem addressed by RealNames – that is the poverty of the DNS as a naming and navigation system for the world’s internet users – remains unresolved.

November 11, 2004

Market Based Resource Allocation

Decentralization By: ams

Fine is a former student of Ledyard’s, who also Hanson’s advisor.

Research at HP Labs : Information Dynamics Lab : Papers : Eliminating Public Knowledge Biases in Small Group Predictions

Kevin Lai, Bernardo A. Huberman, Leslie R. Fine

HP Laboratories
Palo Alto, CA 94304

Abstract

P2P clusters like the Grid and PlanetLab enable in principle the same statistical multiplexing efficiency gains for computing as the Internet provides for networking. The key unsolved problem is resource allocation. Existing solutions are not economically efficient and require high latency to acquire resources. We designed and implemented Tycoon, a market based distributed resource allocation system based on an Auction Share scheduling algorithm. Preliminary results show that Tycoon achieves low latency and high fairness while providing incentives for truth-telling on the part of strategic users.

November 9, 2004

Great Oneliner From a Schmidt Talk

Decentralization By: ams

kwc blog: Forum: Google:

Google allows weirdos to advertise to weirdos (e.g. Monkey hats and Bird poop ads)