A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps of finite time, regardless of the execution speeds of the other processes.
Wait-free algorithms are always lock-free algorithms. Whenever one process locks an object, other objects are forced to wait an unbounded amount of time until the first process releases that object. This causes many well-known problems (indeterministic DeadLock and LiveLock) that are completely avoided by wait-free algorithms.
Deterministic deadlock/livelock will happen consistently and predictably (i.e., you could program it to happen if you wanted to, although I'm not quite sure why you would).
Indeterministic deadlock/livelock is unpredictable. Even if you wanted to you could only cause it to occur probabilistically (i.e., run a couple hundred threads together knowing that the odd's of them escaping deadlock are about the same as you winning the lottery).
The reason for the distinction is that you can in theory program your way back into deadlocks; wait-free synchronization demonstrates that it is never necessary.