The order in which powerable blocks (e.g. redstone dust blocks) along a wire are powered or de-powered is not clearly defined and causes a non-deterministic behavior for redstone contraptions

This also affects 13w10a (but not any snapshots before it), hopefully this helps figuring out what is causing this.

I also noticed this bug today and made video about it (since I though it hadn't been posted): http://www.youtube.com/watch?v=KM9DNfxBogw

Just wanted to add that I've noticed this always happens on row 0 of the x chunks: the effect can be reproduced constantly if found build a z row for every row 0 of any x chunk.

I haven't found anything significant regarding z repeptetivity yet though.

Furthermore, I've found behaviour of the activation can be diffent if coming from the side (as demonstrated in the video and images provided bu the reporter) and from the top (using block with a lever on top, activating the redstone) ie: sometimes they act the same, sometimes the switch on top works, but not the side one; sometimes the side works, but the top doesn't! The "effect" remains constant depending on your z location (respecting the x chunk rule mentioned above).

Still in 13w16a
Some love from a developer ? (Jeb ? dinnerbone ?)

Still in 13w21a

It's still there in 1.6.2 and as a redstoner I find this really annoying... if you power a piston facing down with a block on top and redstone on top of that block, there's an unpredictable chance that the piston will never retract. Same with dispensers and droppers. Can a mod please make mojang aware of this bug?

frod, the behavior you're describing is a different bug, reported at MC-108. Mojang is quite aware of these bugs.

pic of the bug that I described really bad in my previous comment: imgur.com/nLiVvG0.png

I just checked the code of 1.6.1 (and I have no reason to believe it would not be the same in 1.6.2), and the reason is indeed the same as it was years ago. It is as I described in the first comment: redstone wire signal propagation to other blocks is stored temporarily in a _hash_set and the hashing is based on the location. This gives, in practice, different (seemingly random) results in different locations/setups/orientations.

There are also other reasons for the non-deterministic redstone behavior, but they would be other issues. Since full deterministic behavior would require fixing them all, I will not provide a fix for this issue. It would be better (and easier) to simply rewrite redstone logic code from scratch.

Still in 13w36b

still in 1.7.1

Still in 06b (MC-47986)

Confirming for 1.7.5.

Confirmed for 14w20b
Please update your discription 🙂

Relates to: MC-50187

Confirmed for 1.8.

Another way to replicate this:

/tp @p 1216 17 -634

/fill ~10 ~10 ~10 ~-10 ~-10 ~-10 air

/setblock 1216 17 -634 minecraft:piston

/setblock 1216 18 -634 minecraft:melon_block

/setblock 1215 18 -634 minecraft:melon_block

/setblock 1214 18 -634 minecraft:lever 10

/setblock 1215 19 -634 minecraft:redstone_wire

/setblock 1216 19 -634 minecraft:redstone_wire

Then toggle the lever and observe the piston not retract. The same setup will retract the piston in other locations.

Aaron, this ticket is not about that issue. This ticket is about the issue that the order in which powerable blocks (e.g. redstone dust blocks) along a wire are powered or de-powered is not clearly defined and causes a non-deterministic behavior for redstone contraptions. Please check the title, the description and the video demonstration.

1.8.3 has this bug

1.8.4 has this bug

Confirmed for 1.8.7: The left setup fires all items; the right setup doesn't. This is because of either the redstone wire next to the bottom dropper or the one at the very top (I'm not sure) updating sometimes before and sometimes after their respective droppers and dispensers

Confirmed for 15w33c, not yet fixed in current 1.9 devbuilds

Confirmed for 1.9...

Confirmed for 1.9.1-pre1, pre2, and pre3

confirmed for 16w14a: pistons randomly stay extended, effect is worse when redstone is in a grid (see 2016-04-09_20.26.08.png)

This bug makes is basically impossible to power a compact water dispenser setup to break the portals in a nether portal gold farm.

still affects 16w15b

Affects 1.9.3-pre2... Interestingly, when using upsidedown slabs instead of solid blocks to power pistons below, they retract as intended...

https://gfycat.com/SlimyWellgroomedDikdik

Edit: i know why it works that way given this bug, just found it interesting and it might be a workaround for some people, given this seems unlikely to be fixed soon

@a a this is because the bug is created by budded Blocks next to the piston, not the Blocks above, so if the diagobally above Blocks are not Solid they don't create a Bud and in consequence everything works.

I also found this unresolved in 16w21b.

In addition, this odd setup also acts as a bud, but relies on chunk boarders. (red/white should be in different chunks. Replace dropper with piston for better visual)
Image:
https://drive.google.com/file/d/0BxOpmZr8Qp5cSjRkNjBySHZ3WTA/view?usp=sharing
Scematic:
https://drive.google.com/open?id=0BxOpmZr8Qp5cb19nNC0yeWpqb0k

