text:
# SpatialOS single shard MMO

## Recommended Posts

drainedman    104

Has anyone tried SpatialOS?

I'd like a different perspective I don't pick up a lot just by thinking about it myself.

Is this stuff quite similar to Pikkoserver though?

Are workers/services really the way forward. I don't see any detailed explanation or case studies, just presentations.

##### Share on other sites
khawk    2924

I know of two members here who may be able to help, and there may be more but I'll tag them. @JWalsh's studio Soulbound Studios has partnered with SpatialOS.

@riuthamus was talking to them at one point as well for their Greenlit game, but I don't know if anything came of it. Perhaps there are others.

For large scale simulation SpatialOS is probably a strong future since it's based on the fundamental concept of distributed simulation architectures. Pikkoserver sounds similar, but to be honest I had never heard of it until your post.

The concept that SpatialOS provides has been around a long time. In the simulation world, distributed simulations are a common architecture. SpatialOS takes that idea to the next level by moving the distributed concept to "the cloud", where computation is relatively cheap and easy to scale. They then take that to the next level with gaming by offering engine integrations and other technology that makes it easier to work with their platform.

As I understand it, in SpatialOS you define behaviors for entities in the world, and these entities are running on their servers. From a backend perspective the servers scale as the number of entities scale. In theory you could simulate every detail in a world by just adding more computational power.

##### Share on other sites
hplus0603    11356

Every five years, some company with expertise from some "adjacent" technology area (finance, mil/sim, telecom, geospatial, etc) believes that they can do games better! They will win with their superior tech!

I have not seen a single one of those actually manage to get anything real and lasting into the marketplace. Not for lack of trying!

Is Improbable different? Perhaps. They got a giant investment from SoftBank, which might mean they have something neat and new. Or it may mean they have good connections to investors who have different investment criteria.

Quote

moving the distributed concept to "the cloud", where computation is relatively cheap and easy to scale

You mean, in the "cloud," where latencies cannot be managed, where noisy neighbors can flood your network, and where two processes that communicate intimately end up being placed on different floors of a mile-long data center, and that charges 10x mark-ups on bulk network capacity? That "cloud"? Or is this some other "cloud" that actually works for non-trivial low-latency real-time use cases?

In the end, though, most games just aren't well-funded and big enough to actually make a lot of sense for more business-focused companies. And, those who are (OverGears of BattleDuty and such) they end up distinguishing their games from others by integrating gameplay with networking with infrastructure really tightly, and at that point, a "one size fits all" solution looks more like "one size fits none."

Don't get me wrong. Distributed simulation is a fun area to work in, and there are likely large gains to be had through innovative whole-stack approaches. History just shows that the over/under on any one particular entrant in the market is "not gonna make it."

##### Share on other sites
khawk    2924
3 minutes ago, hplus0603 said:

That "cloud"? Or is this some other "cloud" that actually works for non-trivial low-latency real-time use cases?

That's "the cloud". I don't see SpatialOS being ready for low-latency real-time any time soon and not necessarily of their own fault.

FWIW, I did some press time with them at GDC. It was an interesting visit since I have experience in developing the types of distributed entity simulation platforms they're building. The demo was to showcase intelligent behavior across thousands of entities in a "virtual world" setting. It was fairly slow paced, when it worked - true to startup style they didn't account for poor internet at a trade show. So, not much of a demo.

##### Share on other sites
drainedman    104
23 minutes ago, khawk said:

That's "the cloud". I don't see SpatialOS being ready for low-latency real-time any time soon and not necessarily of their own fault.

FWIW, I did some press time with them at GDC. It was an interesting visit since I have experience in developing the types of distributed entity simulation platforms they're building. The demo was to showcase intelligent behavior across thousands of entities in a "virtual world" setting. It was fairly slow paced, when it worked - true to startup style they didn't account for poor internet at a trade show. So, not much of a demo.

Ah pretty disappointing if it can't do low latency. They kind of sold it as that though.

##### Share on other sites
hplus0603    11356

Also, a variety of multi-entity architectures have been tried. The most famous failure is probably Sun Darkstar, which ended up supporting fewer entities in cluster mode than in single-server mode :-) They used tuple spaces, which ends up being an instance of "shard by ID." The other main approach is "shard by geography."

A "massively multiplayer" kind of server ends up with, at a worst case, every entity wanting to interact with every other entity. For example, everyone try to pile into the same auction area or GM quest or whatever. (Or all the mages gather in one place and all try to manabolt each other / all soldiers try to grenade each other / etc.)

N-squared, as we know, leads to an upper limitation to the number of objects that can go into a single server. Designing your game to avoid this, helps not just servers, but also gameplay. When there's a single auction area that EVERYBODY wants to be in, it's not actually a great auction experience (too spammy,) so there's something to be said for spreading the design out. (Same thing for instanced dungeons/quests, etc.)

Anyway, once you need more than one server, then you can allocate different servers to different parts of the world (using level files, or quad trees, or voronoi diagrams, or some other spatial index,) To support people interacting across borders, you need to duplicate an entity across the border for as far as the "perception range" is. This, in turn, means that you really want the minimum size of the geographic areas to be larger than the perception range, so you don't need to duplicate a single entity across very many servers. If by default you have chessboard distribution, and the view range is two squares, you have to duplicate the entity across 9 servers all the time. That means you need 10 servers just to get up to the capacity range of a single non-sharded server! The draw-back then is that you have a maximum density per area, and a minimum area size per server, which means your world has to spread out somewhat evenly. Because the server/server communication is "local" (only neighbors,) you can easily scale this to as large an area as you want, as long as players keep under the designated maximum limit. Many games have used methods similar to this (There.com, Asheron's Call, and several other.)

The other option is to allocate by ID, or just randomly by load on entity instantiation. Each server simulates entities allocated to them. You have to load the entire static world into each server, which may be expensive if your world is really large, but on modern servers, that's not a problem. Then, to interact between other servers, each server broadcasts the state of their entities using something like UDP broadcast, and all other servers decode the packets and forward entities that would "interact with" entities that are in their own memory. This obviously lets you add servers in linear relation to number of players, and instead you are limited by the speed at which servers can process incoming UDP broadcast updates to filter for interactions with their own entities, and you are limited by available bandwidth on the network. 100 Gbps Ethernet starts looking really exciting if you want to run simulation at 60 Hz for hundreds of thousands of entities across a number of servers! (In reality, you might not even get there, depending on a number of factors -- Amdahl's Law ends up being a real opponent.)

None of this is new. The military did it in the '80s on top of DIS. And then again in the late '90s / early '00s on top of HLA. It's just that their scale stops at how many airplanes and boats and tanks they own, and they also end up accepting that they have to buy one computer per ten simulated entities or whatever the salespeople come up with. There's only so many billion-dollar airplanes in the air at one time, anyway.

