Introduction to Lattice Theory with Computer Science Applications

Chapter 4Merging Algorithms

4.1 Introduction

In Chapter 3, we proved Dilworth's Theorem for partitioning a poset into the least number of chains. We now give an efficient algorithm to compute this partition that is especially useful in distributed systems. This algorithm is based on reducing the number of chains in a given chain partition whenever possible. To determine optimal chain composition, we begin with the trivial chain partition in which each element of the poset is a one element chain. By repeatedly reducing the number of chains, we arrive at the optimal chain partition. The number of chains in the final partition also gives us the width of the poset.

4.2 Algorithm to Merge Chains in Vector Clock Representation

Assume that we have a poset corresponding to a distributed computation. This poset is represented using vector clocks for each element. Furthermore, we will assume that the given poset is partitioned into chains, corresponding to processes. The algorithm uses queues to represent the initial chains. Each queue is stored in increasing order so the head of a queue ...