Note that the BUD updates when either a block is placed next to the piston, or when the redstone connecting to the piston and within the piston's chunk is destroyed. This redstone placement is unrelated to the one mentioned above, since we rely on chunk boarders hear.

FWIW, I like the idea of a BUD, but I fear that the way they are currently implemented (more of a side effect/bug of lazy updates than a feature) will cause more headaches than it will solve problems (kindly put, I'm in bugy/BUDy hell). I wish they would reconsider BUD as a bug and create a new BUD block.

Fix for this is quite simple. RedstoneWire uses a non-deterministic Set to store block update positions. Just changing this to a List (funnily enough the code creates temporary lists from this set already) will fix the issue.

I suppose directional is better than completely random.

Using list will not be a good or a full fix. It could store the same block multiple times, leading to inefficiencies if not worse things. The set is used due to its "mathematical" property of storing each to-be-handled block only once.

Also, even if the list would not have random order based on block's location, it would still suffer from sub-tick issues (unless Mojang did something to these, I have vague memories of some related changes).

The first comment (mine) should clarify a bit. The real solution lies in using a separate input and output states (per block), instead of sharing single state (per block) for both input and output. After that, it doesn't matter how and in which order the logic is calculated inside a tick.

As pointed out by @unknown replacing the non-order-keeping HashSet with a oder-keeping one (e.g. LinkedHashSet) would make it symmetric regarding changes in position.
But the order would still be very directional and counterintuitive.

Also when fixing it, unnecessary block updates should be reduced (see MC-81098).

A possible way to update redstone in an "along the wire"-order and remove the performance issue on unpowering it, would be to first evaluate and set the new state of the whole wire and then cause each update just once along the wire.
The problematic case when turning off a wire that's still powered from an other source could be solved by turning off all connected wires (all that get powered by this one anyways) first.
When all of them are off they get turned back on starting from the other power sources.

I attempted to implement such a solution.
Mod: http://www.mediafire.com/download/okhobwmcj4e8jqa/1.10_RedstoneFix.zip
Code: https://gist.github.com/Panda4994/70ed6d39c89396570e062e4404a8d518
Video: https://www.youtube.com/watch?v=NEMARMNvDsw

The main goals of the implementation were:

• Reduce unnecessary updates

• Make the update order more logical and predictable

• Keep old behaviour working

Some of the changes made in the mod are simple improvements and I doubt they have downsides.
For example when the blocks around the wire get updated it used to update all surrounding blocks of all surrounding blocks and itself.
So each time a wire updates its neighbors 42 block updates are caused, while 18 of them are repetitive (17 if the update on itself is needed).
To avoid that I made a static List of Vec3i containing the offsets of the positions that need to be updated.

However, other changes are a bit weird or imply some follow-up changes on other redstone components.

• The entire wire changes its state before causing any updates.
  This quite a change but in the 1.9 update the same was done to pistons, so it seems logical to apply it to redstone too.

• Needed updates are caused first
  In the mod blocks that actually get powered by the wire get updated first.
  To do so I created a method canBlockBePoweredFromSide() which checks if a block can receive redstone power from a certain side.
  At the moment it is a bunch of instanceof-cases for all blocks that have special behaviour regarding redstone.
  If this was actually adapted it should probably be changed to be a method of Block.java that gets overridden by the blocks with special behaviour regarding redstone and works with a fancy PowerSource-Enum and stuff like that.
  There are two reasons why this is needed.
  The first one is that there are cases where updates from the start of the wire could cause changes on blocks further back, making the order of changes less logical again.

  [media]

  The piston on the right is connected closer to the power source, but without this check the one on the left would receive an update first.

• The second reason for it is that not really needed updates are caused in a reverse order and after the needed ones.
  This is probably the weirdest quirk in the mod.
  The not-really-needed-updates are updates that will only have an effect on block update detectors.
  The only reason I put them in is to keep old behaviours working. For the same reason they are in a backwards order, because that is closer to the order the recursive updates would have generated.
  I know this is a weird and specific quirk, but I found a few (very timing specific) builds that would break if the order wasn't reversed for these updates.

• The updates travel from the first UPDATED wire outwards.
  For example if there is a lever in the center of a diamond shape of redstone wire and you turn it on, you would probably expect the updates to wander out in a diamond shape as well.
  However currently the wire west of the lever will turn on first, as it receives the initial update and then the diamond shape emerges from there.

  [media]

  This is something that's not perfect with the mod yet, but changing it would require to change how other blocks trigger redstone updates.

  As the mod already works with sets of wire positions, it would be possible to make some adjustments to allow triggering the algorithm with several wire positions instead of just one.
  So all wires around a lever could be added to the set, before the algorithm starts working.
  In case this idea would be considered, there might be many more elements on the lists in some cases.
  So it might be necessary to replace the current use of lists and contains calls as set with a remove-first-method with something with a less expensive contains implementation.

• The updates around a single wire also follow a closest-first order.
  This is not so much a problem than rather a logical conclusion from the decision to make the update order logical.
  But it feels inconsistent with how other redstone components currently update their surrounding blocks.
  So I think if this fix was used, other redstone components such as repeaters or torches, should use an update order following the same principles.
  However this would break quite a few old designs, as repeaters and torches already follow an order. (Other than redstone wire for which the order was basically random before, which gives the freedom to just decide on a good order without breaking designs)

This is the main concerns I have with this fix, but I would like to get some feedback on it.
Also I would be interested in finding designs that worked position independent before, but won't work in the fix. I tried quite a few huge and fast builds, but the only things that broke were positional before, so it's unavoidable for them when fixing this bug.

... and, by the sound of it, Panda is approaching towards both the proper solutions I suggested in the first comment.

"to first evaluate and set the new state of the whole wire and then cause each update just once along the wire." is at least part of the case 1; the idea is to store all "current state" separate from all "next state", then change all the states at once. Apply this to the whole block set reachable via blocks (or other effects, should there be some day things that cause effects instantly "over the air") that will or can change state within the same tick.

And "As the mod already works with sets of wire positions, it would be possible to make some adjustments to allow triggering the algorithm with several wire positions instead of just one. So all wires around a lever could be added to the set, before the algorithm starts working." would be part of the case 2, even if it doesn't use the same terms or data structures. Idea is to build a directed graph of connections between affected/affecting entities (or groups of entities to simplify e.g. wire handling). The minor challenge is to keep that graph correct when the things change (or chunks get unloaded/loaded), but the actual runtime simulation becomes near trivial.

It really would be easiest simply to go full throttle with the EE-simulation basics; all the current problems would be gone just like that. Bad sides could be memory use (depending, it might still be insignificant compared to everything else, and in some cases could even use less memory), and how to implement it with the dynamically loaded/unloaded chunks (i.e. circuits can be "cut" but should still do something with the parts that are loaded).

Also, I haven't given a single thought on trying to keep weird existing behaviors intact (like BUDs and such); keeping them "as is" might require some extra rules, like exceptionally using other "next state" info as input data when calculating some block type's output "next state", etc.

All that said, nice effort trying to tackle this bug, Panda! I welcome any and all changes that improve things, even a bit, and removing the non-deterministic things is a big step.

Noticed suggestions being tossed around on this in my email. Conceptually dust has no timing, so a segmented list of dust structures would make more sense. If a dust segment/structure gets activated all input components on its list get an update scheduled in the order of distance from the activated output. In certain situations this would cause significantly more memory usage, yet, those situations should be rare. Sorry if my explanation is unclear. Communicating my thoughts is becoming increasingly more difficult.

This ticket would be so much less serious if MC-108 wasn't a thing: the green-and-purple-wool example here and MC-105150 wouldn't be problems. Conversely, MC-108 is made more confusing to learn as a "useful feature" by this bug because it always seems to crop up near quasi-connectivity. The 2 bugs together cause many more problems than each individually.

My ticket (105937) was flagged as a duplicate of this one, so I'll add to this.

https://twitter.com/SirMrDaisyBates/status/762842999189417984

Above is the video of it I posted on Twitter.

I was in the process of building the Iron Titan in my single player world. I built it to spec and followed TangoTek's 1.9+ updated design.

Using the original design, the dispenser seemed to fire correctly. Once I upgraded to the design he suggested for 1.9+, the dispenser would fire only one time after applying the redstone dust. After the very first time, it would never fire again despite it receiving a pulse. The interesting thing was, if I broke the dust and replaced it, it would fire correctly upon the next pulse, yet it would not fire again after that one time. The same was also true if I extended the redstone dust to the next block over (updating the dust that way seemed to make it fire successfully one time, then break).

I did my best to look over the build. I haven't seen any indirect powering or anything like that that may possibly lock the dispenser some how (though I'm not too great with indirect/bud stuff). I'm baffled.