For games, the challenge is much more around designing your game really tightly around the challenges and opportunities of whatever technology you choose, and then optimizing the constant factor such that you can run a real-size game world on reasonable hardware. (For more on single-hardware versus large-scale, see for example http://www.frankmcsherry.org/assets/COST.pdf )

##### Share on other sites
drainedman    104

What if you had just one server with 128 cores and a huge shared memory?

Surely that would support hundreds of thousands of players.

##### Share on other sites
hplus0603    11356

Cores talk to memory through a memory bus. That memory bus has some fixed latency for filling cache misses. Surely, it will be faster than an external network, but on the other hand, all of those users need packets generated to/from themselves, going into/outof the core, too.

It's hard to get more than four-channel memory into a single socket, and price goes up by something like the square of the socket count (dual-socket much more expensive than single-socket; quad-socket much more expensive than dual-socket.)

And, once you have CPUs with different sockets, the different CPUs should be thought of as different network nodes -- a cache miss filled in 400 cycles on a local RAM module may take 4000 cycles when filling from a remote CPU NUMA node. (usually, the difference is less stark, but it's easily noticeable if you measure it.)

So, let's assume there are four sockets, each with 50 GB/s throughput. Split 25,000 users per core, at 60 Hz. That gives 33 kilobytes per player per frame, and this is assuming that you will use memory optimally. (Most cache-miss-based algorithms would be happy to get past half the theoretical throughput.)

Can you do all the processing you need to do for a single player for a single frame, touching only 33 kilobytes of RAM? (Physics, AI, rules, network input, network output, interest management, and so on all go into this budget.) It's quite possible, if you know what you're doing, and carefully tune the code for the system that's running it, but it's no sure slam-dunk winner. Write your code in Java or Python or some other language that ends up chasing too many pointers, and you lose your edge very quickly.

I just priced a PowerEdge with quad 16 core/32 thread Xeons, four 8-way 16 GB DIMMs per socket, and dual 10 Gb network interfaces; it's about $50k (plus tax and if you need storage disks and such.) You'd also want at least two, because if you have a single server and it dies, your game is as dead as the server. (You'd also need data center rack space/power/cooling and routers/switches/uplink and so on.) Although, still,$100k isn't that bad; the multiplayer networking systems have to compete with this offering and make it worthwhile, which limits their ability to charge upwards, which in turn means they can't solve problems that are too advanced or too fancy, and thus have to simplify their solution to the wider masses of developers. This, coupled with the incredible importance of designing game and network behavior hand-in-hand, probably is one of the explanations why there isn't a phletora of successful game multiplayer hosting/middleware solutions out there, and why each of the ones that are surviving actually fills a different niche -- there simply isn't space to survive for two different competitors in the same niche.

##### Share on other sites
drainedman    104
Posted (edited)

I can't afford $50k but I am planning on building a beowulf cluster to support a kind of MMO with 100k+ entities (not all human but all are persistent). I'm just going to go for a simple method - each 2 km sq region is handled one process. Every process sends sync messages to its neighbours via network messaging. Only edges of the regions are kept in sync. I'd like to run this over a VLAN to separate network channels. Of course this has lots of limitations but if I get this far then I will implement some load balancing e.g. split the regions with heavy loads into 1km sq regions, etc. So long as not too many objects converge in spot and do too many interactions it might be ok. Edited by drainedman #### Share this post ##### Link to post ##### Share on other sites Kylotan 10005 I worked for an MMO company who had very similar technology up and running back in 2005. We didn't even use that tech in the end because it wasn't a useful selling point and the market had moved away from the single-shared-world model anyway due to World of Warcraft. (Arguably this was because their networking model was so primitive that they had no choice, but turning limitations into opportunity is always a good idea.) As mentioned above the main draw of this new service is that you don't have to manage your own servers like we did. Cloud services are probably low latency enough for most MMO usages now, but probably not shooter-style ones. Potential downsides include hosting and operation costs, since you can probably get it cheaper via a specialised solution (although you also run the risk of over-specifying and paying for capacity you don't need), and development costs, because you have to write the entire game using their paradigm, which may not suit you. #### Share this post ##### Link to post ##### Share on other sites ggambett 145 Posted (edited) Hi! I'm Gabriel, former game dev and very interested in niche topics such as client/server network architectures or pathfinding for games, now working at Improbable. I hope I can clarify a few things about SpatialOS - apologies for the long reply but there’s loads of great stuff to discuss here! @khawk your understanding of SpatialOS is pretty much spot-on. An alternative explanation that I really like is this: imagine the traditional Entity-Component-System architecture, where each system is a distributed system rather than a thread on a server. SpatialOS lets you do this, without having to actually write a distributed system. Quote FWIW, I did some press time with them at GDC I was there!!! From your description it sounds like you tried Worlds Adrift by Bossa Studios, or some of the other games by our partners (like Chronicles of Elyria by @JWalsh, whom I also had the pleasure to meet!). Did anyone give you a 1:1 tour of our Wizards demo game? We're now offering this tour on the website, and I can't recommend it enough - it should make the core concepts and the workflow clear to everyone (if it doesn't, please message me - I run the team responsible for this content, so feedback is more than welcome!) Quote latencies cannot be managed, where noisy neighbors can flood your network, Yes, but this is also the case for any client-server game, and it depends on your internet connection at home; whether there's a single server or a swarm of workers on the other side can't improve that. Quote processes that communicate intimately end up being placed on different floors of a mile-long data center The internal latencies in a mile-long data center are so small compared to the latency from your home to the datacenter, that the latency you experience as a gamer will be dominated by the latter (as I said above, this is no different to connecting to a game with a single server). That said, SpatialOS is called SpatialOS for a reason Locality of reference is one of the core concepts of how the load balancing and worker allocation algorithms work. We go to great lengths to make sure that entities in close proximity in the virtual world are physically close in the datacenter - usually within the same physical server. To see all this in action, I'd suggest you take a look at Worlds Adrift, which has to be pretty much real-time because it's a very physics-heavy game. Every single thing in the game is physically simulated, including individual ship parts - as you can see in that video! Quote N-squared, as we know, leads to an upper limitation to the number of objects that can go into a single server. Designing your game to avoid this, helps not just servers, but also gameplay. Yep, agreed. Just like we can't work around the speed of light to provide zero end-to-end latency, we can't do much about the way O(n2) works As you point out, this has to be solved with a mixture of game design and clever software techniques. Note that O(n2) appears in different places. Interactions of objects within a worker are one, as you point out, but there's also O(n2) network communication between workers, and we can and do something about it - smart distribution and migration of entities between physical servers. This is another non-trivial problem that SpatialOS solves, and which is invisible to the developer and the player (see this for an example). @hplus0603 your thoughts about the impact of the perception range are very interesting. SpatialOS does this in a different way, though. In SpatialOS, the allocation of workers is dynamic, and it follows the workload of the simulation around. This minimises the migrations that need to happen. There is co-simulation where the areas overlap, but we make this invisible both to developers and players. Distributed physics is a particularly fun example of this - we've written about that in a blog post. Second, SpatialOS does this at the component level rather than the entity level. So you could have a game world simulated by 100 physics workers (e.g. instances of PhysX) but only 10 game logic workers if it's a physics-heavy game. Or 10 physics workers, 50 AI workers and 5 pathfinding workers. The point is that every kind of worker needs to "see" just a narrow subset of the components of an entity (generally, the ones it is able to simulate), and this reduces the bandwidth requirements tremendously. Workers follow the workload, and they do this in a layered way, so in practice there are far less physical migrations than you may think. Quote I can't afford$50k but I am planning on building a beowulf cluster to support a kind of MMO with 100k+ entities (not all human but all are persistent).

Sounds like a job for SpatialOS You get the benefits of running a cluster, but without any of the complexity of setting up and running a cluster. In fact, you don't have to write networking code at all - you see this in practice in our Wizards demo.

About the $50k, are you aware of our Games Innovation Program? We understand this is a concern for a lot of developers, so in a nutshell, we've partnered with Google Cloud to offer subsidies to usage costs to users enrolled in the Program. Read more details in this article. Also, development on your local machine is always free, so you can try SpatialOS with your SDK of choice, try the Wizards demo or the Pirates tutorial, etc. Quote Potential downsides include hosting and operation costs, since you can probably get it cheaper via a specialised solution (although you also run the risk of over-specifying and paying for capacity you don't need), and development costs, because you have to write the entire game using their paradigm, which may not suit you. You would be surprised! We ran the numbers in detail, and the economics may not be so different, especially when you really scale your game up. And at that point you also need to consider the cost and expertise of having a dedicated infrastructure / DevOps team. Spilt Milk, the creators of Lazarus, touch upon these topics in this article. As a small team with no previous large scale networking experience, they went from zero to a continuous playable alpha with 3000 concurrent players in 4 months. Once again, this was a great thread to read! Happy to address any other questions you may have Edited by ggambett Formatting #### Share this post ##### Link to post ##### Share on other sites Scouting Ninja 3968 Posted (edited) 1 hour ago, ggambett said: Yes, but this is also the case for any client-server game, and it depends on your internet connection at home; 1 hour ago, ggambett said: The internal latencies in a mile-long data center are so small compared to the latency from your home to the datacenter, that the latency you experience as a gamer will be dominated by the latter interesting, so what range of networking would be ideal from the players point? I mean if only players with the highest bandwidth can play then what is the point of a huge game world? How do you plan to deal with the view range, it is notable that in the Wizards demo the camera is setup to prevent the player from seeing into the distance. The Pirate tutorial has nothing there, only a flat plane. Isn't the point of making a large world to have enough space for a huge player base, for players to see they are in a large open world and to have hundreds of players interacting with each other at once. At the moment it still looks like having servers for each region is a better idea than having one large server where you lump players. Then there also is the fact that the further a player is from the server the more they will lag. Edited by Scouting Ninja #### Share this post ##### Link to post ##### Share on other sites Kylotan 10005 (Replying to ggambett, 2 posts up) Hi Gabriel, thanks for coming on here and answering some questions. I can see why the product is an attractive one for people who aren't able or willing to manage their own hosting. That is one reason why it is a more attractive proposition than what my former company was offering 10 years ago, because although we provided a very similar architecture, the expectation there was that the game developer would provide and manage their own servers. So things have changed there. I still think the paradigm shift necessary to use such a system can be complex. The "zero networking code" aspect is not a big deal these days since most game engines offer that to some degree with state replication - but learning to write code with fewer 'shared-everything' assumptions and more message passing is tricky for many game developers. That's not a criticism of your tech, as the problem is intrinsic to running a distributed simulation. But it's also why some games have gone down the WoW route and simply decided it wasn't a problem that was worth solving. Additionally, trying to describe it as like an entity-component system for the cloud is a negative in this regard because it's clear from posts on Gamedev.net that most developers aren't comfortable with that approach and struggle significantly with creating clear partitions between components and in handling complex multi-entity/component interactions. That's arguably why the 2 major engines allow full communication between arbitrary entities and components - the alternatives make otherwise easy interactions quite complex to handle.) #### Share this post ##### Link to post ##### Share on other sites hplus0603 11356 Quote Quote latencies cannot be managed, where noisy neighbors can flood your network, Yes, but this is also the case for any client-server game, and it depends on your internet connection at home; whether there's a single server or a swarm of workers on the other side can't improve that. I think you misunderstood me. I'm talking entirely about things that go in inside a virtualized, cloud-hosted data center. Because it uses virtualization for the machine hosts, you are subject to the requirements of the virtualization platform, and that often introduces significant (many milliseconds) latencies in scheduling, because the VM hosts are all optimized for batch throughput, not for low-latency real-time processing. For real-time simulation running close to full machine utilization, a physics step time that goes from 15.5 milliseconds to 17.5 milliseconds will make you miss your deadline. For real-time physics games, I much prefer bare metal for this reason. It's also interesting that you mention co-simulation across visibility borders and PhysX at the same time. PhysX is not deterministic, so any co-simulation across borders will diverge. With enough authoritative network state snapshots, you can mash that with brute force, of course. Regarding the "borders moving with load," that's something we looked at an implemented for There.com, but it ended up not being useful for real gameplay, because players tended to gather in the same kind of gathering places. Meanwhile, the view distance across borders (i e, how much you need to co-simulate) has to be determined by the "visibility range" of your objects. If your object is a missile cruiser with a range of 150 kilometers, you have to have an instance of the object on any server that touches this radius, so that it can do target acquisition. (Either you have an instance of the cruiser on each server within the radius, OR you bring a copy of each object within that radius to the cruiser's server -- if there are fewer cruisers than targets, you want the former, for hopefully obvious reasons.) If you have a soldier with a sniper rifle with a 2 kilometer scope, you have to be able to see each object within two kilometers, or the player will be sad. I'm pointing this out, not to cast shade on SpatialOS, but to show that any distributed server framework has to be used with gameplay design that goes hand-in-hand with the networking/simulation capabilities, and each solution will bring with it specific limitations you have to accept as a game designer. Using words such as "invisible to the developer" or "without having to think about distribution" sounds great in marketing, but ends up not actually being helpful to the end developer. And, honestly, is actually untrue for all but the most trivial kinds of games. I've found that the companies that end up doing the best in gaming are those that are clear about pros and cons about their systems, and that do not make over-simplified promises they cannot actually deliver on (without tons of caveats) in their marketing. #### Share this post ##### Link to post ##### Share on other sites ggambett 145 1 hour ago, Scouting Ninja said: I mean if only players with the highest bandwidth can play then what is the point of a huge game world? I didn't say that; apologies if I expressed myself in an unclear way. What I tried to say is that the player's latency to a datacenter is the same regardless of whether there's a single server inside the datacenter running the game, or a cluster of a hundred (because the internal latency is minimal). So the network requirements of a SpatialOS game are no more strict than a regular game running on a single server. On the flip side, the SpatialOS game is not limited by whatever that single server and engine can handle (and servers can get only so big). 1 hour ago, Scouting Ninja said: How do you plan to deal with the view range, Each worker has a configurable "checkout radius", which is effectively the view range. There are interesting LOD techniques you can apply to updates to minimise the bandwidth impact of a big checkout radius. We also have the concept of streaming queries, which allows workers to "see" entities that wouldn't normally fall within their checkout radius. This is used in Worlds Adrift, for example, where islands are visible from vast distances, much farther away from where a worker would need 60hz position updates for things in their surface. Hopefully this also answers @hplus0603's question (although this is the only instance of "view across borders", because the border of the region of interest of a client is the view range). 2 hours ago, Scouting Ninja said: Isn't the point of making a large world to have enough space for a huge player base, for players to see they are in a large open world and to have hundreds of players interacting with each other at once. Absolutely, and this is exactly the kind of experience that SpatialOS enables - take a look at Worlds Adrift for an example of exactly that 2 hours ago, Scouting Ninja said: At the moment it still looks like having servers for each region is a better idea than having one large server where you lump players. That may be more appropriate for some types of games. SpatialOS offers different load-balancing modes, and one of them puts workers in a static configuration. Note that even in this case, workers aren't equivalent to servers handling regions; all the workers combine to simulate a single continuous game world with no hard boundaries, regardless of whether you choose a static or a dynamic worker allocation setup. 2 hours ago, Kylotan said: I can see why the product is an attractive one for people who aren't able or willing to manage their own hosting. Making massively distributed systems is not exactly simple, especially for non-embarrassingly-parallelizable problems such as physics. Of course as a game developer you want to spend most of your time and effort making a game and exploring the creative possibilities of large worlds, not a spatially distributed cloud compute platform! But even studios that are experts in, and famous for, long-running MMOs see the value in using SpatialOS. The clearest example I can offer of this is Jagex, the creators of Runescape, with whom we've recently partnered with. 2 hours ago, Kylotan said: I still think the paradigm shift necessary to use such a system can be complex. [...] That's not a criticism of your tech, as the problem is intrinsic to running a distributed simulation. There is a bit of a paradigm shift, absolutely. But what you get for your investment in learning how to work with SpatialOS is the possibility of building games of a scale and richness that is currently beyond the reach of most game developers. 2 hours ago, Kylotan said: most developers [...] struggle significantly with creating clear partitions between components [...] That's arguably why the 2 major engines allow full communication between arbitrary entities and components - the alternatives make otherwise easy interactions quite complex to handle.) I would argue that's not a limitation of the ECS (or ECW) architecture. In fact, this limitation doesn't exist in SpatialOS - any component of any entity can communicate with any other component of any other entity by sending a command (essentially RPCs), no matter where it is (in the game world, or in computational terms). 1 hour ago, hplus0603 said: PhysX is not deterministic, so any co-simulation across borders will diverge. With enough authoritative network state snapshots, you can mash that with brute force, of course. I have limited knowledge of physics simulation, but I understand stable simulation is not trivial, even on a single instance of a physics engine; forcing more than one physics engine to cooperate, where they aren't even aware of the other's existence, is not a matter of brute force I refer again to this experiment we made (the video is pretty cool!). But the broader point is that a SpatialOS game developer doesn't even have to think about this - no discussion about whether to use brute force or something more subtle, no code to deal with this or with anything related to co-simulation. 1 hour ago, hplus0603 said: Using words such as "invisible to the developer" or "without having to think about distribution" sounds great in marketing, but ends up not actually being helpful to the end developer. But this is pretty much true in the case of SpatialOS, and I say this as both as a game developer and a hardcore software engineer, not as a marketing person. As discussed above, there is a bit of a paradigm shift required, but you really don't have to think in terms of implementing or running a distributed system; game logic involves workers receiving state updates, doing whatever computation they need, and sending back state updates. There really isn't any need to write networking code, or any kind of manual synchronization code, or in general, even being aware that you're making a massively distributed game rather than a single-player game running in a single machine, except in the broadest terms (e.g. commands may fail, so you may need to add some custom retry logic if you're not happy with the defaults). Don't take my word for this; you can play actual games built on SpatialOS right now (Worlds Adrift, Lazarus). You can download the SDK and play with the Wizards demo or the Pirates tutorial right now. It's all freely available, fully documented, in production, and with enough examples and starter projects to get you started (github.com/spatialos). #### Share this post ##### Link to post ##### Share on other sites hplus0603 11356 Quote game logic involves workers receiving state updates, doing whatever computation they need, and sending back state updates I know what you're talking about. I built a system that had many similar properties, including this programming model for entities. Our sales people used the same marketing claims. It turns out, there are things developers do "as a matter of course" that ends up generating way too much RPC traffic to scale well. Developers need to know what the distribution decomposition is, if they want to get anywhere near (say, within an order of magnitude of) the theoretical maximum performance of the system. Naive developers, even using your carefully crafted API that attempts to make developing distributed objects easy, and "hiding" RPC/messaging, WILL flood your system to the point where scalability is 1/100th of what it should be. Further, developers will assume that RPC or events are reliable, AND bounded time. As you know you can't get both of those at the same time across a lossy network ("two generals problem.") If, in the context of "paradigm shift," you suggest that developers also need to train themselves to know about these things, then yes, inside the paradigm you live inside the paradigm. But that paradigm includes limitations that are imposed by your particular distribution model. That's an unavoidable outcome of distributed games, and it's what makes distributed games (and other systems) an order of magnitude harder to work with than in-RAM single-player games, and pretending that they're the same does nobody any favors. (Except possibly salespeople on commission who would prefer to close deals early over closing the right deals -- luckily, I've managed to avoid most of those in my life!) #### Share this post ##### Link to post ##### Share on other sites drainedman 104 Posted (edited) This is how my tiny brain understands the problem. Ultimately locality is at the core of the it (server side). Suppose an entity is processed 30 times in 1 second. In order for this entity to process its behaviour within that slice of time it must take in information of its nearby space. For example a brick falling through space will need to know about its neighbours so it can go bumpity-bump-bump with other bricks. We can cheat a bit by generally disregarding entities a long way away to reduce the number of interactions from squared to linear. When working within a single process we can do entity neighbour lookups very quickly as RAM access is pretty quick (we have seen this used to great effect with CUDA physx demos and so on). 10,000 entities will mean 300,000 neighbour queries on top of physics, behaviour calculations etc per second. Quite manageable within one process. However, to scale up to more entities we want to split the workload across two or more nodes and the processes cannot access each other's RAM. non-local entities (entities from different process) must talk to each other by some other medium. Quick, large distributed shared memory isn't an option with current hardware (although surely some hardware guru could build it), so we use something like standard networking. Because of this our communication speed between non-local entities has dropped by a factor of about 200 or worse. To compound this latency we find that highly dynamic environments such as MMO's will vary the load which can mean high volumes of traffic in concentrated areas. Some entities will travel insanely fast across multiple nodes (speeding bullets, airplanes, cars). Also some very selfish entities are particularly inconsiderate and want to exchange HIGH volumes of data and want to do it instantly. Transactions in market places springs to mind. Or perhaps a car with a 10 hour pre-planned route. Or an entity with a daily schedule. We can't really ever get around these limitations until we (somehow) increase the speed of access across all nodes to be as quick as if they were all a single unified node. Meanwhile designing the game/simulation is critical to making the whole experience balance out. I don't even think its possible in the generic sense to make a scaleable MMO - with current hardware. Actors, services, workers, etc I view as a kind of syntax flim-flam, froo-froo. It does little to address the limitations. My personal pet favourite tech to tackle this problem is MPI https://en.wikipedia.org/wiki/Message_Passing_Interface Edited by drainedman speling #### Share this post ##### Link to post ##### Share on other sites hplus0603 11356 You are not wrong :-) Quote We can cheat a bit by generally disregarding entities a long way away to reduce the number of interactions from squared to linear. It's actually still quadratic, but quadratic in a smaller number (number of entities divided by number of servers, times number of entity copies needed for cross-border resolution.) Similarly, a single locality query for "nearby" objects is not a constant cost, but actually has a cost that is linear in number of neighbors. While there may be 300,000 queries for 10,000 entities at 30 Hz, each query may return more than one entity, and thus may cost more than "1" along a few cost metrics (storage, memory touched, entities to check against, etc.) Quote My personal pet favourite tech to tackle this problem is MPI MPI lets you send messages between processes, using non-lossy but also not-real-time-aware TCP RPC. This is a useful primitive to use when building distributed systems, but it doesn't really get at the real question, which is "how do you structure your game design to make best use of distributed servers, and avoid placing undue burden on the server system that you have?" It seems like SpatialOS implements a particular kind of trade-off and an API to support developing entities for that trade-off. Other systems do a similar thing, reaching different conclusions with different base assumptions. This is why "how can I compare these different platforms?" is such a hard question, because it totally depends on the specifics of your game. Farmville works great on plain Amazon ECC web server instances. Unreal Tournament, not as much. #### Share this post ##### Link to post ##### Share on other sites drainedman 104 13 minutes ago, hplus0603 said: This is a useful primitive to use when building distributed systems, but it doesn't really get at the real question, which is "how do you structure your game design to make best use of distributed servers, and avoid placing undue burden on the server system that you have?" It seems like SpatialOS implements a particular kind of trade-off and an API to support developing entities for that trade-off. Other systems do a similar thing, reaching different conclusions with different base assumptions. This is why "how can I compare these different platforms?" is such a hard question, because it totally depends on the specifics of your game. Farmville works great on plain Amazon ECC web server instances. Unreal Tournament, not as much. Indeed MPI is just a tool and not a complete solution. SpatialOS is a "solution" platform but it remains to be seen that it can do the more demanding applications such as a huge Unreal tournament, for example. Of course as you pointed out we have seen this kind of tech many times before. Pikkoserver, Shinra spring to mind as the latest failures. I don't think its an impossible feat as such, just a bit limiting with current hardware. I don't really know! I suspect the answer lies in a more hardware solution than software however. #### Share this post ##### Link to post ##### Share on other sites Kylotan 10005 14 hours ago, ggambett said: 17 hours ago, Kylotan said: most developers [...] struggle significantly with creating clear partitions between components [...] That's arguably why the 2 major engines allow full communication between arbitrary entities and components - the alternatives make otherwise easy interactions quite complex to handle.) I would argue that's not a limitation of the ECS (or ECW) architecture. In fact, this limitation doesn't exist in SpatialOS - any component of any entity can communicate with any other component of any other entity by sending a command (essentially RPCs), no matter where it is (in the game world, or in computational terms). I think hplus0603 already touched upon this, but the problem is that this decomposition never comes for free. When you split logic over multiple objects you have to decide how and when those objects communicate, and what gets communicated. It's rare that any desired communication is impossible but it's common that certain communications become more verbose, more complex, slower, or all of the above. With a distributed simulation the problem gets worse. If one component has to send an asynchronous message to another to get data, that is quick but complex. If you wrap the asynchronous message and the receipt of a response into an RPC call, that is simple but slow. I see that your commands use a Request/Response pair, which is basically the former approach, and is exactly what we used at the first MMO company I worked at. It is elegant at the networking and simulation level, and complex at the game logic level. Again, I'm not criticising the SpatialOS technology - just stating that it really does require a mental shift to implement things using such a model and that developers still have to think like a network programmer even if they never have to worry about packets or serialisation. #### Share this post ##### Link to post ##### Share on other sites flodihn 281 Posted (edited) On 20/06/2017 at 7:31 AM, drainedman said: I can't afford$50k but I am planning on building a beowulf cluster to support a kind of MMO with 100k+ entities (not all human but all are persistent).

I'm just going to go for a simple method - each 2 km sq region is handled one process. Every process sends sync messages to its neighbours via network messaging. Only edges of the regions are kept in sync. I'd like to run this over a VLAN to separate network channels.

Of course this has lots of limitations but if I get this far then I will implement some load balancing e.g. split the regions with heavy loads into 1km sq regions, etc.

So long as not too many objects converge in spot and do too many interactions it might be ok.

I am currently building a mini cluster of raspberry pi's. So far I got two of them but plan to expand to four.

Each raspberry pi has 4 cores and 1 GB RAM and 16 GB SSD drive.

You could easly support 20,000 - 40,000+ concurrent players on that, but it heavily depends on the game design.
When doing single shard multiplayer games, it is critical to avoid choke points, such as having one capitol city or one location for the auction house where players tend to group together.

I made my own distributed server in Erlang and on an 8 core desktop computer I could support congestion of about 2 groups with 2000 players at the very same spot. This would be similar to players forming a warband in WoW and running around killing stuff.
With those 2 groups of 2000 players each, the same server was under heavy load but still responsive, I tried to fire up a third group of that size but then things started to lag badly.

In an other test, I spread the players evenly about the world, I had divided the world (1024x1024m) into smaller chunks of 64x64 meters. With about 60 players in each such chunk the server were running smoothly handling around 12,000 concurrent players with latencies between 10 - 50 ms.

I have not yet tested the performance on my raspberry pi cluster, but I am working on it now and should have some interesting results to share later this  summer.

Supporting 100k+ entities were most of them are static or mostly inactive should not be very hard, but it is time consuming to build such software unless you use something already existing.

Edited by flodihn

##### Share on other sites
hplus0603    11356

You could easly support 20,000 - 40,000+ concurrent players on that

While the Raspberry Pi is amazing, it's not THAT amazing. For example, the Ethernet is a 100 Mbps interface sitting on an internal USB hub. And calling the MicroSD card a "SSD" is ... a little optimistic :-)

I bet, if players aren't doing much, and you don't have real-time simulation requirements, and bandwidth is carefully managed, you could do thousands per Pi. That's still pretty amazing!

##### Share on other sites
drainedman    104

I have always generally preferred to roll my own solutions where there is not a proven technology available. I think the reason behind this is that I like to fully understand how my system works. I also like to deal in precise quantities, I like to know what is and isn't possible. Using 3rd party stuff I can never be sure if I'm using it wrong or if the "technology" is limited.

For example Erlang gets recommended a lot but I just don't see the speed advantage of using Erlang for low latency distributed simulation for instance. Perhaps I just don't like Erlang. Maybe the supposed advantage is that its easier to use but I'm already invested in my own pet technology so that its easier doesn't really hold true for me either.

In any case my approach is not treading new ground, which gives me some optimism. I have read papers on similar stuff done years ago.

##### Share on other sites
hplus0603    11356

For example Erlang gets recommended a lot but I just don't see the speed advantage of using Erlang for low latency distributed simulation for instance.

Erlang gives you the advantages of immutable data. It also gives you the advantages of ultra-cheap "processes" (more like "fibers" but the immutable data means you can't accidentally someone else.) It also gives you the advantages of being able to upgrade the running code in-place. No rolling re-starts, no socket close and reconnects, just keep on going with the new version of the code. (The immutable-isolated-data concept makes writing these in-RAM migrations possible.) Finally, it gives you very small-size, threaded garbage collection, because each little micro-process has its own heap that's collected in isolation.

The upgrade-in-place is actually quite hard to do with DLL re-loads in C/C++, or most of any other language. The other bits are possible in other languages, with slightly different trade-offs. If you're interested in systems, in general, and haven't used most of those features (especially immutable-data functional programming) on previous projects, it's at least worth checking out for learning. It is a very different paradigm, though (if you haven't already used ML/Haskell/OCaml/F#) so expect going to be very hard and uphill initially. It really takes time and effort to learn, like anything else that is actually big, different, and worthwhile.

That doesn't mean Erlang is the right choice for you. The IPC is low-latency, but cross-node communication uses TCP. The VM generates native code for execution, but the constant overhead is noticeable (Erlang is slightly slower than Java in my experience.) Not every project needs 100% uptime even through deploys and rollbacks. But, it represents a fundamentally different approach to the problems faced by distributed systems developers, and thus, it's quite worth learning in detail.

##### Share on other sites
flodihn    281
9 hours ago, hplus0603 said:

While the Raspberry Pi is amazing, it's not THAT amazing. For example, the Ethernet is a 100 Mbps interface sitting on an internal USB hub. And calling the MicroSD card a "SSD" is ... a little optimistic :-)

I bet, if players aren't doing much, and you don't have real-time simulation requirements, and bandwidth is carefully managed, you could do thousands per Pi. That's still pretty amazing!

I was referring to my Raspberry cluster of 4 Raspberry's, maybe that was not clear in my post, sorry about that. But yeah, the numbers heavily depend on the type of game play you have in your game.


text:
# Learning Theory

Why is learning from data even possible? To discuss this problem, we need a framework for learning. …

Two of the key elements in a learning problem are: a set of hypothesis $\mathcal H$, and a set of …

Information Bottleneck In a [[induction-deduction framework]] Induction, Deduction, and …

Given a set $\mathcal S$, and a class (collection of sets) $\mathcal H$. For any subset of $\mathcal … Noise contrastive estimation (NCE) objective function is1$$\mathcal L = \mathbb E_{x, x^{+}, … Cross validation is a method to estimate the [[risk]] The Learning Problem The learning problem … The learning problem posed by Vapnik:1 Given a sample:$\{z_i\}$in the probability space$Z\$; …

format: plain


text:
# Math Help - Factorization of Polynomials - Gauss's Lemma

1. ## Factorization of Polynomials - Gauss's Lemma

Please ignore this post _ see corrected post


text:
# zbMATH — the first resource for mathematics

Computable symbolic dynamics. (English) Zbl 1170.03029
The paper mainly consider computable dynamical systems on the string space $$\{0,1,\dots,k\}^{\mathbb N}$$. The symbolic dynamics relative to a clopen partition is considered and several results are proved on the associated subshift. In particular, this set is proved to be an effectively closed set, and examples of $$\Pi _0^1$$ subshifts without computable elements are contructed. In the last part of the paper this framework is applied to investigate some computability question about unimodal maps and their symbolic dynamics.

##### MSC:
 03F60 Constructive and recursive analysis 03D80 Applications of computability and recursion theory 26E40 Constructive real analysis 37B10 Symbolic dynamics
##### Keywords:
computability; symbolic dynamics; computable closed sets
Full Text:
##### References:
 [1] Braverman, Computing over the reals: foundations for scientific computing, Notices Amer. Math. Soc. 53 pp 318– (2006) · Zbl 1092.68038 [2] Braverman, Non-computable Julia sets, J. Amer. Math. Soc. 19 pp 551– (2006) [3] D. Cenzer, Effective dynamics. In: Logical Methods in Honor of Anil Nerode’s Sixtieth Birthday (J. Crossley, J. Remmel, R. Shore, and M. Sweedler, eds.), pp. 162-177 (Birkhäuser, 1993). [4] D. Cenzer, $$\Pi$$01 classes in computability theory. In: Handbook of Recursion Theory (E. Griffor, ed.). Studies in Logic and Foundations of Mathematics 140, pp. 37-85 (North-Holland, 1999). · Zbl 0939.03047 [5] D. Cenzer, S. A. Dashti, and J. L. F. King, Effective symbolic dynamics. In: CCA 2007 (Computability and Complexity in Analysis, Siena, June 2007) (R. Dillhage, T. Grubb, A. Sorbi, K. Weihrauch, and N. Zhong, eds.). Informatik Berichte, Universität Hagen, 79-89 (2007) and [6] Electronic Notes in Theoretical Computer Science 202, 89-99 (2008). [7] Cenzer, Effectively closed sets and graphs of computable real functions, Theoret. Comput. Sci. 284 pp 279– (2002) · Zbl 1039.03033 [8] D. Cenzer, and J. B. Remmel, $$\Pi$$01 classes in mathematics. In: Recursive Mathematics (Y. Ersov, S. Goncharov, A. Nerode, and J. B. Remmel, eds.). Studies in Logic and Foundations of Mathematics 138, pp. 623-821 (North-Holland, 1998). · Zbl 0941.03044 [9] D. Cenzer, and J. B. Remmel, Effectively closed sets. To appear in Association for Symbolic Logic Lecture Notes. · Zbl 1140.03026 [10] P. Collet, and J. P. Eckmann, Iterated Maps On The Interval As Dynamical Systems (Birkhäuser, 1980). · Zbl 0458.58002 [11] J.-C. Delvenne, Dynamics, information and computation. Ph. D. thesis, Université Catholique de Louvain (2005). [12] Delvenne, Decidability and universality in symbolic dynamical systems, Fundamenta Informaticae 74 pp 463– (2006) · Zbl 1114.03032 [13] R. L. Devaney, An Introduction to Chaotic Dynamical Systems (Addison-Wesley, 1995). [14] Grzegorczyk, On the definitions of computable real continuous functions, Fund. Math. 44 pp 61– (1957) · Zbl 0079.24801 [15] Huang, Applications of pure recursion theory to recursive analysis, Acta Sinica 28 pp 625– (1985) · Zbl 0638.03058 [16] K. Ko, Complexity Theory of Real Functions (Birkhäuser, 1991). · Zbl 0791.03019 [17] Ko, On the computability of fractal dimensions and Julia sets, Ann. Pure Appl. Logic 93 pp 195– (1998) [18] Lacombe, Extension de la notion de fonction récursive aux fonctions d’une ou plusieurs variables réelles, Comptes Rendus Acad. Sci. Paris 241 pp 2478– (1955) · Zbl 0065.00201 [19] D. Lind, and B. Marcus, An Introduction to Symbolic Dynamics and Coding (Cambridge University Press, 1995). · Zbl 1106.37301 [20] M. Lothaire, Combinatorics on Words (Addison-Wesley, 1983). · Zbl 0514.20045 [21] Metropolis, On finite limit sets for transformation of the unit interval, J. Combinatorial Theory (A) 15 pp 25– (1973) · Zbl 0259.26003 [22] R. Rettinger, and K. Weihrauch, The computational complexity of some Julia sets. In: Proc. 35th ACM Symposium on Theory of Computing (San Diego, June 2003) (M. X. Goemans, ed.), pp. 177-185 (ACM Press, 2003). · Zbl 1192.68375 [23] K. Weihrauch, Computable Analysis (Springer, 2000). · Zbl 0956.68056 [24] H. Xie, Grammatical Complexity and One-Dimensional Dynamical Systems (World Scientific, 1996). · Zbl 1368.58001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.


text:
# Suggest the product from two-substituted benzene ring

Which are the possible products from this reaction?

The answer in the mark scheme shows that it should be as demonstrated as pic A. However, I think it could be either A. or B. since both substituted groups of the benzene ring, NH2 and Cl, direct the incoming electrophiles to attack the 2,4 and or 6 positions. Do I understand correctly?

I have never come across two substituted groups before. Should I consider both NH2 and Cl as substituted groups or only one of them, but which one? Also, how to count the position of carbon on the benzene ring in this case?

• Aniline directs o/p, chlorobenzene is weaker but directs m. The effects are additive – Waylander Mar 9 '17 at 10:44
• I thought halogens dieected o/p (except $\cw{F}$, maybe), bbut more weakly than an amino group. – Oscar Lanzi Mar 9 '17 at 11:26

Then can you now think about the correct choice? $\ce{-NH2}$ has a greater positive mesomeric effect (+M effect) in comparison to the Halogen groups.
Since the para position with respect to $\ce{-NH2}$ is already occupied by chlorine the ortho position would be attacked.
What we come to know is that since $\ce{-NH2}$ creates more electron availability in comparison to halogen it leads to "electrophilic substitution" on ortho position with respect to $\ce{-NH2}$.
And moreover $\ce{-NH2}$ group since a very very strong electron donor so once again another substitution of next bromine takes place at the other ortho position with respect to $\ce{-NH2}$.


text:
5. Jermaine is thinking about attending college. However, he knows he could get a job right out of high school making about $18 Question 5. Jermaine is thinking about attending college. However, he knows he could get a job right out of high school making about$18,000 a year.
He could also work part time while attending 4 years of college and
make $7,000 a year. Assuming grants will pay for his college, how long will it take Jermaine to recover his lost wages by choosing to go to college instead of working full time after high school? He will make$40,000 a year with his degree.

in progress 0
5 months 2021-08-22T05:57:24+00:00 1 Answers 4 views 0


text:
# Quick deprotonation question

## Main Question or Discussion Point

Why is it that when methylamine ($$CH_3 NH_2$$) loses a proton,

you get $$CH_3 NH$$ (with a negative charge on nitrogen) rather than $$CH_2 = NH_2$$ (with a positive charge on nitrogen) ?

GCT


text:
+0

+1
276
3
+1451

√x2+9 +3= x+4

Feb 27, 2018

#3
+20217
0

you can just use parentheses like this

(x^2+9)       or use the  LaTex function...

$$\sqrt{x^2+9}$$   + 3   = x+4      simplify by subtracting 3 from both sides of the equation

sqrt(x^2+9) = x+1        Now square both sides

x^2 + 9  = (x+1)^2       Now expand the R side

x^2 + 9 = x^2 + 2x +1  Subtract x^2 from both sides

9 = 2x+1

8=2x

x=4

Feb 27, 2018

#1
+20217
0

Is ONLY x^2 under the radical sign?

Feb 27, 2018
#2
+1451
+1

no it also extends to the +9..I just dont know how to extend it can you tell me?

Feb 27, 2018
#3
+20217
0

you can just use parentheses like this

(x^2+9)       or use the  LaTex function...

$$\sqrt{x^2+9}$$   + 3   = x+4      simplify by subtracting 3 from both sides of the equation

sqrt(x^2+9) = x+1        Now square both sides

x^2 + 9  = (x+1)^2       Now expand the R side

x^2 + 9 = x^2 + 2x +1  Subtract x^2 from both sides

9 = 2x+1

8=2x

x=4

ElectricPavlov  Feb 27, 2018


text:
# Calculate partial pressure of gases at equilibrium

I have the reaction $\ce{CO_{(g)} + Cl2_{(g)} <=> COCl2_{(g)}}$ where $K=4.5\times10^9$ at $100\ \mathrm{^\circ C}$

The first question was to find $K_p$ which I know is $K_p=K(RT)^{\Delta n}$ where $R=0.08206$, $T=273+100=373$ and $n=1-2=-1$. Put in the numbers and get $K_p\approx1.47\times10^8$.

Now comes the second question and this is where I get stuck:

Equal moles of $\ce{CO}$ and $\ce{Cl2}$ are reacted at $100\ \mathrm{^\circ C}$. If the total pressure at equilibrium is 5.0 atm calculate the equilibrium partial pressures of the gases.

I have tried several solutions, where I either end up with a wrong answer or hit a dead end. I just don't understand how to solve this.

The equations you need are $$K_p=\frac{p_{\ce{COCl2}}}{p_{\ce{CO}} p_{\ce{Cl2}}}=1.47\cdot10^8$$ and $$p_\text{tot}=p_{\ce{COCl2}}+p_{\ce{CO}}+p_{\ce{Cl2}}=5.0~\text{atm}$$ Additionally, $n_{\ce{CO}}=n_{\ce{Cl2}}\implies p_{\ce{CO}}=p_{\ce{Cl2}}$, making the system solvable.


text:
## Electronic Journal of Probability

### Hitting probabilities of random covering sets in tori and metric spaces

#### Abstract

We provide sharp lower and upper bounds for the Hausdorff dimension of the intersection of a typical random covering set with a fixed analytic set both in Ahlfors regular metric spaces and in the $d$-dimensional torus. In metric spaces, we consider covering sets generated by balls and, in tori, we deal with general analytic generating sets.

#### Article information

Source
Electron. J. Probab., Volume 22 (2017), paper no. 1, 18 pp.

Dates
Accepted: 17 May 2016
First available in Project Euclid: 5 January 2017

https://projecteuclid.org/euclid.ejp/1483585523

Digital Object Identifier
doi:10.1214/16-EJP4658

Mathematical Reviews number (MathSciNet)
MR3613694

Zentralblatt MATH identifier
06681503

Subjects
Primary: 60D05, 28A80

#### Citation

Järvenpää, Esa; Järvenpää, Maarit; Koivusalo, Henna; Li, Bing; Suomala, Ville; Xiao, Yimin. Hitting probabilities of random covering sets in tori and metric spaces. Electron. J. Probab. 22 (2017), paper no. 1, 18 pp. doi:10.1214/16-EJP4658. https://projecteuclid.org/euclid.ejp/1483585523

#### References

• [1] D. Badziahin, A. Pollington and S. Velani, On a problem in simultaneous Diophantine approximation: Schmidt’s conjecture, Ann. of Math. (2) 174 (2011), 1837–1883.
• [2] V. Beresnevich, Rational points near manifolds and metric Diophantine approximation, Ann. of Math. (2) 175 (2012), 187–235.
• [3] V. Beresnevich and S. Velani, A mass transference principle and the Duffin-Schaeffer conjecture for Hausdorff measures, Ann. of Math. (2) 164 (2006), 971–992.
• [4] R. Broderick, L. Fishman and A. Reich, Intrinsic approximation on Cantor-like sets, a problem of Mahler, Mosc. J. Comb. Number Theory 1 (2011), 3–12.
• [5] R. Broderick, L. Fishman, D. Kleinbock, A. Reich and B. Weiss, The set of badly approximable vectors is strongly $C^1$ incompressible, Math. Proc. Cambridge Philos. Soc. 153 (2012), 319–339.
• [6] Y. Bugeaud and A. Durand, Metric Diophantine approximation on the middle-third Cantor set, J. Europ. Math. Soc. 18 (2016), 1233–1272.
• [7] L. Carleson, Selected Problems on Exceptional Sets, Van Nostrand, 1967.
• [8] K. Dajani and A. Fieldsteel, Equipartition of interval partitions and an application to number theory, Proc. Amer. Math. Soc. 129 (2001), 3453–3460.
• [9] P. Deheuvels and D. M. Mason, Random fractal functional laws of the iterated logarithm, Studia Sci. Math. Hungar. 43 (1998), 89–106.
• [10] C. Dellacherie, Ensembles Analytiques, Capacités, Mesures de Hausdorff, Lecture Notes in Mathematics 295, Springer-Verlag, 1972.
• [11] A. Dembo, Y. Peres, J. Rosen and O. Zeitouni, Thick points for spatial Brownian motion: multifractal analysis of occupation measure, Ann. Prob. 28 (2000), 1–35.
• [12] D. Dickinson and S. Velani, Hausdorff measure and linear forms, J. Reine Angew. Math. 490 (1997), 1–36.
• [13] A. Durand, On randomly placed arcs on the circle, Recent developments in fractals and related fields, Appl. Numer. Harmon. Anal., Birkhäuser Boston Inc. (2010), 343–351.
• [14] A. Durand, Sets with large intersection and ubiquity, Math. Proc. Cambridge Philos. Soc. (1) 144 (2008), 119–144.
• [15] A. Dvoretzky, On covering a circle by randomly placed arcs, Proc. Nat. Acad. Sci. U.S.A. 42 (1956), 199–203.
• [16] A. Dvoretzky, P. Erdös and S. Kakutani, Double points of paths of Brownian motion in n-space, Acta Sci. Math. Szeged 12 (1950), 75–81.
• [17] A. Dvoretzky, P. Erdös, S. Kakutani and S. J. Taylor, Triple points of Brownian paths in 3-space, Proc. Cambridge Philos. Soc. 53 (1957), 856–862.
• [18] M. Einsiedler, L. Fishman and U. Shapira, Diophantine approximations on fractals, Geom. Funct. Anal. 21 (2011), 14–35.
• [19] K. Falconer, Fractal Geometry, John Wiley & Sons Inc., 2003.
• [20] A.-H. Fan, Recouvrements par des intervalles de longueurs aléatoires, Ann. Sci. Math. Québec 19 (1995), 49–64.
• [21] A.-H. Fan, How many intervals cover a point in Dvoretzky covering? Israel J. Math. 131 (2002), 157–184.
• [22] A.-H. Fan, T. Langlet and B. Li, Quantitative uniform hitting in exponentially mixing systems, Recent developments in fractals and related fields, 251–266, Appl. Numer. Harmon. Anal., Birkhäuser Boston, Inc., 2010.
• [23] A.-H. Fan, J. Schmeling and S. Troubetzkoy, A multifractal mass transference principle for Gibbs measures with applications to dynamical Diophantine approximation, Proc. London Math. Soc. (3) 107 (2013), 1173–1219.
• [24] D.-J. Feng, E. Järvenpää, M. Järvenpää and V. Suomala, Dimensions of random covering sets in Riemann manifolds, arXiv:1508.07881.
• [25] G. Harman, Metric Number Theory, London Mathematical Society Monographs 18, Oxford University Press, 1998.
• [26] J. Hawkes, On the Hausdorff dimension of the intersection of the range of a stable process with a Borel set, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 19 (1971), 90–102.
• [27] J. Hawkes, Trees generated by a simple branching process, J. London Math. Soc. (2), 24 (1981), 373–384.
• [28] R. Hill and S. Velani, The ergodic theory of shrinking targets, Invent. Math. 119 (1995) 175–198.
• [29] S. Janson, Random coverings in several dimensions, Acta Math. 156 (1986), 83–118.
• [30] E. Järvenpää, M. Järvenpää, H. Koivusalo, B. Li and V. Suomala, Hausdorff dimension of affine random covering sets in torus, Ann. Inst. Henri Poincaré Probab. Stat. 50 (2014), 1371–1384.
• [31] H. Joyce and D. Preiss, On the existence of subsets of finite positive packing measure, Mathematika 42 (1995), 15–24.
• [32] A. Käenmäki, T. Rajala and V. Suomala, Existence of doubling measures via generalised nested cubes, Proc. Amer. Math. Soc. 140 (2012), 3275–3281.
• [33] J.-P. Kahane, Some Random Series of Functions, Cambridge Studies in Advanced Mathematics 5, Cambridge University Press, 1985.
• [34] J.-P. Kahane, Sur la dimension des intersections, In Aspects of mathematics and its applications, 34 North-Holland Math. Library, 419–430. North-Holland, 1986.
• [35] J.-P. Kahane, Recouvrements aléatoires, Gaz. Math. 53 (1992), 115–129.
• [36] J.-P. Kahane, Random coverings and multiplicative processes, In Fractal geometry and stochastics, II (Greifswald/Koserow, 1998), Progr. Probab. 46, 125–146, Birkhäuser, 2000.
• [37] A. S. Kechris, Classical Descriptive Set Theory, Springer-Verlag, 1995.
• [38] D. Khoshnevisan, Y. Peres, and Y. Xiao, Limsup random fractals, Electron. J. Probab. 5 (2000), no. 5, 24 pp.
• [39] J. Levesley, C. Salp and S. Velani, On a problem of K. Mahler: Diophantine approximation and Cantor sets, Math. Ann. 338 (2007), 97–118.
• [40] B. Li, N.-R. Shieh and Y. Xiao, Hitting probabilities of the random covering sets, Fractal geometry and dynamical systems in pure and applied mathematics. II. Fractals in applied mathematics, 307–323, Contemp. Math. 601, Amer. Math. Soc., 2013.
• [41] B. Li and V. Suomala, A note on the hitting probabilities of random covering sets, Ann. Acad. Sci. Fenn. Math. 39 (2014), 625–633.
• [42] B. Li, B.-W. Wang, J. Wu and J. Xu, The shrinking target problem in the dynamical system of continued fractions, Proc. Lond. Math. Soc. 108 (2014), 159–186.
• [43] L. Liao and S. Seuret, Diophantine approximation by orbits of expanding Markov maps, Ergodic Theory Dynam. Systems 33 (2013), 585–608.
• [44] R. Lyons, Random walks and percolation on trees, Ann. Probab. 18 (1990), 931–958.
• [45] P. Mattila, Hausdorff dimension and capacities of intersections of sets in $n$-space, Acta Math. 152 (1984), 77–105.
• [46] P. Mattila, Geometry of Sets and Measures in Euclidean Spaces: Fractals and rectifiability, Cambridge University Press, 1995.
• [47] S. Orey and S. J. Taylor, How often on a Brownian path does the law of the iterated logarithm fail?, Proc. London. Math. Soc. 28 (1974), 174–192.
• [48] Y. Peres, Intersection-equivalence of Brownian paths and certain branching processes, Comm. Math. Phys. 177 (1996), 417–434.
• [49] A. Pollington and S. Velani, Metric Diophantine approximation and ‘absolutely friendly’ measures, Selecta Math. (N.S.) 11 (2005), 297–307.
• [50] B. Rynne, Hausdorff dimension and generalized simultaneous Diophantine approximation, Bull. London Math. Soc. 30 (1998), 365–376.
• [51] L. A. Shepp, Covering the line with random intervals, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 23 (1972), 163–170.
• [52] L. A. Shepp, Covering the circle with random arcs, Israel J. Math. 11 (1972), 328–345.
• [53] W. M. Schmidt, Diophantine approximation, Lecture Notes in Mathematics 785, Springer, 1980.
• [54] P. Shmerkin and V. Suomala, Spatially independent martingales, intersections, and applications, Mem. Amer. Math. Soc, to appear.
• [55] C. Tricot, Two definitions of fractional dimension, Math. Proc. Cambridge Philos. Soc. 91 (1982), 57–74.
• [56] B.-W. Wang, J. Wu and J. Xu, Mass transference principle for limsup sets generated by rectangles, Math. Proc. Cambridge Philos. Soc. 158 (2015), 419–437.
• [57] B. Weiss, Almost no points on a Cantor set are very well approximable, R. Soc. Lond. Proc. Ser. A. 457 (2001), 949–952.
• [58] L. Zhang, Hausdorff dimension of limsup random fractals, Electron J. Probab. 18 (2012), no. 39, 26 pp.


text:
# Cluster Sampling involving Design Effect

A survey of residents is performed using cluster sampling. The design effect is 3.00. From the survey, the estimated proportion of people who are happy with their insurance company is 0.42 with a standard error of 0.05. How many people were in the sample?

Can someone please explain as to how I am to do this?

Thank you

• Please add the [self-study] tag & read its wiki. Then tell us what you understand thus far, what you've tried & where you're stuck. We'll provide hints to help you get unstuck. – gung Jul 4 '15 at 0:32


text:
## CryptoDB

### Paper: Automatic Generation of Sound Zero-Knowledge Protocols

Authors: Endre Bangerter Jan Camenisch Stephan Krenn Ahmad-Reza Sadeghi Thomas Schneider URL: http://eprint.iacr.org/2008/471 Search ePrint Search Google Efficient zero-knowledge proofs of knowledge (ZK-PoK) are basic building blocks of many practical cryptographic applications such as identification schemes, group signatures, and secure multiparty computation. Currently, first applications that essentially rely on ZK-POKs are being deployed in the real world. The most prominent example is Direct Anonymous Attestation (DAA), which was adopted by the Trusted Computing Group (TCG) and implemented as one of the functionalities of the cryptographic chip Trusted Platform Module (TPM). Implementing systems using ZK-PoK turns out to be challenging, since ZK-PoK are, loosely speaking, significantly more complex than standard crypto primitives, such as encryption and signature schemes. As a result, implementation cycles of ZK-PoK are time-consuming and error-prone, in particular for developers with minor or no cryptographic skills. To overcome these challenges, we have designed and implemented a compiler with corresponding languages that given a high-level ZK-PoK protocol specification automatically generates a sound implementation of this. The output is given in form of $\Sigma$-protocols, which are the most efficient protocols for ZK-PoK currently known. Our compiler translates ZK-PoK protocol specifications, written in a high-level protocol description language, into Java code or \LaTeX\ documentation of the protocol. The compiler is based on a unified theoretical framework that encompasses a large number of existing ZK-PoK techniques. Within this framework we present a new efficient ZK-PoK protocol for exponentiation homomorphisms in hidden order groups. Our protocol overcomes several limitations of the existing proof techniques.
##### BibTeX
@misc{eprint-2008-18155,
title={Automatic Generation of Sound Zero-Knowledge Protocols},
booktitle={IACR Eprint archive},
keywords={implementation / Zero-Knowledge, Protocol Compiler, Language Design},
url={http://eprint.iacr.org/2008/471},
note={This paper will be presented at EuroCrypt 2009 poster session. stephan.krenn@bfh.ch 14291 received 5 Nov 2008, last revised 16 Feb 2009},
author={Endre Bangerter and Jan Camenisch and Stephan Krenn and Ahmad-Reza Sadeghi and Thomas Schneider},
year=2008
}


text:
# Idempotents in commutative ring

I have proven for $e$ an idempotent in a commutative ring $R$ that there exists an isomorphism $\phi:R\rightarrow R/eR\times R/(1-e)R$ given by $r\mapsto(r,r-re)$.

Now I would like to prove that the idempotents of $R$ correspond bijectively to the 'decompositions' of $R$ as a product of $R=R_1\times R_2$. However I don't fully understand what is meant by this or how to do this. I understood that somehow I have to do something with the sets $\{(e,1-e):\text{e idempotent}\}$ and $\{(R_1,R_2):R=R_1\times R_2\}$ and the maps $R_1\times R_2\mapsto((0,1),(1,0))$ and $(e,1-e)\mapsto R/eR\times R/(1-e)R$.

Extra: I also want to prove that the set of idempotents in $R$ are a ring with the 'usual' multiplication and addition defined by $x+y=(x-y)^2$. Do I have to use the above for this proof (if yes, how) or is this 'easily' done without it?

However I don't fully understand what is meant by this or how to do this.

Expressing it as $\phi:R\rightarrow R/eR\times R/(1-e)R$ is a little weird considering that $R=eR\oplus (1-e)R$ as a direct sum of ideals. No isomorphism is needed. The two things match since $eR\cong R/(1-e)R$ and $(1-e)R\cong R/eR$ as rings. I guess if you are armed with the Chinese remainder theorem, the isomorphism is give for free. Hi it does not really help you understand decompositions.

Really, you would like to prove that for ideals $R_1$ and $R_2$ of $R$, then $R=R_1\oplus R_2$ iff there is an idempotent $e$ in $R$ such that $eR=R_1$ and $(1-e)R=R_2$.

It's easy to show that $R=eR\oplus (1-e)R$. Conversely, suppose $R=R_1\oplus R_2$ and think about what the identity $1$ must look like in terms of $R_1\oplus R_2$. This establishes the link between the idempotent and a particular splitting of $R$ into two pieces.

This is the same thing as considering $R=R_1\times R_2$ as a direct product of rings since you can just view $R_1\times \{0\}$ and $\{0\}\times R_2$ as two ideals which add up to $R$.

I also want to prove that the set of idempotents in $R$ are a ring with the 'usual' multiplication and addition defined by $x+y=(x−y)^2$. Do I have to use the above for this proof (if yes, how) or is this 'easily' done without it?

The proof above seems unrelated. Just verify that the set of idempotents is a group under the new addition operation, and that multiplication appropriately distributes.

## Generally

• For any idempotent in $R$, $eRe$ is a subring of $R$ with identity $e$.
• If $e$ is a central idempotent, $eRe=eR$ and you get this splitting of the ring. Splittings of the ring correspond to central idempotents.
• For a noncentral idempotent, you get $R=eR\oplus (1-e)R$ as right $R$ modules, still. (And a similar statement as left $R$ modules.) Splittings as a module correspond to idempotents.
• For any idempotent $e$, you have $R\cong \begin{bmatrix}eRe&eR(1-e)\\(1-e)Re&(1-e)R(1-e)\end{bmatrix}$ with formal matrix multiplication. As you can see, when $e$ is central the off-diagonal entries are zero, and you're looking at a "block sum" of two rings $eRe$ and $(1-e)R(1-e)$.
• The $\phi$-isomorphism part is done already, that's not a problem. But can you help me with the bijective correspondence part and those maps? – user235238 Sep 18 '15 at 19:05
• @TonyStrong That is the purpose of the entire first half of this post. For every idempotent there is a decomposition, for every decomposition there is an idempotent. – rschwieb Sep 18 '15 at 19:52
• But how do I use those maps i described? – user235238 Sep 18 '15 at 21:07
• @TonyStrong I don't think it is a good use of time to use that map to the product of quotients. The point is that in $R_1\times R_2$, $e=(1,0)$ and $(1-e)=(0,1)$ are idempotents, and $R=eR\oplus (1-e)R$ and $eR\cong R_1$ and $(1-e)R\cong R_2$. You can go further and show $eR\cong R/(1-e)R$, but I don't see what advantage there is. – rschwieb Sep 19 '15 at 3:12


text:
# Enforcing Compliance using the AWS Ansible Collection

WORDS BY   Manca Bizjak

If you are responsible for managing a bunch of your organization’s AWS resources, you probably know how annoying it is to debug various deployment-related issues, only to learn that someone accidentally messed with your setup, yet again. Which you probably resolved by navigating your command-line history like a maniac (because you don’t use Ansible and have to Ctrl+R, as you also forgot to put down the setup instructions ;)). We’ve been there, too. And this is what we learned:

1. You should use Ansible and deploy your environment with a playbook, and
2. You should make the most of it by taking advantage of both Ansible’s built-in mechanisms and the modules that allow you to detect configuration drift, and correct it.

Our dear sysadmins and DevOps engineers, this post is for you. Stay with us and read along!

## Ansible and compliance? How?

According to Cambridge Advanced Learner’s Dictionary, compliance is

The fact of obeying a particular law or rule, or of acting according to an agreement.

To see what the above definition has got to do with Ansible and the AWS Ansible Collection, let’s briefly descend to the world of Ansible playbooks and modules.

Ideally, playbook tasks describe the desired final state of a managed system - for example, configuration of an AWS EC2 instance. An Ansible module takes that description and performs the necessary steps to ensure that state.

It’s important to emphasize that it’s easy to write playbook tasks describing the final state of a managed system when Ansible modules adopt declarative APIs. As a consequence, we can treat playbook tasks as “the rule”, “the policy”, or simply as something we need to be compliant with. Perhaps even more importantly, we can treat Ansible playbooks as simple diagnostic tools to help us detect when we are not compliant anymore, so that we can mitigate the situation.

If you are familiar with Ansible, all of this probably rings a bell to you already. Was your first thought the value of the changed variable that you see every time you run your playbooks? Or perhaps even Ansible’s --diff and --check modes? Indeed, this post is about all of them!

Let’s walk through a practical example demonstrating how you can use the modules from the AWS Ansible Collection to detect and resolve configuration drift.

To follow along easier, make sure you have completed the tutorial about the basic usage of the collection in Getting Started with the AWS Ansible Collection.

Make sure you have Steampunk AWS Ansible Collection version 0.8.3 installed.

## Set up the desired state

Let’s start by creating a simple AWS enviromnent that will support running an imaginary app. The environment will comprise:

• an EC2 instance named steamy-server;
• a network interface named steamy-eni to attach to the EC2 instance, which we secure with the VPC’s default security group.

We created a playbook called setup.yaml for spinning up this environment. And then, we run

$ansible-playbook setup.yaml --diff  Output: PLAY [localhost] ************************************************************ TASK [Create the steamy-server instance for running a simple app] *********** --- before +++ after @@ -1 +1,24 @@ -{} +{ + "ami": "ami-085925f297f89fce1", + "availability_zone": "use1-az1", + "id": "i-0f1300d2456233353", + "key_pair": "test-keypair", + "launched_at": "2020-06-12T07:35:19+00:00", + "monitoring": "detailed", + "network_interface": "eni-0cf22a025bd9f7c98", + "on_instance_initiated_shutdown": "stop", + "secondary_network_interfaces": [], + "security_groups": [ + "sg-0415ac333af261fc1" + ], + "state": "running", + "subnet": "subnet-06a0f705bc79538ed", + "tags": { + "Name": "steamy-server", + "app": "steamy", + "env": "staging" + }, + "tenancy": "default", + "type": "t3.micro", + "vpc": "vpc-032c4ec6c40cf17a3" +} changed: [localhost] TASK [Retrieve the default security group for the VPC] ********************** ok: [localhost] TASK [Create a dedicated network interface and attach it to steamy-server] ** --- before +++ after @@ -1 +1,21 @@ -{} +{ + "attachment": { + "device_index": 1, + "instance": "i-0f1300d2456233353", + "keep_on_termination": false + }, + "description": null, + "id": "eni-0c7d09f8e5290b78d", + "ip": "172.31.6.213", + "mac_address": "02:5b:f9:a2:db:fd", + "public_ip": null, + "security_groups": [ + "sg-0415ac333af261fc1" + ], + "source_dest_check": true, + "subnet": "subnet-06a0f705bc79538ed", + "tags": { + "Name": "steamy-eni" + }, + "type": "normal" +} changed: [localhost] PLAY RECAP ****************************************************************** localhost : ok=3 changed=2 unreachable=0 failed=0 skipped=0 rescued=0 ignored=0  We can see two changed tasks, corresponding to the two newly created AWS resources. Thanks to the --diff flag which instructs the modules to report the differences they made, we also get a nice visual indication of what exactly the modules changed. The red-colored lines show the previous state of the AWS resource (before a specific task ran), while the green ones show the current state, i.e. after the task ran. We can interpret the diff output above as “the instance and network interface didn’t exist before, so we created them, and they are now configured as shown”. Typically, we can’t take support for diff mode for granted, as it is up to individual modules to implement it. This is why some tasks make changes but report no differences despite running ansible-playbook with --diff. ### A word about idempotence Can you guess what will happen if we run the same command again? Let’s try it out! $ ansible-playbook setup.yaml --diff

Output:

PLAY [localhost] ************************************************************

TASK [Create the steamy-server instance for running a simple app] ***********
ok: [localhost]

TASK [Retrieve the default security group for the VPC] **********************
ok: [localhost]

TASK [Create a dedicated network interface and attach it to steamy-server] **
ok: [localhost]

PLAY RECAP ******************************************************************
localhost              : ok=3         changed=0    unreachable=0    failed=0
skipped=0    rescued=0    ignored=0

This time around, we see that there was nothing to be done - the Ansible modules already did all the hard work when they were invoked the first time. So no changed tasks, no updates done, and no diff output shown. With other words, the current state of our managed AWS resources is compliant with the state described by the tasks in our setup.yaml playbook. This demonstrates another important aspect related to Ansible’s declarative approach, which is that playbook tasks should ideally be idempotent. If the state of the managed resource is aligned with the desired state as described by the playbook tasks, running the playbook again will not affect its state.

But how can all of this be useful to me, you wonder? Glad you asked, time to spice things up a bit!

## Deviate from the initial state

Now, let’s put ourselves in the shoes of an adversary that wants to tweak the state of our AWS resources to their taste. In practice, this could be done accidentally, or worse - with malicious intent. But we’ll be doing it solely for the purpose of demonstration. Disclaimer: we won’t actually be doing anything dangerous, we’ll only make some simple configuration changes that should indicate that configuration has drifted if we take setup.yaml as our baseline for compliance.

To make the changes, we could open the AWS Management Console and manually modify some properties of the EC2 instance or the network interface that we created with [setup.yaml][setup earlier. But since we’re all about automation, let’s put the tweaks in an Ansible playbook called tweaked-setup.yaml.

Here’s a recap of what we’ll be tweaking with this playbook:

• We’ll downgrade our steamy-server’s CloudWatch monitoring to the basic level and modify it’s shutdown behavior;
• We’ll update the value of steamy-server’s env tag.
• We’ll create a new security group called dangerous-secgroup with some suspicious permissions;
• We’ll associate this dangerous-secgroup with the network interface attached to the steamy-server instance, and we’ll also disable source/destination checking for the network interface;

Sneaky, right? ;)

If we ran ansible-playbook tweaked-setup.yaml now, we would end up with three changed tasks. But since we’re learning about Ansible diff mode, let’s do:

$ansible-playbook tweaked-setup.yaml --diff  and we end up with three changed tasks, plus the diff output consistent with the tweaks described above: PLAY [localhost] ************************************************************ TASK [Retrieve the steamy-server instance] ********************************** ok: [localhost] TASK [Modify configuration of the steamy-server instance] ******************* --- before +++ after @@ -4,9 +4,9 @@ "id": "i-0f1300d2456233353", "key_pair": "test-keypair", "launched_at": "2020-06-12T07:35:19+00:00", - "monitoring": "detailed", + "monitoring": "basic", "network_interface": "eni-0cf22a025bd9f7c98", - "on_instance_initiated_shutdown": "stop", + "on_instance_initiated_shutdown": "terminate", "secondary_network_interfaces": [ "eni-0c7d09f8e5290b78d" ], @@ -18,7 +18,7 @@ "tags": { "Name": "steamy-server", "app": "steamy", - "env": "staging" + "env": "dev" }, "tenancy": "default", "type": "t3.micro", changed: [localhost] TASK [Create a security group to permit SMB traffic from anywhere] ********** changed: [localhost] TASK [Extend steamy-eni's security groups, and update source/dest checking] * --- before +++ after @@ -10,9 +10,10 @@ "mac_address": "02:5b:f9:a2:db:fd", "public_ip": null, "security_groups": [ + "sg-0447e7e7bc88aeab1", "sg-0415ac333af261fc1" ], - "source_dest_check": true, + "source_dest_check": false, "subnet": "subnet-d8b640be", "tags": { "Name": "steamy-eni" changed: [localhost] PLAY RECAP ****************************************************************** localhost : ok=4 changed=3 unreachable=0 failed=0 skipped=0 rescued=0 ignored=0  Basically, tweaked-setup.yaml introduced an alternative desired state of the AWS resources - the adversary’s. And this state is not exactly in agreement with the one we described in setup.yaml (we already learned that if it were, the last invocation of ansible-playbook would report no changed tasks!). ## Detect configuration drift Let’s now imagine that one day, we get a call from our teammates who report unusual traffic to the app server instance we provisioned on AWS, using our setup.yaml. Luckily, we know what to do; for starters, we’ll try re-running the setup.yaml playbook, but with one important addition: this time we’ll add the --check flag to the ansible-playbook command. The --check flag instructs the modules behind playbook tasks to run in check mode (also called dry run). In check mode, a module does not perform any work that would change the state of the resource it manages. Instead, the module merely checks whether a change would need to be made to ensure the desired state. This is evident from the module’s changed value, and you might already be familiar with it. $ ansible-playbook setup.yaml --check

Output:

PLAY [localhost] ************************************************************

TASK [Create the steamy-server instance for running a simple app] ***********
changed: [localhost]

TASK [Retrieve the default security group for the VPC] **********************
ok: [localhost]

TASK [Create a dedicated network interface and attach it to steamy-server] **
changed: [localhost]

PLAY RECAP ******************************************************************
localhost              : ok=3         changed=2    unreachable=0    failed=0
skipped=0    rescued=0    ignored=0

We notice something peculiar in the above output: two changed tasks. This could very well be the related to the problem our teammates reported. But at this point, it’s too early to make any conclusions. We only know that something has changed on the instance and network interface with respect to how we want them configured.

However, our goal is not only to verify that a configuration has drifted, but to pinpoint exactly what deviated from the desired state. Luckily, we have another trick up our sleeve. You guessed it, it’s as simple as adding our beloved --diff flag to the previous ansible-playbook --check command:

$ansible-playbook setup.yaml --check --diff  Output: PLAY [localhost] ************************************************************ TASK [Create the steamy-server instance for running a simple app] *********** --- before +++ after @@ -4,9 +4,9 @@ "id": "i-0f1300d2456233353", "key_pair": "test-keypair", "launched_at": "2020-06-12T07:35:19+00:00", - "monitoring": "basic", + "monitoring": "detailed", "network_interface": "eni-0cf22a025bd9f7c98", - "on_instance_initiated_shutdown": "terminate", + "on_instance_initiated_shutdown": "stop", "secondary_network_interfaces": [ "eni-0c7d09f8e5290b78d" ], @@ -18,7 +18,7 @@ "tags": { "Name": "steamy-server", "app": "steamy", - "env": "dev" + "env": "staging" }, "tenancy": "default", "type": "t3.micro", changed: [localhost] TASK [Retrieve the default security group for the VPC] ********************** ok: [localhost] TASK [Create a dedicated network interface and attach it to steamy-server] ** --- before +++ after @@ -10,10 +10,9 @@ "mac_address": "02:5b:f9:a2:db:fd", "public_ip": null, "security_groups": [ - "sg-0447e7e7bc88aeab1", "sg-0415ac333af261fc1" ], - "source_dest_check": false, + "source_dest_check": true, "subnet": "subnet-d8b640be", "tags": { "Name": "steamy-eni" changed: [localhost] PLAY RECAP ****************************************************************** localhost : ok=3 changed=2 unreachable=0 failed=0 skipped=0 rescued=0 ignored=0  If we compare the output of this command and the output of ansible-playbook tweaked-setup.yaml --diff that we ran earlier, we can see that they’re exactly the opposite. So the last ansible-playbook command we ran detected what tweaked-setup.yaml modified in our desired AWS setup. And if we we weren’t running in check mode, we could actually … ## Enforce compliance! Fear not - our setup.yaml describes the desired configuration state of our AWS resources exactly, so the modules from the AWS Ansible Collection know what to do. To repair our setup, i.e. to bring it back to the desired state, let’s run ansible-playbook command once more, but this time without --check: $ ansible-playbook setup.yaml --diff

And we can observe exactly the same output as with the previous command. This time however, the modules actually performed the changes shown in the diff output.

Afterwards, we can try running the same command again and we should end up with no changed tasks, once again. This indicates that the configuration state of our AWS resources is up-to-date with the configuration described in our setup.yaml playbook. And we are compliant with our baseline setup!

## But I get no output with my playbooks

As we said before, not all modules support running in check mode or displaying differences between the before and after states. Our AWS Ansible Collection was designed with this use case in mind, so make sure you check it out.

## What’s next?

In this post we demonstrated the value of Ansible’s --diff and --check mode and how we can use the modules in the AWS Ansible Collection to detect configuration drift, which makes them suitable as a tool to ensure compliance of the state of AWS resources. Perhaps the nicest thing in this whole story is that we used the same playbook for setting up the infrastructure, detecting the changes, and restoring our setup back to the desired state.

In our example, we ran the compliance checks using --check --diff after receiving an imaginary report about unusual behavior of the app running on our AWS resources. Try to imagine a similar situation, but with a real-world app deployment. How many of the app’s users could be affected and possibly discouraged from interacting with the app ever again, before state alterations (accidental or not) were discovered, reported, and, finally, fixed? So if we wanted to take things a bit further, we could implement automated checks that would periodically run ansible-playbook setup.yaml --check --diff` command. This way, we could increase the chances of picking up anomalies, and be notified of similar situations before anyone notices.

If you have any questions, troubles, or doubts, you can always reach us on Twitter, LinkedIn, and Reddit. Thank you for checking out this post for a different perspective on simple Ansible concepts (get it?;)).

So long!


text:
## Elementary Algebra

Let X represent the amount of gasoline required to travel 238 miles. Now, let’s set up a proportion in which one ratio compares the amounts of gasoline and the other ratio compares the corresponding distance. So, $\frac{10}{X}$ = $\frac{170}{238}$ We cross multiply to obtain: 10 $\times$ 238 = X $\times$ 170 2380 = 170X Divide both sides by 170. X = 14 The car will need 14 gallons of gasoline to travel 238 miles.


text:
# Goodstein's theorem without transfinite induction

Is it possible to prove Goodstein's theorem without transfinite induction? Is there such a proof?

-

I'm pretty sure the short answer is "no" (if you mean, can you prove Goodstein's theorem without invoking apparatus as strong as a transfinite induction which can't be reduced to an ordinary induction). For if I recall correctly, Goodstein's theorem is actually equivalent (over a weak base theory) to transfinite induction up to $\varepsilon_0$. My first port of call to check this would be Kirby and Paris's paper on 'Accessible independence results for Peano Arithmetic'.

-
I can't tell if you are just being modest, but the phrasing of your reply suggests some uncertainty. If so, please let me assure you that I believe that your answer is exactly correct. –  MJD Dec 17 '12 at 14:41
I studied this a bit further. I guess that we need transfinite induction if we stick with first-order logic(?). If we allow quantification over sets, could we do with ordinal induction? I ask because I came across this link math.niu.edu/~rusin/known-math/00_incoming/goodstein Notice the the comment by Torkel Franzen. –  rank Dec 17 '12 at 19:23

I found the following paper which seems fairly relevant:

Miller J.T. On the independence of Goodstein’s theorem. 2001, Citeseer.

-
Very interesting link, thank you! But I'm afraid it does not (directly) address the question? (I didn't read it through yet, though..) –  rank Dec 17 '12 at 19:25
@rank: Look at the section about the independence itself. This means that you cannot prove the theorem from first-order PA without some extra assumptions, which are ultimately equivalent to the transfinite induction. –  Asaf Karagila Dec 17 '12 at 19:46


text:
# How to estimate the frequency characteristics of a nonlinear chirp?

Given a partial time-domain recording of a noise-corrupted chirp that asymptotically approaches a frequency, and the function that determines the non-linearity, how can I accurately estimate the final frequency it approaches?

Here's an example of what I'm talking about. A radio receiver hears noise until around sample x=5100, then the chirp starts at f=0, and quickly sweeps up to an unknown frequency, but then fades out around x=5500 to some annoying filter ringing caused by a hardware front-end band-pass filter.

X: sample count, Y: ADC count

Ideal solution will have the following characteristics:

1. Accurately predict the final frequency
2. Work over a range of final frequencies
3. Be invariant to different starting frequencies
4. Be invariant to different stopping frequencies
5. Relatively quick to compute

Approaches Tried So Far:

1. Estimating instantaneous frequency using zero-crossing, then curve-fitting. It seems that noise and filter-ringing causes errors in the frequency calculation that make it very sensitive to slight changes in waveform shape. It works better but not well if the signal is resampled to a higher sample-rate first.

2. Estimating instantaneous frequency using autocorrelation, then curve-fitting using the strongest lags from autocorrelation Function. This works well given knowledge of the incoming frequency so that the autocorrelation window size can be picked ahead of time, but fails when the ACF window isn't wide enough to see the whole signal. If the ACF is too wide, it'll sometimes see a harmonic as the strongest lag.

3. Curve-fitting the raw signal. This tends not to converge if there's even a little error in the initial conditions, or noise in the signal.

4. FFT/STFT, then curve-fitting the bins. What I ran into here was that it seemed the bins were destroying the shape of the signal. I couldn't find a good size of bin that gave enough frequency-resolution and time-resolution.

An example recording is available here.

• Have you tried a PLL-based approach? – Marcus Müller Dec 3 '18 at 11:06
• I haven't tried a PLL-based approach yet. – rsaxvc Dec 3 '18 at 20:09

How about just using $$\dfrac{d\phi}{dt}$$ to compute the instantaneous frequency?

GNU Octave code (I just made up a sample rate of 2 Msps):

pkg load signal;
y = hilbert(x);
z = y - mean(real(y));
dphi_dt = diff(unwrap(arg(z)));
Fs = 2e6;
f_inst = (Fs/2)/pi * dphi_dt;
k = [0:length(f_inst)-1];
t = k/Fs;
plot(k, f_inst);
axis([5000 5800 -2e5 2e5]);
title('Instantaneous Frequency');
xlabel('Sample index');
ylabel('Frequency (Hz)');
grid on;

• I think this is exactly what I'm looking for and will likely accept the answer in a few days once I've had time to test it. – rsaxvc Dec 3 '18 at 21:28
• Ok. I played a little fast and loose with removing the DC component of the analytic signal and also in just winging in tbe hilbert function to make the analytic signal. Normally I build a single sided complex BPF that goes from DC to $+Fs/2$. – Andy Walls Dec 3 '18 at 22:25
• There is also a slightly more clever way to compute $d\phi/dt$ without having to use diff() and unwrap(). One takes the $\mathrm{Arg}(z[n]z^*[n-1])$, but I didn't feel like writing a loop in Octave/Matlab. – Andy Walls Dec 3 '18 at 22:31
• I should also mention that the first difference is an approximate derivative filter, that is best close to DC but isn't very good the closer you get to $\pm F_s/2$. A good derivative filter isn't hard, but how to choose/design is another separate question that requires your performamce requirememts s to be better specified. – Andy Walls Dec 3 '18 at 22:53
• Ok. But because your input signal was real, you can not make a distinction between positive and negative frequencies. So with only real input, you can only estimate frequencies in $[0, +F_s/2]$. If you have both I & Q on input, then you can talk about negative frequencies too. – Andy Walls Dec 4 '18 at 3:25