Unique Media Access Control (MAC) addresses are determined for dynamically addressable synthetic and physical network devices by requesting a MAC address anonymously from a server acting as an address allocator and arbiter, confirming the use of the requested MAC address, and relinquishing the address to the server for reuse when the MAC address is no longer needed. Alternatively, an agent with a known or established MAC address may be used to request a unique MAC address for the device from the server and to inform the server when the device no longer requires the requested MAC address. Also, instead of requesting a MAC address from a server acting as an address allocator and arbiter, the device instead may send a broadcast Ethernet packet with a broadcast source address having a payload indicating an intent to use a specific MAC address. If another device receiving this broadcast is already using the specific MAC address, then a broadcast packet is sent indicating a conflict with the device's intended address. In this case, the original device would send a new broadcast Ethernet packet with a payload indicating an intent to use a different specific MAC address. This process repeats until no response or assertion of use of the specific address in the payload is received by the original device. These techniques assure that dynamically addressable synthetic devices (such as virtual machines) and physical network devices do not attempt to use the same MAC address on the same network link.