I did do a fly around of it towards the end of the video. I receive the same results with or without optifine, so I do not believe it is a factor.

I'm glad you're working on this.

Wow, Mojang. Any idea when you're going to get around to fixing this THREE YEAR OLD ISSUE!!!!

The age of the issue has nothing to deal with how soon it can be fixed. This issue in particular is very hard to fix (and will probably require a major rework of most of the redstone code). It's not like you can just say, "I want to fix MC-11193" today, and it'll magically be fixed.

I think this is the effect of BUD pistons because since BUDs don't realize that they are powered until a block update is performed, the BUD will be stuck in its current position, if it was powered it will remain like that and since in the video presented does not place a block beside the piston and a block near it is powered, it won't realized its powered state.

@Mark Jovelle C. Sulibaga: If you read the part above the conclusions, you'll see that the cause was never questioned - the problem is the "randomness" of the unpowering order of redstone dust causes problems

Confirmed for 1.12.2

I believe this is the bug that adds the unintended "BUD" feature with pistions which is much loved.

No, that’s MC-108.

Hi,

I have uploaded a fix for this bug. Please find that and an explanation on MC-81098.

Thanks.

This appears to be partially fixed in 18w01a, can someone who has enough knowledge about how this works check please? It still looks weird to me, but that might be caused by QC, I'm not entirely sure about that.

