More Web Proxy on the site http://driver.im/

Article

Contention resolution under selfishness

Authors:

George Christodoulou,

Katrina Ligett,

Evangelia PyrgaAuthors Info & Claims

ICALP'10: Proceedings of the 37th international colloquium conference on Automata, languages and programming: Part II

Pages 430 - 441

Published: 06 July 2010 Publication History

Abstract

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. [8] 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 + clogn and is in o(1)-equilibrium, where n is the number of users.

References

[1]

Abramson, N.: The ALOHA system: Another alternative for computer communications. In: Proceedings of the Fall Joint Computer Conference, November 17-19, pp. 281-285. ACM, New York (1970).

Digital Library

[2]

Altman, E., El Azouzi, R., Jiménez, T.: Slotted aloha as a game with partial information. Comput. Netw. 45(6), 701-713 (2004).

Digital Library

[3]

Altman, E., Barman, D., Benslimane, A., El Azouzi, R.: Slotted aloha with priorities and random power. In: Proc. IEEE Infocom (2005).

Digital Library

[4]

Auletta, V., Moscardelli, L., Penna, P., Persiano, G.: Interference games in wireless networks. In: Papadimitriou, C., Zhang, S. (eds.)WINE 2008. LNCS, vol. 5385, pp. 278-285. Springer, Heidelberg (2008).

Digital Library

[5]

Bender, M., Farach-Colton, M., He, S., Kuszmaul, B., Leiserson, C.: Adversarial contention resolution for simple channels. In: SPAA 2005, pp. 325-332. ACM, New York (2005).

Digital Library

[6]

Capetanakis, J.: Generalized tdma: The multi-accessing tree protocol. IEEE Transactions on Communications 27(10), 1476-1484 (1979).

[7]

Capetanakis, J.: Tree algorithms for packet broadcast channels. IEEE Transactions on Information Theory 25(5), 505-515 (1979).

[8]

Fiat, A., Mansour, Y., Nadav, U.: Efficient contention resolution protocols for selfish agents. In: SODA 2007, pp. 179-188. SIAM, Philadelphia (2007).

Digital Library

[9]

Georgiadis, L., Papantoni-Kazakos, P.: A collision resolution protocol for random access channels with energy detectors. IEEE Transactions on Communications COM-30, 2413- 2420 (1982).

[10]

Geréb-Graus, M., Tsantilas, T.: Efficient optical communication in parallel computers. In: SPAA 1992, pp. 41-48. ACM, New York (1992).

Digital Library

[11]

Goldberg, L.A., MacKenzie, P.D.: Analysis of practical backoff protocols for contention resolution with multiple servers. J. Comput. Syst. Sci. 58(1), 232-258 (1999).

Digital Library

[12]

Goldberg, L.A., Mackenzie, P.D., Paterson, M., Srinivasan, A.: Contention resolution with constant expected delay. J. ACM 47(6), 1048-1096 (2000).

Digital Library

[13]

Greenberg, A., Winograd, S.: A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels. J. ACM 32(3), 589-596 (1985).

Digital Library

[14]

Hayes, J.: An adaptive technique for local distribution. IEEE Transactions on Communications 26(8), 1178-1186 (1978).

[15]

Koutsoupias, E., Papadimitriou, C.H.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404-413. Springer, Heidelberg (1999).

Digital Library

[16]

Ma, R.T., Misra, V., Rubenstein, D.: Modeling and analysis of generalized slotted-aloha mac protocols in cooperative, competitive and adversarial environments. In: ICDCS 2006, Washington, DC, USA, p. 62. IEEE, Los Alamitos (2006).

Digital Library

[17]

MacKenzie, A., Wicker, S.: Stability of multipacket slotted aloha with selfish users and perfect information (2003).

[18]

MacKenzie, P.D., Plaxton, C.G., Rajaraman, R.: On contention resolution protocols and associated probabilistic phenomena. J. ACM 45(2), 324-378 (1998).

Digital Library

[19]

