Ethereum is a great blockchain, but for some services the transaction fee is prohibitively too expensive. Is there any project and/or guideline on making Ethereum so it works on permissioned blockchains - i.e., with the consensus algorithm and mining replaced by majority vote? Would a simple fork of the network work fine, or is there any reason this wouldn't work?
Yes, Quorum is one open source example.
The Ethereum wiki has a detailed section on Consortium Chain Development including suggestions for consensus algorithms:
In a private chain context, there are three consensus algorithms that make the most sense:
Proof of authority - essentially, one client with one particular private key makes all of the blocks
PBFT (or some other traditional byzantine-fault-tolerant consensus algorithm)
DPOS (or some other chain-based limited-validator consensus algorithm)
Regarding P2P Networking:
A private chain may want to either use the same networking code (but with a different network ID set in the config file), or use an alternative type of network; the most likely alternative is a design where every node connects directly to every other node (quite feasible and likely optimal in networks with under ~20 nodes).
Regarding transaction fees, it highlights:
Important note: "gas" and "ether" are NOT the same thing. Gas is a mechanism that allows computation inside the EVM to be deterministically metered, ie. for contracts to deterministically restrict calls to some fixed number of computational steps. Ether is a way of paying transaction fees, which are expected to be proportional to gas consumption. The Bitcoin analog of ether is BTC, the Bitcoin analog of gas is the number of bytes that a transaction takes up in a block; in Ethereum, measuring bytes alone is not enough as you also need to measure computation, hence the concept of gas. On a private chain, you do not need to use ether to pay for gas; you can come up with alternate rulesets, including for example simply requiring every transaction to have a maximum gas limit of 1 million.
You can use HydraChain (https://github.com/HydraChain/hydrachain). It is a permissioned blockchain based on Ethereum.
Take a look at Monax (formerly Eris). They were IMO the first ones to explore private permissioned chains with eris:db and the system is compatible with Ethereum as they use the EVM and Solidity.