I can't see any substantive changes

affects 18w16a

Random order of updates to redstone dust still exists in 1.13-Pre4

Still in 18w31a

Also happens in 1.14.3 I had a hard time figuring out what's going on before I found this report. It's also a diagonal going on here but what I find interesting is that the comparator clock for the hopper dropper works on one side but not the other, possibly due to update order. Manually I found out that by extending the wire by one it changes the behaviour https://www.youtube.com/watch?v=LyFJE-DIMtQ

Sven
The 'random' redstone dust update order, does cause the dropper to be budded sometimes but not other times
Droppers and dispensers can be QC powered like pistons

See YouTube video https://youtu.be/wVJDz0ca7Ps. Time stamp at 1:50. 

Matt, that video applies to Bedrock Edition. This is a Java Edition bug.

Yes but he is saying that
NO! java should NOT have random redstone
It is a terrible idea, directional is much better
and theres many different things that can be coded to reduce the directionalness

One simple method to make redstone wire update in a more predictable manner would simply be to stop using the `toUpdate` field of `net.minecraft.world.level.block.RedStoneWireBlock`: instead of adding the positions to be updated to a set which is later iterated over and then cleared (note that the only uses of `toUpdate` are in `updatePowerStrength` and `updatePowerStrengthImpl`), simply update the positions as they are found - call `Level.updateNeighborsAt` once with the position of the dust, then once per Direction, utilizing the loop in `updatePowerStrengthImpl` that currently adds the positions to the `toUpdate` set.

I could create a patch showing these changes, but I'm not sure how useful it would be since it's deobfuscated code, and am also unsure about whether or not it violates the EULA

Would that decrease performance? I think this collection and later execution of updates is done so that redstone dust doesn't keep updating itself hundreds of times over whenever you e.g. depower a line from 15 to 0. (It still does that a lot, but less than it would with regular block updates only.)

The "update as positions are found" was suggested already by the ticket description, which I sort of debunked in the first comment...  I and Panda have given couple ways to handle it properly. (And hint, there is no "simple" way to solve it properly, although what is and isn't simple may vary from developer to developer.)

About showing code here. I haven't seen any solid official guide in what is and isn't allowed in that regard, but I've shown quite a bit code snippets in here, with no trouble so far. And at least one fix I have shown here has even been used by a developer (with confirmation in the issue's comment). However, I limited myself to relatively small snippets, at most full medium sized functions.

Also note that large part of mod development would already break the same EULA rules, so if they want to kill source code snippets here, then for equality good bye mods...

Perhaps I'm misreading the code, but as I see it, updatePowerStrength and updatePowerStrengthImpl could be merged into one method, with toUpdate being a local variable (which would be slightly slower than having it as a field, my point is just that it could be done).

