Japanese Wikipedia article page for link-local address mentions that the creation of link-local address is almost always indeterministic (非決定論的 in Japanese). The corresponding English page does not contain an equivalent statement.
My questions are how APIPA is implemented and how the candidate address is selected (or calculated). Is it really an undeterministic algorithm?
RFC 3927 is the specification for how it should be implemented. It has a section 2.1. Link-Local Address Selection which specifies the usage of a PRNG and recommends that the PRNG should be seeded using the same initial value (e.g. a MAC address) every time.
PRNGs are deterministic – their only source of randomness comes from external seeds; reinitializing the same PRNG with the same seed will always give the same sequence of outputs (hence pseudo-random). So any APIPA implementation that uses a MAC address as its PRNG seed should also generate the IPv4 addresses deterministically.
The pseudo-random number generation algorithm MUST be chosen so that
different hosts do not generate the same sequence of numbers. If the
host has access to persistent information that is different for each
host, such as its IEEE 802 MAC address, then the pseudo-random number
generator SHOULD be seeded using a value derived from this
information. This means that even without using any other persistent
storage, a host will usually select the same IPv4 Link-Local address
each time it is booted, which can be convenient for debugging and
other operational reasons. Seeding the pseudo-random number
It is not possible to know whether all APIPA implementations follow this recommendation except by testing them experimentally (many of them, such as the one in Windows, are closed-source). If I remember correctly, Avahi on Linux is compliant.
As one differing example, I seem to remember that the implementation used by Ubiquiti's airOS firmware is specifically called out in the device docs as directly using the device's last two MAC octets as the initial APIPA address (being somewhat noncompliant but nevertheless deterministic).
From RFC 3927:
This means that even without using any other persistent storage, a host will usually select the same IPv4 Link-Local address each time it is booted, which can be convenient for debugging and other operational reasons.
Note the usually there. The PRNG is used to generate a sequence of IP addresses, and the device chooses the first address from that sequence that isn't claimed by another device. This means that the result is path-dependent. Even if all devices seed their PRNGs deterministically, in case of a clash the results depend on the order that different devices come online and claim addresses. If you turn everything off and then bring it up again in a different order than the last time, the results may be different. Even just changing the relative order of two devices may create a chain reaction that causes any number of devices to receive different addresses (although this is statistically quite unlikely unless you have thousands of devices on the same network segment).
So is this deterministic or nondeterministic? That totally depends on the view you take of the system. The narrower view is that algorithm is deterministic — it will make the same choice every time given the same inputs (i.e. the same seed and the same set of currently-online network peers).
But if we take the view that the network consists of a collection of devices with various seeds (some of which may be unknown to us), which join and leave the network at unpredictable times, then we come to the conclusion that we can't predict with certainty what address any device will have at any future time. We can only figure it out at the moment of assignment by taking census of the network. In this sense, automatic IP assignment is nondeterministic, because it depends on nondeterministic outside factors (like people walking in and out of the building with their phones and laptops).
