NDLI: Adaptive Collaboration in Peer-to-Peer Systems

Content Provider	IEEE Xplore Digital Library
Author	Awerbuch, B. Patt-Shamir, B. Peleg, D. Tuttle, M.
Copyright Year	2005
Description	Author affiliation: Johns Hopkins Univ., Baltimore, MD (Awerbuch, B.)
Abstract	We consider a simple model for reputation systems such as the one used by eBay. In the model there are n players, some of which may exhibit arbitrarily malicious (Byzantine) behavior, and there are m objects, some of which are bad. The goal of the honest players is to find a good object. To facilitate collaboration, the system maintains a shared billboard. A basic step of a player consists of consulting the billboard, probing an object to learn its true value, and posting the result on the billboard for the benefit of others. Probing an object incurs a unit cost to the player, and consulting the billboard is free. The dilemma of an honest player is how to balance between the desire to reduce its cost by taking advantage of the reports posted by honest peers, and the fear of being exploited by adopting reports posted by malicious players. In prior work, the authors presented an algorithm solving this problem in an asynchronous model, and the total cost of the probes made by honest players during the algorithm was analyzed. In this paper, the focus is on the individual cost, and a synchronous model in which each player takes a step in each round was considered. The prior algorithm has individual cost O(1/alphalog n) in this model, assuming that an alpha fraction of players are honest. In this paper, it is proven that no algorithm could guarantee individual cost of less than Omega(1/alpha), which is essentially constant if there are enough honest players. The main result is a new algorithm that achieves O(1) individual cost when there are many honest players, and achieves individual cost O((1/alpha)(log n/ log log n)) even when there are not. It is also shown that this algorithm generalizes to other interesting scenarios
Sponsorship	IEEE Comput. Soc. Tech. Comm. on Distributed Process. (TCDP)
Starting Page	71
Ending Page	80
File Size	173335
Page Count	10
File Format	PDF
ISBN	0769523315
ISSN	10636927
DOI	10.1109/ICDCS.2005.9
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-06-06
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Collaboration Peer to peer computing Costs Probes Algorithm design and analysis Business Collaborative work Protocols
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Collaborative networking in an uncooperative Internet

Reciprocal Exchange for Resource Allocation in Peer-to-Peer Networks

A Backward Algorithm in a Distributed Agreement Computing

Peer-to-peer and group collaboration do they always match?

Decentralized Network Analysis: A Proposal

Inter-enterprise collaborative business process management

Scalability in adaptive multi-metric overlays

Adaptive replication in peer-to-peer systems

Trust and reputation in dynamic scientific communities

Adaptive Collaboration in Peer-to-Peer Systems

Similar Documents

Collaborative networking in an uncooperative Internet

Reciprocal Exchange for Resource Allocation in Peer-to-Peer Networks

A Backward Algorithm in a Distributed Agreement Computing

Peer-to-peer and group collaboration do they always match?

Decentralized Network Analysis: A Proposal

Inter-enterprise collaborative business process management

Scalability in adaptive multi-metric overlays

Adaptive replication in peer-to-peer systems

Trust and reputation in dynamic scientific communities

Adaptive Collaboration in Peer-to-Peer Systems