Problemet med att hitta en skog som spänner över en graf i en distribuerad processmiljö studeras. Om en inmatningskurva viktas är målet att hitta en minsta vikt som spänner över skogen. Processorerna kommunicerar genom radio- och TV-sändningar. Utgången består av de kanter som gör en spännande skog och har sänts ut på nätet. Ingångskanter fördelas mellan processorer, med varje kant som hålls av en processor. Det underliggande sändningsnätet genomförs som en kanal för flera åtkomster. Om exakt en processor försöker utföra en sändning, då sändningen är framgångsrik. Ett meddelande som sänds framgångsrikt levereras till alla processorer i ett steg. Om fler än en processor sänder samtidigt, då meddelandena stör varandra och ingen processor kan ta emot någon av dem. Optimalitet av algoritmiska lösningar undersöks, genom att jämföra deterministiska med randomiserade algoritmer, och adaptiv med omedvetna. Nedre gränser bevisas antingen motivera optimaliteten hos specifika algoritmer eller visa att den optimala prestandan beror på en klass av algoritmer. * Detta verk publicerades som [5]. Resultaten av detta dokument presenterades i en preliminär form [6].
Arbetet av Chlebus et al. REF ansåg att sändningar som spänner över skogar på en flergångskanal, med lokalt lagrade kanter på en inmatningskurva.
Broadcasting Spanning Forests on a Multiple-Access Channel
{'venue': 'Theory of Computing Systems, 36(6) : 711 - 733, 2003', 'journal': None, 'mag_field_of_study': ['Computer Science']}