Re: Fragen zu 2PL vs. TO vs. SGT

Subject:

Comments:
: : : in der letzten Uebungsstunde haben wir festgestellt, dass TO die Klasse SGT (=CPSR) enthaelt, falls die Zeitstempelordnung beliebig ist (der Beweis mit der topologischen Sortierung). Auf einem aelteren Uebungsblatt kam einmal vor, dass 2PL und TO nicht vergleichbar sind. Das heisst doch, dass es S gibt, die ausserhalb von TO, aber in 2PL sind, und weil TO > CPSR, dann auch ausserhalb von CPSR sind?? : : (Oder kann man sagen, dass bei beliebig waehlbarer Zeitstempelordnung TO die Klasse 2PL enthaelt? Ist TO mit solcher beliebig waehlbaren Zeitstempelordnung so maechtig wie VSR (es ist ja dann auch in NP, oder?) : : Ich habe mal eine Zeichnung angefertigt fuer die erwaehnten Klassen, links fuer den Fall TO mit fixer Zeitstempelordnung, rechts mit anpassbarer - stimmt die? : Im linken Bild (TO mit fix vorgegebener Zeitstempelordnung) ist TO NICHT in CPSR bzw. SGT enthalten. Ebenso ist dieses TO auch mit VSR nicht vergleichbar. Ein Beispiel fuer VSR aber nicht TO (mit BOT-Ordnung = Zeitstempelordnung) ist der : folgende Schedule: r1(x) w2(y) r1(y). : In anderen Fall, in dem die Zeitstempelordnung beliebig waehlbar ist, haben wir festgestellt, dass jeder SGT-Schedule auch durch TO haette enstehen koennen. Das heisst eben auch, dass es zu jedem CPSR-Schedule eine Zeitstempelordnung fuer TO gibt. : Allerdings trifft dies nicht fuer VSR zu. Der foilgende Schedule beweist dies: S = w1(x) w2(x) w2(y) w1(y). Es gibt keine RF-Paare, also ist S trivialerweise VSR. Allerdings laesst keine der moeglichen Zeitstempelordnungen diesen Schedule via TO zu. : Was die Komplexitaet angeht, so stimmt es, dass die Wahl der geeigneten Zeitstempelordnung das ganze NP-vollstaendig machen wuerde. Aber wie bereits in der Uebungsstunde erwaehnt: in praktischen Protokollen ist diese Ordnung fest vorgegeben und : nicht waehlbar. : -- Heiko

Optional Link URL:
Link Title:
Optional Image URL: