I'd think sending multiple packets (parallelism) with varying TTLs (1,2,3..n) without waiting for responses from each hops to increment the TTL, would probably give us faster traceroute. n being the number of hops you "expect" the destination subnet to be.
Not really. You'd want every routers in the path to reply to see all the hops in between. This would be unreliable though, since the ICMP TTL exceeded message might come in out-of-order to the sender, who is sending these probes(with varying TTLs) simultaneously. But assuming, you could somehow figure out the hop-order, this IMO is faster than current traceroute implementation.
