Show simple item record

dc.contributor.authorKoukopoulos, D.en
dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorNikoletseas, Sotiris E.en
dc.contributor.authorSpirakis, Paul G.en
dc.contributor.editorMalkhi D.en
dc.creatorKoukopoulos, D.en
dc.creatorMavronicolas, Mariosen
dc.creatorNikoletseas, Sotiris E.en
dc.creatorSpirakis, Paul G.en
dc.date.accessioned2019-11-13T10:40:46Z
dc.date.available2019-11-13T10:40:46Z
dc.date.issued2002
dc.identifier.issn0302-9743
dc.identifier.urihttp://gnosis.library.ucy.ac.cy/handle/7/54291
dc.description.abstractA 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 concerns the preservation (or loss) of important correctness and performance properties of the individual protocols when they are composed in a large network. In this work, we specifically address stability properties of greedy, contention-resolution protocols operating over a packet-switched communication network. We focus on a basic adversarial model for packet arrival and path determination for which the time-averaged arrival rate of packets requiring a single edge is no more than 1. Stability requires that the number of packets in the system remains bounded, as the system runs for an arbitrarily long period of time. It is known that several commonly used contentionresolution protocols, such as LIS (Longest-in-System), SIS (Shortest-in- System), NTS (Nearest-to-Source), and FTG (Furthest-to-Go) are universally stable in this setting – that is, they are stable over all networks. We investigate the preservation of universal stability under compositions for these four greedy, contention-resolution protocols. We discover: – The composition of any two protocols among SIS, NTS and FTG is universally stable. – The composition of LIS with any of SIS, NTS and FTG is not universally stable: we provide interesting combinatorial constructions of networks over which the composition is unstable when the adversary’s injection rate is at least 0.519. – Through an involved combinatorial construction, we significantly improve the current state-of-the-art record for the adversary’s injection rate that implies instability for FIFO protocol to 0.749. Since 0.519 is significantly below 0.749, this last result suggests that the potential for instability incurred by the composition of two universally stable protocols may be worse than that of some single protocol that is not universally stable. © Springer-Verlag Berlin Heidelberg 2002.en
dc.source16th International Conference on Distributed Computing, DISC 2002en
dc.source.urihttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84947207411&partnerID=40&md5=4f967e04704446cd8c1c128724f9f076
dc.subjectDistributed computer systemsen
dc.subjectStabilityen
dc.subjectDistributed computationsen
dc.subjectInternet protocolsen
dc.subjectStability propertiesen
dc.subjectPerformance propertiesen
dc.subjectLongest in systemsen
dc.subjectContention resolution protocolsen
dc.subjectLarge scale platformsen
dc.subjectPacket-switched communication networksen
dc.subjectSwitching circuitsen
dc.subjectUniversal stabilityen
dc.titleOn the stability of compositions of universally stable, greedy contention-resolution protocolsen
dc.typeinfo:eu-repo/semantics/article
dc.description.volume2508
dc.description.startingpage88
dc.description.endingpage102
dc.author.faculty002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences
dc.author.departmentΤμήμα Πληροφορικής / Department of Computer Science
dc.type.uhtypeArticleen
dc.description.notes<p>Sponsors:en
dc.description.notesConference code: 132319en
dc.description.notesCited By :20</p>en
dc.source.abbreviationLect. Notes Comput. Sci.en
dc.contributor.orcidSpirakis, Paul G. [0000-0001-5396-3749]
dc.gnosis.orcid0000-0001-5396-3749


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record