Distributive Lattices

Distributive lattices form one of the most interesting class of lattices. Many lattices that arise in distributed computing and combinatorics are distributive. The set of all consistent global states in a distributed computation forms a distributive lattice. The set of all subsets of any set forms a distributive lattice under the subset relation. This chapter discusses some of the crucial properties of distributive lattices. It provides a characterization of distributive lattices using forbidden sublattices. The chapter discusses a duality between finite distributive lattices and finite posets. Every finite distributive lattice can be recovered from the poset of its join-irreducible elements. This result due to Birkhoff, is known as the fundamental theorem of finite distributive lattices. The notion of join-prime elements is useful in the characterization of finite distributive lattices by Birkhoff's Theorem. Birkhoff's Theorem requires the distributive lattice to be finite.