Huangs algoritm - Huang's algorithm
Huangs algoritm är en algoritm för att detektera avslutning i ett distribuerat system . Algoritmen föreslogs av Shing-Tsaan Huang 1989 i Journal of Computers .
Avslutningsdetektering
Grunden för detektering av avslutning ligger i begreppet tillstånd för ett distribuerat systemprocess. När som helst är en process i ett distribuerat system antingen i ett aktivt tillstånd eller i viloläge. En aktiv process kan bli inaktiv när som helst men en inaktiv process kan bara bli aktiv igen efter mottagande av ett beräkningsmeddelande.
Avslutning inträffar när alla processer i det distribuerade systemet blir inaktiva och det inte finns några beräkningsmeddelanden under transport.
Algoritm
Huangs algoritm kan beskrivas på följande sätt:
- Till en början är alla processer inaktiva.
- En distribuerad uppgift startas av en process som skickar ett beräkningsmeddelande till en annan process. Denna första process för att skicka meddelandet är "kontrollerande agent".
- Den initiala vikten för det kontrollerande medlet är (vanligtvis 1).
- Följande regler tillämpas genom hela beräkningen:
- En process som skickar ett meddelande delar upp sin nuvarande vikt mellan sig själv och meddelandet.
- En process som tar emot ett meddelande lägger till vikten av meddelandet till sig själv.
- Efter att ha blivit tomgång skickar en process ett meddelande som innehåller hela sin vikt tillbaka till den kontrollerande agenten och den går på tomgång.
- Avslutning inträffar när det kontrollerande medlet har en vikt av och är i viloläge.
Några svagheter för Huangs algoritm är att den inte kan upptäcka avslutning om ett meddelande försvinner under transitering eller om en process misslyckas i ett aktivt tillstånd.