Since the blocks which get added to toUpdate are the same every time, and none of those will be the same as any other (they're the redstone wire block and the 4 blocks in each cardinal direction from it), I see no reason to store them in a HashSet at all.

Again, I may well be reading the code wrong and it's much more complex than I think.

I haven't read the relevant code in years, so things could have changed over the time, and/or I could remember wrong... but, trying to read between the lines, it seems that if there have been changes, they haven't been the kind of that would have been needed. So, what I say may miss the mark, but should still give the idea(s) behind it all.

The hashset of blocks to be updated can hold more blocks than just the one and its neighbours. (Or at least it should, otherwise it would indeed be pointless.)  Note that while the blocks have class and object, the object (or class) is used as a "representative", not for individual blocks. (Or at least that was the way it worked back then, IIRC.)  Thus, a field in the object (let alone in the class) is actually shared by all blocks of the same type (or aboutish, depends on the particular code).

The point of that set is to collect all the to-be-updated blocks/positions into one collection, with no duplicates (it is a "set" after all). The travel through the propagation of redstone effect on a wire can branch and rejoin many times, so each block can be seen multiple times. If not done via a set, there could blocks that get updated multiple times during a tick, and depending on the block type, that could then spread further.

Also, while I don't remember whether it was the same set or another, there is a need to check if a particular redstone block has already been handled during the same tick (to avoid infinite loops and for efficiency).

The problem in this issue is (partially!) specifically due to the way the set works and is used; the order in which the contents of the set can be gone through is not the same in all cases of an identical circuit (not only as a hashset implementation can validly have randomness in its working, but also due to how the hash-value is calculated for the blocks in this purpose). And due to the way the redstone logic updates are handled, the order in which the changes happen to various blocks during a single tick can lead different end results. Additionally sometimes affected by non-redstone based updates. (The sub-tick quirks have been abused for various purposes over time, too, so.. fix this problem, and break a few circuits.)

Read Panda's long comment which notes about LinkedHashSet; it would reduce some of the overall causes, but not all.

Read my and Panda's comments through to get a better idea how much is needed to get it done properly. It is not really that difficult, but it is not a small change, either.

I think you may be out of date. updatePowerStrengthImpl is the only place where toUpdate is modified, and performs no recursive calls that I can see. updatePowerStrength clears toUpdate directly after calling updatePowerStrengthImpl which, as you say, makes the set pointless.

There may be a hidden recursive call I'm missing, however.

Just to make sure I wasn't being an idiot, I wrote a mod using my suggested fix. It seems to work fine, but I've not done particularly extensive testing. If anyone feels like playing with it, the code is here: https://github.com/vktec/wire-order-fix

A JAR file for 1.14.4 Fabric can be downloaded from here if you don't feel like compiling it yourself: https://github.com/vktec/wire-order-fix/releases/tag/0.1.0

This is now happening as for snapshot 20w18a.

(Didn't see this ticket when created MC-181606 but it seems essentially the same)

I personally feel that you can divide this problem into two different categories. One is the more “literal” one, in that stuff happens in a different order depending on coordinates. The consequences of this can be seen in command blocks triggering in different orders or that a dropper chain sends an item a different distance when all power on. This is a natural result of the sequential nature of computers and will never quite go away. The focus should therefor be to fix the second category, although my suggestion for a solution would make even the first category more manageable.

Edit: To clarify I don’t mean that the update order is impossible to make in a predictable intuitive way, just that because of how computers work (sequential) it would be difficult without drastically increasing the amount of calculations required. At that point the cost can quickly outweigh the gain. So not impossible, just impractical.

The second category consists of the situation where the update order causes unpredictable inconsistencies in redstone. Quasi-connectivity is the origin of a large part of these and can cause pistons or droppers/dispensers be BUD-ed (typically on falling edge) for seemingly no reason. This should be a priority to fix, as they cause confusion for the player and can often break contraptions. I do believe some of the inconsistencies with how repeaters and comparators handle fast clocks (some cases signal propagation, some cases off and some cases on) could also be put in this category (not sure).

My suggestion to fix this is to create a better-defined order of (redstone) updates. As far as I can logically think the order should be something like this

1) The empowering components. Redstone torches, comparators and repeaters that are tagged for change does that. Affected blocks/components are queued for change.

2) The blocks that becomes strongly powered or looses said state gets updated. Affected blocks/components are tagged for change. If a component like a dropper gets powered at this stage, it only acts like a solid block at this stage and is queued for change as appropriate.

3) Redstone wire gets handled. Queue appropriate components for change.

4) Weakly powered blocks updates.

5) All components that cause block updates (that have not already been checked) should be noted, and all components that are updated should be queued for execution (but not actually done yet). Do this recursively so that everything is queued for execution.

6) Execute the behaviour of all the components queued for action. As it is only at/after this stage pistons and dispensers can influence the world, no consequences of those action should have been handled.

7) If the world has been influenced (pistons moving a powered block etc), repeat the steps. They should keep repeating until they are done, as things like instant (falling edge piston) signals requires multiple loops. The game should already be free of potential closed loops.

Edit: To clarify the only two blocks that can change the state of the world in such a way that I can see are dispensers (can place certain blocks, blocking redstone wire or getting strongly powered) and pistons (moving a powered block, moving a block blocking redstone wire over an ledge). The dispenser uses 2 redstone ticks to activate and can therefore not be looped this tick. The piston starts moving the same tick, and moving blocks loses their ability block or power redstone, and therefore instantly cause a change. As I understand it the blocks would only return to solid blocks in a future tick and can therefore not be looped. So, while long chains are possible, loops should be impossible. Exactly where in the process the dispensers place the block or the moved block turns solid should also be considered. Note that I included this last step to conserve 0-tick behaviour. If it is a bug rather than a quirk (like quasi-connectivity), simply dropping step 7 should remove all 0-tick behaviour I can think of as the change only gets registered the next tick.

I believe this loop would keep the behaviour more constant (no variable BUDing) while staying mostly the same (for example 0 tick pistons and pulses should still work).