Menache, I., Shimkin, N.: Efficient rate-constrained nash equilibrium in collision channels with state information. In: INFOCOM 2008, pp. 403-411 (2008).

[20]

Pippenger, N.: Bounds on the performance of protocols for a multiple-access broadcast channel. IEEE Transactions on Information Theory 27(2), 145-151 (1981).

[21]

Raghavan, P., Upfal, E.: Stochastic contention resolution with short delays. Technical report, Weizmann Science Press of Israel, Jerusalem, Israel, Israel (1995).

Digital Library

[22]

Roberts, L.: Aloha packet system with and without slots and capture. SIGCOMM Comput. Commun. Rev. 5(2), 28-42 (1975).

Digital Library

[23]

Ruszinko, M., Vanroose, P.: How an erdöos-rényi-type search approach gives an explicit code construction of rate 1 for random access with multiplicity feedback. IEEE Transactions on Information Theory 43(1), 368-372 (1997).

Digital Library

[24]

Srivastava, V., Neel, J.A., MacKenzie, A.B., Hicks, J.E., DaSilva, L.A., Reed, J.H., Gilles, R.P.: Using game theory to analyze wireless ad hoc networks. IEEE Communications Surveys and Tutorials 7(5), 46-56 (2005).

Digital Library

[25]

Tsybakov, B.: Resolution of a conflict of known multiplicity. Problemy Peredachi Informatsii (1980).

[26]

Tsybakov, B.S., Mikhailov, V.A.: Free synchronous packet access in a broadcast channel with feedback. Problems of Information Transmission 14(4), 259-280 (1978).

[27]

Wang, D., Comaniciu, C., Tureli, U.: Cooperation and fairness for slotted aloha. Wirel. Pers. Commun. 43(1), 13-27 (2007).

Digital Library

[28]

Zheng, D., Ge, W., Zhang, J.: Distributed opportunistic scheduling for ad-hoc communications: an optimal stopping approach. In: MobiHoc 2007, pp. 1-10. ACM, New York (2007).

Digital Library

Cited By

Koutsoupias EPapakonstantinopoulou K(2012)Contention issues in congestion gamesProceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part II10.1007/978-3-642-31585-5_55(623-635)Online publication date: 9-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31585-5_55

Recommendations

Contention Resolution under Selfishness

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 ...
Strategic Contention Resolution in Multiple Channels
Approximation and Online Algorithms
Abstract
We consider the problem of resolving contention in communication networks with selfish users. In a contention game each of identical players has a single information packet that she wants to transmit using one of multiple-access channels. To do ...
A New Contention Resolution Procedure for HFC Access Networks and its Performance Evaluation

Bidirectional Cable TV networks using hybrid fiber coaxial (HFC) systems are good examples of broadcast environments where a contention resolution algorithm is needed in order to allocate the multiaccess medium among various customers. The medium access ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICALP'10: Proceedings of the 37th international colloquium conference on Automata, languages and programming: Part II

July 2010

614 pages

ISBN:3642141617

Editors:
Samson Abramsky
Oxford University Computing Laboratory, Oxford, UK
,
Cyril Gavoille
Université de Bordeaux, LaBRI & INRIA, Talence Cedex, France
,
Claude Kirchner
INRIA, Centre de Recherche Bordeaux - Sud-Ouest, Talence Cedex, France
,
Friedhelm Meyer auf der Heide
Heinz Nixdorf Institute, University of Paderborn, Paderborn, Germany
,
Paul G. Spirakis
University of Patras and RACTI, Patras, Greece

Sponsors

GDR Informatique Mathématique
CNRS: Centre National De La Rechercue Scientifique
Communauté Urbaine de Bordeaux
Conseil Rgional d'Aquitaine
INRIA: Institut Natl de Recherche en Info et en Automatique

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 06 July 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Koutsoupias EPapakonstantinopoulou K(2012)Contention issues in congestion gamesProceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part II10.1007/978-3-642-31585-5_55(623-635)Online publication date: 9-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31585-5_55

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents