August 1979 - Vol. 22 No. 8

August 1979 issue cover image

Features

Research and Advances

Computing connected components on parallel computers

We present a parallel algorithm which uses n2 processors to find the connected components of an undirected graph with n vertices in time O(log2n). An O(log2n) time bound also can be achieved using only n⌈n/⌈log2n⌉⌉ processors. The algorithm can be used to find the transitive closure of a symmetric Boolean matrix. We assume that the processors have access to a common memory. Simultaneous access to the same location is permitted for fetch instructions but not for store instructions.
Research and Advances

Proving termination with multiset orderings

A common tool for proving the termination of programs is the well-founded set, a set ordered in such a way as to admit no infinite descending sequences. The basic approach is to find a termination function that maps the values of the program variables into some well-founded set, such that the value of the termination function is repeatedly reduced throughout the computation. All too often, the termination functions required are difficult to find and are of a complexity out of proportion to the program under consideration. Multisets (bags) over a given well-founded set S are sets that admit multiple occurrences of elements taken from S. The given ordering on S induces an ordering on the finite multisets over S. This multiset ordering is shown to be well-founded. The multiset ordering enables the use of relatively simple and intuitive termination functions in otherwise difficult termination proofs. In particular, the multiset ordering is used to prove the termination of production systems, programs defined in terms of sets of rewriting rules.
Research and Advances

Secure personal computing in an insecure network

A method for implementing secure personal computing in a network with one or more central facilities is proposed. The method employs a public-key encryption device and hardware keys. Each user is responsible for his own security and need not rely on the security of the central facility or the communication links. A user can safely store confidential files in the central facility or transmit confidential data to other users on the network.
Research and Advances

Further remark on stably updating mean and standard deviation estimates

A procedure for sequentially recomputing the mean and standard deviation of a weighted series of numbers as new values are added is given by Hanson [2]. To accommodate the most frequently occurring situation, Cotton [1] expressed Hanson's formulas in terms of unit weights. The result is accurate for updating the mean. However, for updating the standard deviation, Cotton chose to use Hanson's eq. (14), which Hanson rejected as being inaccurate when the new value is close to the mean.

Recent Issues

  1. December 2024 CACM cover
    December 2024 Vol. 67 No. 12
  2. November 2024 CACM cover
    November 2024 Vol. 67 No. 11
  3. October 2024 CACM cover
    October 2024 Vol. 67 No. 10
  4. September 2024 CACM cover
    September 2024 Vol. 67 No. 9