In addition, I believe it is sensible to instead of activating all components in the order they where detected, to separate the different components into their own queues (one queue for droppers, one queue for trapdoors, one queue for both piston types). While the update order within each queue is the same as it is now (if only there was components of that type), but create a known hierarchy between the different. For example, fire all droppers before any dispensers fire. The result of this addition would be a much clearer update order, something that partially fixes the first category problem. It would also lower the skill celling for working with these timings benefitting casual(ish) players. Note that the hierarchy and content of the queues is important and should be thoroughly considered. For example, droppers should activate before dispensers as droppers can be used to move an item and using it the same tick. Likewise, both pistons types should be in the same queue to conserve loads of currently vital behaviour. And depending on if pistons are prior to dispensers the behaviour could differ, although if the steps mentioned above are followed using pistons to (de)power components in different loops the order can be accurately manipulated.

To implement this in the code I imagine "all" you need is to fill different FIFO queues with blocks/wire/components to power. If something powers something handled in a different step, put it in the appropriate queue. A wire on top of a dispenser should queue it in both the ‘weakly powered block queue’ to see if something reacts to that, and the ‘dispensers to be activated queue’. Redstone wire powering redstone wire are both on the same step, and don’t need to be queued. The idea is to have a ‘detect all, then execute all’ approach instead of the ‘detect execute repeat’ approach it seemingly has now (could be completely wrong there. Don’t know any Java nor the inner workings of the game).

Although some of the more advanced contraption that are orientation dependent probably would break, a more well-defined update order would make it easier and more predictable to redesign most of them. It would remove inconsistencies and make the process more beginner friendly, all while staying mostly the same as now. And lastly it would offer more manipulation of chain of events for advanced players opening new possibilities. So, in total something I think would be worth implementing.

TL; DR: This problem has a “everything happens, but in a location dependent order” part and a “things can get BUD-ed dependent on location” part. I personally think the BUD part should be a high priority to fix. My suggestion to do that is to have a component-dependent update order. First things that gives redstone power (repeaters, redstone torch, comparator), then strongly powered blocks, then redstone wire, weakly powered blocks, and lastly activate the components. If something changed the same tick (e.g. piston moving powered blocks) repeat. The different components with behaviour should have a strict order of activation (like all droppers activate before any dispensers do. Order among in a single category can have a similar order as now).  

I hope this ramble could be of some help or inspiration, and don’t only make sense in my head.

Edit: Some grammar fixes (although i still think redstone has its tics as well 😛)

The good:

The BUD problem is a valid statement, BUDs should be deterministic regardless of coordinate, and fixing that first, will greatly simplify the rest of this problem.

The bad:

The idea that a circuit cannot be emulated properly regardless of coordinates is provably false. There are numerous circuit emulators out there that work just fine regardless of where you drag the components around in their UI. A "computer" incapable of deterministic operation is a worthless device.

I think we do need (at least) three separate passes on all redstone components in a circuit to do it properly, but the idea that it can't be done is absurd.

 The funny:

If something changed the same tic*k* (e.g. piston moving powered blocks) repeat.

$10 says I can use this piece of your proposed patch alone to send your server into a CPU-hogging infinite loop and never tick again.

Replies to @unknown:
1. "stuff happens in a different order depending on coordinates" is not an unsolvable problem. Hard, but not unsolvable. That things happen differently depending on rotation is unsolvable in some situations, for example if you power two pistons facing each other with only one block gap in the middle at the same time, then rotating that contraption by 180° would of course change the result, because you arrive at the same situation, just with the two pistons having switched places (let's say they have something to keep them apart, like sticky or not). The only thing you could do against this would be the MCBE strategy: Randomness. I don't personally think that this is a good solution, but there are different opinions on this. See also this video by Panda: https://www.youtube.com/watch?v=aRr3NpmQiCg
2. Note that 0-ticks are considered a bug: MC-8328 But it might be impossible to fix all cases of them.

Reply to @unknown: At least currently you would probably get a StackOverflow, which is already sometimes used for update suppression, but that's a bug as well. The solution is obviously to let every redstone component and physical mechanism have a delay. 😛

Not all redstone components/mechanisms need to have a delay of game ticks (or similar). Delay is essentially just one way to achieve input-to-output separation and thus (mostly) correct logic.

Another way to do it is what had been proposed ages ago, which is to separate current and next output states. As long as any (sub-tick) calculations are still going (and optionally some time-limit has not been exceeded), output states would not be changed (except if a component is defined to be instant, like redstone wire, but such component needs to have logic/behavior that is safe for the instant processing, not leading to oscillation). Once everything is done and stable, flip all outputs (without starting to process/propagate updates yet) in one go. Then repeat in calculating how the new state changes things (those updates propagating to inputs), while holding outputs fixed. This way it should also at least reduce, if not eliminate any position/orientation dependency, except in cases like the symmetric pistons etc. where the nature of the situation is such that it really should be more or less random (equal rules fighting each other..).

The above description is actually effectively also a delay, but it is a dynamic one; it only lasts as short or long as the propagation needs, not some specific quantity of "ticks"... except if specifically delayed to a desired time resolution. E.g. by starting the round of processing, or by doing the output flip part, only once per tick, then one gets the ideal version of current behavior; things would change once per tick (or sub-tick or whatever proper unit is/was for redstone), but would do so without (time/order/position/orientation related) quirks.  It may or may not cause issues with BUDs, though, depending on which kind of rule/mechanism was making such BUD to work as it does.

The "optional time-limit" I mentioned matters. If no time-limit, all redstone operation slows down when there is too much stuff going, but its logic works correctly (except for timing vs. other systems, like physics of flying/dropping items). With a processing time-limit, redstone works as fast as usual even under load, but at heavy load something may need to be left unprocessed before the outputs are flipped, which leads to incorrect operation. Which way is better depends on the particular system/needs.  I am not suggesting such option should be added, or which way is better in general, I only mentioned it as it affects the result and it can not be left undecided.

Response to the comments from @(Fabian Röling) and @(Pegasus Epsilon) 

1)  To clarify I don’t mean that the update order is impossible to make in a predictable intuitive way, just that because of how computers work (sequential) it would be incredibly difficult without drastically increasing the amount of calculations required. At that point the cost can quickly outweigh the gain. So not impossible, just impractical.

