Distributed algorithms adapted to knows-based systems

T. Eirich

english, 10 pages

Abstract: This paper presents distributed algorithms for a computational model based on knows relations. Usually, a distributed system is modelled by a graph. The edges of the graph represent static communication links and messages between nodes has to follow a path in the graph. This model is called the topology model. In contrast to this model we assume that any two nodes can exchanged messages directly provided the sender knows the identification of the destination. A network layer abstracts from the underlying communication topology and provides efficient delivery of messages. This model seems to be more convenient with respect to today's software layering. Objects or processes communicate via messages, RPCs or DSM without any knowledge of the physical network. We present three classes of algorithms, simple propagation of information, echo algorithms, and election algorithms tailored to this model. Each class is based on the algorithms of the previous one. The time complexity of the algorithms is only half of those designed for network topologies.

[Full Paper (ps,http) , 37 kB][Full Paper (pdf) , 38 kB]