The bond between a lord and his men was fundamental to both Anglo-Saxon and Norman society. After the Conquest, this bond was predominantly based on the tenure of land; before the Conquest, the bond was more often a personal one, a bond of commendation. In return for the protection and patronage of a powerful man, a landowner would commend himself to him, thus becoming his 'man'. As such, he would render service, and in return hope to receive patronage and protection. The service might sometimes take the form of personal attendance and sometimes of service alongside the lord when the king summoned an army. Land need not, and usually was not, involved in the bond.
The differences between the personal bonds characteristic of Anglo-Saxon society, and the tenurial bonds of Anglo-Norman landholding relationships, are reflected in the formulae employed in Domesday Book. Norman landowner are normally described as 'holding' from their lords; Anglo-Saxon as being the 'men' of theirs.
For more detail, see F.W. Maitland, Domesday Book and beyond (1897); Carl Stephenson, 'Commendation and related problems in Domesday Book', English Historical Review, vol. 59 (1944), pages 289-310; and Robin Fleming, Kings and lords in Conquest England (1991).