2) As I understand the game it should be impossible to create loops in the last step. The only two blocks that can change the state of the world in such a way that I can see are dispensers (can place certain blocks, blocking redstone wire or getting strongly powered) and pistons (moving a powered block, moving a block blocking redstone wire over an ledge). The dispenser uses 2 redstone ticks to activate and can therefore not be looped this tick. The piston starts moving the same tick, and moving blocks loses their ability block or power redstone, and therefore instantly cause a change. As I understand it the blocks would only return to solid blocks in a future tick and can therefore not be looped. So, while long chains are possible, loops should be impossible. Exactly where in the process the dispensers place the block or the moved block turns solid should also be considered.

3) I thought 0-tick pulses was a quirk (like quasi-connectivity) rather than a bug, and specifically included the last step to conserve it. Simply removing that step should remove all the cases of 0-ticks that I can think of, because affected wire/components only would ‘see’ that something had changed the next tick.

I updated the main text to clarify.

Edit: Some grammar fixes (although i still think redstone has its tics as well 😛)

The delays for everything were a joke (as indicated by 😛). If every component had delays, it would make everything extremely slow and not even fix this bug.

"It may or may not cause issues with BUDs" All BUDs except observers are fundamentally based on bugs, so that's not a problem.

A time limit after which every remaining update is skipped is definitely a bad idea, because it leads to infinite possible problems that cannot even be reproduced properly and are also unfixable.

Do you have an example of a contraption that is locational and would be computationally extremely inefficient to make non-locational? I can't imagine any reason why that would be the case.

BTW, it's "tick", not "tic".

— "It may or may not cause issues with BUDs" All BUDs except observers are fundamentally based on bugs, so that's not a problem.

Except that breaking BUDs is something people (including Mojang dev(s), IIRC) have used to justify not fixing a clear bug, so it can be a problem (for one or the other group of people). I've even given suggestions that would result in having both BUDs and properly working redstone logic.. to no effect. I gave up years ago on trying to use proper reasoning and good programming habits/rules when it comes to Minecraft development.

— A time limit after which every remaining update is skipped is definitely a bad idea, because it leads to infinite possible problems that cannot even be reproduced properly and are also unfixable.

IIRC, those maaany years ago when I last went in the code, there was a limit on how many updates could be queued, after which either oldest or the latest were simply dropped (not processed), which essentially leads to similar behavior as a time-limit. I.e. incorrect operation, in a random way, not always reproducible.  At least my largest redstone things at the time definitely behaved badly when everything was turned on at once.  So, I'm not sure if that is (or was) really so bad idea (at least in Mojang's view).

In a more practical way, having a time-limit (or another process limiting method) may allow something to work well and fast at least sometimes (say, a simple automated door, keeping you safe from the mobs), while without limits the logic will be correct (door will open/close.... .... ... eventually) but its desired function will not be "correct" (to keep you safe).  I.e. both ways have their pros and cons.

@unknown
"breaking BUDs is something people (including Mojang dev(s), IIRC) have used to justify not fixing a clear bug"
Well, that's bad then. Was that before observers existed or after?
Also, Mojang sometimes changes their mind. MC-9405 was "won't fix" at first and then it was fixed (that snapshot even got released while the report was still marked as resolved). And whether MC-108 is a bug or a feature depends on which dev you ask, on what day, at what weather seemingly, …

