Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/10905
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Koukopoulos, D. | en |
dc.contributor.author | Nikolopoulos, S. D. | en |
dc.date.accessioned | 2015-11-24T17:01:19Z | - |
dc.date.available | 2015-11-24T17:01:19Z | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/10905 | - |
dc.rights | Default Licence | - |
dc.subject | contention-resolution protocols | en |
dc.subject | adversarial queuing model | en |
dc.subject | universal-stability | en |
dc.title | Heterogenous networks can be unstable at arbitrarily low injection rates | en |
heal.type | journalArticle | - |
heal.type.en | Journal article | en |
heal.type.el | Άρθρο Περιοδικού | el |
heal.language | en | - |
heal.access | campus | - |
heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
heal.publicationDate | 2006 | - |
heal.abstract | A distinguishing feature of today's large-scale platforms for distributed computation and communication, such as the Internet, is their heterogeneity, predominantly manifested by the fact that a wide variety of communication protocols are simultaneously running over different distributed hosts. A fundamental question that naturally poses itself for such common settings of heterogeneous distributed systems concerns their ability to preserve or restore an acceptable level of performance during link failures. In this work, we address this question for the specific case of stability properties of greedy, contention-resolution protocols operating over a packet-switched communication network that suffers from link slowdowns. We focus on the Adversarial Queueing Theory framework, where an adversary controls the rates of packet injections and determines packet paths. In addition, the power of the adversary is enhanced to include the manipulation of link slowdowns. Within-this framework, we show that the composition of LIS (Longest-in-System) with any of SIS (Shortest-in-System), NTS (Nearest-to-Source) and FTG (Furthest-to-Go) protocols is unstable at rates p > 0 when the network size and the link slowdown take large values. These results represent the current record for instability bounds on injection rate for compositions of greedy protocols over dynamic adversarial models, and also suggest that the potential for instability incurred by the composition of two greedy protocols may be worse than that of some single protocol. | en |
heal.journalName | Algorithms and Complexity, Proceedings | en |
heal.journalType | peer reviewed | - |
heal.fullTextAvailability | TRUE | - |
Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
nikolopoulos-2006-Heterogenous networks can be unstable at arbitrarily low injection rates.pdf | 539.94 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License