An old article: "A Machine-Independent Linker"

Fraser and Hanson gives a mathematical definition as a termination condition of symbol resolution process. In this paper, they classify symbols as follows.

• R - a set of symbols referenced in object codes
• D - a set of symbols whose values are defined in some object code
• S - a set  of symbols that identify segments

An object file for which

R is a subset of the union of D and S

is said to be resolved.

The definition means that every undefined symbol has a corresponding defined symbol.

In MCLinker, we treat symbol resolution in the other way. MCLinker IR is a reduced graph of the use-define chain in typical compilers. An undefined symbol with relocation identifies the location of a `use`, and a defined symbol identifies the location of a `define`. Symbol resolution is a process to finish the topology of the use-define graph by connecting all defines to all uses. The termination condition of symbol resolution process in MCLinker is set if and only if every `use`s has its corresponding `define`.

Reference

@article{FraserH82,
  title = {A Machine-Independent Linker},
  author = {Christopher W. Fraser and David R. Hanson},
  year = {1982},
  researchr = {http://researchr.org/publication/FraserH82},
  cites = {0},
  citedby = {0},
  journal = {Software: Practice and Experience},
  volume = {12},
  number = {4},
  pages = {351-366},
}