Browse Prior Art Database

A PROBABILISTIC ALGORITHM FOR SCATTERING INFORMATION IN A MULTICOMPUTER SYSTEM

IP.com Disclosure Number: IPCOM000128476D
Original Publication Date: 1984-Mar-01
Included in the Prior Art Database: 2005-Sep-16
Document File: 5 page(s) / 90K

Publishing Venue

Software Patent Institute

Related People

Drezner, Zvi: AUTHOR [+4]

Abstract

In this paper we develop a probabilistic algorithm for scattering information between the nodes of a multicomputer which consists of a set of independent computers that are interconnected by a local area communication network. This algorithm is useful when it is desired to reduce the number of messages and the time delay necessary to transmit information from any node to the other nodes of the multicomputer The algorithm that we develop is based on messages which are sent by each node, every unit of time to a randomly selected node. We show that for large values of n, it is possible with probability tending to 1, to scatter information to a set of n nodes in (1 + ln 2)log 2 n steps.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 23% of the total text.

Page 1 of 5

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A PROBABILISTIC ALGORITHM FOR SCATTERING INFORMATION IN A MULTICOMPUTER SYSTEM

Zvi Dreener and Amnon Barak 1 CRL-TR-15-84

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY

MARCH 1984

Room 1079, East Engineering Building
Ann Arbor, Michigan 48109
USA
Tel: (313) 783 A PROBABILISTIC ALGORITHM FOR SCATTERING INFORMATION IN A MULTICOMPUTER SYSTEM [ title ]

Zvi Drezner and Amnon Barak2 March 1984

SUMMARY

In this paper we develop a probabilistic algorithm for scattering information between the nodes of a multicomputer which consists of a set of independent computers that are interconnected by a local area communication network. This algorithm is useful when it is desired to reduce the number of messages and the time delay necessary to transmit information from any node to the other nodes of the multicomputer

The algorithm that we develop is based on messages which are sent by each node, every unit of time to a randomly selected node. We show that for large values of n, it is possible with probability tending to 1, to scatter information to a set of n nodes in (1 + ln 2)log2 n steps.

1. INTRODUCTION

Consider a multicomputer system which consists of n independent nodes that are interconnected by an Ethernet like local area communication network that allows a direct communication link between any pair of nodes as well as broadcast. To utilize such a system efficiently, the operating system of each node must have knowledge about some of the other nodes. For example, information about the availability and location of the resources, length of queues and the current load of some nodes allow other nodes to improve their performance by making better scheduling decisions. Suppose that one node possesses an information which has to be dispersed to all the other nodes. A simple algorithm for scattering this information is to have each node send (asynchronously) one message every unit of time. In order to speed-up

1 On leave from The Hebrew University of Jerusalem, Israel

2 On leave from The Hebrew University of Jerusalem, Israel.

University of Michigan Computing Research Laboratory Page 1 Mar 01, 1984

Page 2 of 5

A PROBABILISTIC ALGORITHM FOR SCATTERING INFORMATION IN A MULTICOMPUTER SYSTEM

the propagation of new information, each node includes newly arrived information in its future messages. We note that the scattering algorithm does not know the source and the final destination of the information, therefore we require that all the nodes use the same algorithm. There are two parameters for measuring the effectiveness of the scattering algorithm. First, since each message causes a communication overhead due to a context switch at the receiving nodes, it is necessary to reduce the total number of context switches for a given algorithm. For example, in a broadcast scheme the total number of context switches is n2, each unit of time. The second parameter is the time delay until all...