Show simple item record

dc.contributor.authorMavronicolas, Mariosen
dc.contributor.authorMichael, Loizosen
dc.contributor.authorSpirakis, Paul G.en
dc.creatorMavronicolas, Mariosen
dc.creatorMichael, Loizosen
dc.creatorSpirakis, Paul G.en
dc.description.abstractWe study the partially eponymous model of distributed computation, which simultaneously generalizes the anonymous and the eponymous models. In this model, processors have identities, which are neither necessarily all identical, nor necessarily uniqueen
dc.description.abstractprocessors receive inputs and must reach outputs that respect a relation. We focus on the partially eponymous ring R, and we are interested in the computation of circularly symmetric relations on it. • We distinguish between solvability and computability: in solvability, processors must always reach outputs that respect the relationen
dc.description.abstractin computability, they must reach outputs that respect the relation whenever possible, and report impossibility otherwise. - We provide an efficient characterization of solvability of an arbitrary (circularly symmetric) relation on an arbitrary set of rings. The characterization is topological and can be expressed as a numbertheoretic property that can be checked efficiently. - We present a universal distributed algorithm for computing any arbitrary (circularly symmetric) relation on any set of rings. • Towards obtaining message complexity bounds, we derive a distributed algorithm for a natural generalization of Leader Election, in which a (nonzero) number of leaders are elected. We use this algorithm as a subroutine of our universal algorithm for collecting viewsen
dc.description.abstracthence, we prove, as our main result, an upper bound on the message complexity of this particular instantiation of our universal algorithm to compute an arbitrary (circularly symmetric) relation on an arbitrary set of rings. The shown upper bound demonstrates a graceful degradation with the Least Minimum Base, a parameter indicating the degree of topological compatibility between the relation and the set of rings. We employ this universal upper bound to identify two interesting cases where an arbitrary relation can be computed with an efficient number of O(|R|·lg |R|) messages: The set of rings is universal (which allows the solvability of Leader Election), or logarithmic (where each identity appears at most lg |R| times). © Springer-Verlag Berlin Heidelberg 2006.en
dc.source10th International Conference on Principles of Distributed Systems, OPODIS 2006en
dc.subjectDistributed computer systemsen
dc.subjectUpper Bounden
dc.subjectDistributed computationsen
dc.subjectGraceful degradationen
dc.subjectMessage complexityen
dc.subjectO ringsen
dc.subjectEponymous modelsen
dc.subjectLeader electionen
dc.subjectNatural generalizationen
dc.subjectUniversal algorithmen
dc.titleComputing on a partially eponymous ringen
dc.description.volume4305 LNCSen
dc.description.endingpage394 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied SciencesΤμήμα Πληροφορικής / Department of Computer Science
dc.description.notesConference code: 100109en
dc.description.notesCited By :5</p>en
dc.description.notes<p>Sponsors: Agence Universitaire de la Francophonie (AUF)fr
dc.description.notesL'Ecole Pratique des Hautes Etudes (EPHE)fr
dc.description.notesLaboratoire d'Informatique et des Systemes Complexes (LAISC)fr
dc.description.notesUniversite Paris 8, Laboratoire Cognition et Usagefr
dc.source.abbreviationLect. Notes Comput. Sci.en
dc.contributor.orcidSpirakis, Paul G. [0000-0001-5396-3749]

Files in this item


There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record