2009 | OriginalPaper | Buchkapitel
On the Computational Power of Shared Objects
verfasst von : Gadi Taubenfeld
Erschienen in: Principles of Distributed Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose a new classification for evaluating the strength of shared objects. The classification is based on finding, for each object of type
o
, the strongest progress condition for which it is possible to solve consensus for
any
number of processes, using any number of objects of type
o
and atomic registers. We use the strongest progress condition to associate with each object a number call the
power number
of that object. Objects with higher power numbers are considered stronger. Then, we define the
power hierarchy
which is an infinite hierarchy of objects such that the objects at level
i
of the hierarchy are exactly those objects with power number
i
. Comparing our classification with the traditional one which is based on fixing the progress condition (namely, wait-freedom) and finding the largest number of processes for which consensus is solvable, reveals interesting results. Our equivalence and extended universality results, provide a deeper understanding of the nature of the relative computational power of shared objects.