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.

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. “

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.

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.

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.