Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



ID: 536793.0, MPI für Informatik / Algorithms and Complexity Group
Contention Resolution under Selfishness
Authors:Christodoulou, Giorgos; Ligett, Katrina; Pyrga, Evangelia
Language:English
Publisher:Springer
Place of Publication:Berlin
Date of Publication (YYYY-MM-DD):2010
Title of Proceedings:Automata, Languages and Programming : 37th International Colloquium, ICALP 2010. - Pt. II
Start Page:430
End Page:441
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Bordeaux, France
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2010-07-06
End Date of Conference/Meeting 
 (YYYY-MM-DD):
2010-07-10
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:In many communications settings, such as wired and wireless local-area
networks, when multiple users attempt to access a communication channel at the
same time, a conflict results and none of the communications are
successful. Contention resolution is the study of distributed transmission and
retransmission protocols designed to maximize notions of utility such as
channel utilization in the face of blocking communications.

An additional issue to be considered in the design of such protocols
is that selfish users may have incentive to deviate from the
prescribed behavior, if another transmission strategy increases their
utility. The work of Fiat et al.~\cite{Fiat07} addresses this issue by
constructing an asymptotically optimal incentive-compatible
protocol. However, their protocol assumes the cost of any single
transmission is zero, and the protocol completely collapses under non-zero
transmission costs.

In this paper, we treat the case of non-zero transmission cost $c$.
We present asymptotically optimal contention resolution protocols that
are robust to selfish users, in two different channel feedback
models. Our main result is in the Collision Multiplicity Feedback
model, where after each time slot, the number of attempted
transmissions is returned as feedback to the users. In this setting,
we give a protocol that has expected cost $2n+c\log n$ and is in
$o(1)$-equilibrium, where $n$ is the number of users.
Last Change of the Resource (YYYY-MM-DD):2011-02-14
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-30945EFEF69FAA0BC125781F0044245C-...
URL:http://dx.doi.org/10.1007/978-3-642-14162-1_36
DOI:10.1007/978-3-642-14162-1_36
ISBN:978-3-642-14161-4
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.