Paxos provides strong consistency and can proceed even if some nodes fail. 2PC has intermediate states in which a transaction is only partially committed, and all nodes need to be available to perform writes. The downside is that Paxos' write throughput is bounded by network latency and it requires network round-trips on both reads and writes. 2PC is more suitable when you require low read latency or high write throughput.

> Does this only work for append only unique data structures (ex: immutable log style)?

Paxos is based on a technique called state machine replication. It replicates an append-only log of changes to an initial state, which allows you to replicate arbitrary data structures. For example, pg_paxos logs SQL commands on a table (e.g. UPDATE).