O'Reilly logo

Introduction to Lattice Theory with Computer Science Applications by Vijay K. Garg

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 c04-math-0001 is partitioned into c04-math-0002 chains, c04-math-0003 corresponding to c04-math-0004 processes. The algorithm uses queues to represent the initial chains. Each queue is stored in increasing order so the head of a queue ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required