"I gave up years ago on trying to use proper reasoning and good programming habits/rules when it comes to Minecraft development."
You shouldn't. Just because many people ignore best practises doesn't mean they should be ignored by everyone. It is already the case in most software projects that most best practises are ignored by most people, but every bit helps.
The thing is, BUDs (without observers) are based on bringing something to an "invalid state" and then detecting when the game finally notices and auto-fixes it. Sounds like the prime example of "bug-using" to me.

"without limits the logic will be correct (door will open/close... eventually) but its desired function will not be correct"
So you mean after the limit is reached, block updates will be moved to the next tick? That is less bad in some simple cases, but those simple cases already aren't a problem for performance anyway and the more complicated cases would completely break with it.
BTW, this report is not about performance.

@unknown You can tag people with

[~name]

, but that only makes it link to the profile and it updates the displayed name when the person's name changes, it changes nothing about notifications or similar.
Also, the "preview" button is sadly gone, but you can use Ctrl+A Ctrl+C to copy your text, click the "visual" button to see how it looks and then switch back to "text" and restore everything that the visual mode messed up (which it sadly often does) with Ctrl+A Ctrl+V. Your many edits causes 105 times as many mails to be sent, that's multiple thousands in total from this conversation today.

"without limits the logic will be correct (door will open/close... eventually) but its desired function will not be correct"
— So you mean after the limit is reached, block updates will be moved to the next tick? That is less bad in some simple cases, but those simple cases already aren't a problem for performance anyway and the more complicated cases would completely break with it.
— BTW, this report is not about performance.

TLDR: the main point was the separation of "current" output state and the "next" output state. The tricky part is when that "next" gets applied to be the "current" (and is something I won't dare to emphasize one choice over another).

I was considering the situation where there are both simple mechanisms (say, that door) and heavy systems in the same area. In such a situation it does get messy no matter what, though.  Of course a few simple things alone will work well in (almost) all solutions, even with the current little bit borked solution.

The idea with time-limit is to continue processing changes from outputs to inputs in the next cycle of calculations, but any already accumulated output changes would be applied first at the next cycle. If the output changes are not applied like that (after time-limit), the behavior turns back into the same as without time-limit, just perhaps causing slightly less effect on rest of the game (physics, reacting to user-input, etc.), just like with any other properly designed throttling mechanism for heavy load handling.

The time-limit idea is to simply stop processing further redstone calculations during that cycle (whether that is a tick or some other time period), flip the outputs (where necessary), and on the next cycle continue either from "begin" or where the processing was left at (another choice to make, with different pros and cons). This way at least something happens somewhat smoothly under heavy load, though it can not be said what exactly will be smooth and what will not. (I would have ideas even for that last "problem", but that goes waaayyy in the land of feature request.)

Time-limit is of course not the only way to manage overload situation.

I know this report isn't about performance, that is why I don't even suggest any choice over another. I mentioned the time-limit so as to let everyone know about the possible issues remaining even with my suggestion towards fixing this issue. (So that nobody can outright deny the approach by saying that I forgot that it will break under heavy load (as if the current one wouldn't), etc.)  Also, when it comes to time-limit, the logic works a bit differently when using the next state buffer vs. the way where every change is applied to world immediately. E.g. in the easier/current way (no next output state buffer), a time-limit wouldn't really make a difference in the outcome.

May I suggest that, since this is a very followed issue, And a lot of people is watching the issue, perhaps further discussion should be moved onto the sub-reddit thread 

Hi, I was considering submitting a bug report for some really weird behavior breaking a dispenser hopper T flip-flop, but found this issue and wanted to check that it isn't caused by the same bug.

I think this simplified setup using pistons demonstrates the problem clearly:

I have the exact same configuration for both sides, and am expecting the same result (that the top piston fires "first" preventing it from being moved).

However this doesn't occur for the pistons on the right (shown above), but does occur for the pistons on the left (shown below)

This does appear to be location dependent (although not in any pattern I can figure out) and replacing the pistons for droppers results in the same issues.

confirmed for the snapshot 20w49a

Still an issue in snapshot 20W51A

Still an issue in snapshot 21w03a

Relates to MC-11613

Can confirm in 1.17.

Can confirm in 1.17.1.

Mojang its been 8 years, i feel like the priority of this notorious bug should be higher than "low", some redstone contraptions just do not work because of location, and thats just bad.

also its confirmed for 1.18 experimental snapshot, but idk if its important since its experimental and all

Thanks for the nice explanation, this helped me to find a workaround for the bug. If you want to expand/retract a couple of pistons connected to a power line, don't connect them directly to the power line, put a repeater between each piston and the power line, then they reliably retract, if you switch the power line off. But I have to say, this feels stupid, waste of material and space! Either they should skip the BUD "feature", or add some synchronization, but together these two are a fatal combination! I noticed, that sometimes powered rails stay powered on too, when you switch off the power, is this related to this ?  

The rails thing is MC-957 and happens because they don't have the power states that redstone has.

can confirm in 1.18.1