Distributed enumeration protocol for valuation based systems

The paper presents a new algorithm for the problem of an enumeration protocol for nodes in a network. The new algorithm, contrary to previous ones, is local both in information access (neighbourhood only) and information stored (proportional to the number of neighbours). This property is achieved at the expense of the type of connectivity the network is assumed to exhibit.

W pracy przedstawiono nowy algorytm enumeracji węzłów sieci. W odróżnieniu od dotychczasowych algorytmów jest on lokalny zarówno w sensie dostępu do informacji (uwzględnia się wyłącznie informacje pochodzące od sąsiadów aktualnie przetwarzanego węzła) jak i przechowywania informacji (ilość informacji jest proporcjonalna do liczby sąsiadów danego węzła). Cechę lokalności uzyskano zawężając rozważania do rodziny grafów triangulowanych, które odgrywają podstawową rolę w teorii sieci bayesowskich. Uogólnieniem tych ostatnich są systemy z wartościowaniami, nazywane też grafowymi systemami ekspertowymi, czyli struktury grafowe służące do reprezentacji niedeterministycznych zależności między zmiennymi (odpowiadają im węzły grafu).