You don't need proof-of-work to achieve a consensus.
Provided that no more than 1/3 of the actors are dishonest and colluding :
Let's say that by some clever way at time t, you have 2/3+epsilon peers which signs the same database hash to certify that this is their immutable view of database at time t. As a client, you can trust a database view for which you are presented with the 2/3+ signature have been gathered.
Regarding the way to reach consensus. Seeing it from a game theory point of view : You play a game where the goal is to reach a common viewpoint by exchanging some signed messages. Whereas Bitcoin is a competitive game, this is a collaborative game.
As a protocol designer you just have to make sure that the game has a winning strategy for supermajority quorum of honest actors.
If you want to make it simple use a synchronous mechanism. The bar is really low if what you are trying to beat is Bitcoin 10 min per block transaction time (you have thousands of communications trips).
The principle is easy : Everyone exchange their info and the info they have received from others, then accept the largest union of info for which they had a supermajority telling them that they have received this union (i.e. the fixed point of function "I have received [set of received blocks]" which communications helped converging to).
If the honest actors win the round (they successfully agreed on the same thing (they can only sign one [set of received blocks] per round) ) the database grow, otherwise they leave the database unchanged and move to the next round.
There are plenty of winning strategies for a two third quorum provided bounded delay in communications ((by finite recurrence) the union of received must grow or converge during a communication trip)
Hashgraph is an asynchronous version of this collaborative game (they call it Gossiping about Gossiping) which makes it faster, needing less messages, but also harder to debug and prove correctness.
Regarding the broadcast cost, if every peer broadcast to every peer it leads to n^^2 messages but you can get around by introducing p dispatchers relaying the messages resulting to 2pn messages if you accept some additional hypothesis on the trustworthiness of these dispatchers.
The problem which still remains is how to guarantee the strong mathematical hypothesis of no more than a 1/3 non-colluding. As a workaround you can add as many verifiers as you like, so you can know when not to trust anymore, so all clients know to switch (i.e. fork) but knowing to which other set of peers but this then require a consensus :)
Gist goes into why this is sort of the wrong question. What you probably want is; how are Sybil attacks defended against? Which is the topic of one of the documents through the link.
