diff options
Diffstat (limited to 'Английский язык/Final Practice/practice.tex')
| -rw-r--r-- | Английский язык/Final Practice/practice.tex | 1338 |
1 files changed, 1338 insertions, 0 deletions
diff --git a/Английский язык/Final Practice/practice.tex b/Английский язык/Final Practice/practice.tex new file mode 100644 index 0000000..29aee19 --- /dev/null +++ b/Английский язык/Final Practice/practice.tex @@ -0,0 +1,1338 @@ +\documentclass[spec, och, coursework-kb]{SCWorks} +\usepackage{preamble} +\usepackage{underscore} + +\title{Сравнение различных достаточных условий гамильтоновости графов} +\author{Гущина Андрея Юрьевича} % Фамилия, имя, отчество в родительном падеже + +\begin{document} +% \input{titlepage.tex} + +\section{Письменный перевод деловых писем} + +\subsection*{Письмо №1} + +\begin{flushleft} + Jessica Parker, \newline + Astonway Street, 34, \newline + London, 23456 \newline + 27th of May +\end{flushleft} + +\begin{flushleft} + Christine Goward \newline + Relax Hotel, \newline + Burning Street, 7, \newline + London, 76535 +\end{flushleft} + +Dear Miss Goward, + +I am writing to you on behalf of Pear Incorporated to express our sincere +gratitude for your continued support and to discuss a potential business +opportunity. + +We have been following your company's remarkable growth and outstanding +achievements in the agriculture and food industry with great admiration. As a +leading player in the production of fertilizers, we believe that a strategic +partnership between our organizations could bring about significant mutual +benefits and drive further success. + +At Pear Incorporated, we specialize in production of high quality fertilizers +that with our own proprietary formulas. Our innovative solutions have +consistently helped businesses like yours enhance operational efficiency, +increase profitability, and stay ahead in this ever-evolving market. We are +confident that our expertise and resources align perfectly with your needs. + +Our proposal entails selling you large quantities of our best products for your +fields. Also we consider sending you preview batches of our newest formulas. +We have carefully analyzed the market trends and competitive landscape, and we +firmly believe that by joining forces, we can leverage our respective strengths +to create a formidable alliance that will captivate the market and foster +sustainable growth. + +Furthermore, we would be delighted to arrange a meeting at your convenience to +discuss this opportunity in detail. Our team of experts is eager to showcase how +our collaboration can unlock new possibilities and drive transformative results +for both our organizations. Please let us know your preferred date and time, and +we will ensure that all necessary arrangements are made promptly. + +Thank you for considering this proposal. We genuinely believe that working +together will not only amplify our collective potential but also pave the way +for greater achievements and shared success. + +Please feel free to contact me directly via email or phone if you have any +questions or require further information. We look forward to the possibility of +collaborating with your esteemed organization. + +Yours sincerely, +\begin{flushleft} + Jessica Parker \newline + Head of marketing \newline + Pear Incorporated +\end{flushleft} + +\subsection*{Перевод письма №1} + +\begin{flushleft} + Джессика Паркер, \newline + ул. Астонвэй, 34, \newline + Лондон, 23456 \newline + 27 мая +\end{flushleft} + +\begin{flushleft} + Кристина Говард \newline + отель Relax, \newline + ул. Бёрнинг, 7, \newline + Лондон, 76535 +\end{flushleft} + +Уважаемая мисс Говард, + +Я пишу вам от имени компании Pear Incorporated, чтобы выразить нашу искреннюю +благодарность за вашу постоянную поддержку и обсудить потенциальное деловое +сотрудничество. + +Мы следили за замечательным ростом вашей компании и выдающимися достижениями +в сельском хозяйстве и пищевой промышленности с большим восхищением. Являясь +ведущим игроком в производстве удобрений, мы считаем, что стратегическое +партнерство между нашими организациями может принести значительную взаимную +выгоды и способствовать дальнейшему успеху. + +Компания Pear Incorporated специализируется на производстве высококачественных +удобрений с использованием наших собственных запатентованных формул. Наши +инновационные решения постоянно помогают таким предприятиям, как ваше, повышать +операционную эффективность, повысить рентабельность и оставаться впереди на +этом постоянно развивающемся рынке. Мы уверены, что наш опыт и ресурсы идеально +соответствуют вашим потребностям. + +Наше предложение подразумевает продажу вам большого количества нашей лучшей +продукции для ваших полей. Также мы рассматриваем возможность отправления вам +предварительных партий наших новейших формул. Мы тщательно проанализировали +тенденции рынка и конкурентную среду, и мы твердо уверены, что, объединив +усилия, мы сможем использовать наши сильные стороны для создания грозного +альянса, который захватит рынок и будет способствовать устойчивый рост. + +Более того, мы будем рады организовать встречу в удобное для вас время, чтобы +обсудить эту возможность в деталях. Наша команда экспертов с нетерпением ждет +возможности продемонстрировать, как наше сотрудничество может открыть новые +возможности и обеспечить преобразующие результаты для обеих наших организаций. +Пожалуйста, сообщите нам желаемую дату и время, и мы обеспечим оперативное +принятие всех необходимых мер. + +Благодарим вас за рассмотрение этого предложения. Мы искренне верим, что +совместная работа вместе не только усилит наш коллективный потенциал, но и +проложит путь для больших достижений и общего успеха. + +Пожалуйста, свяжитесь со мной напрямую по электронной почте или по телефону, +если у вас возникнут вопросы или потребуется дополнительная информация. Мы с +нетерпением возможности сотрудничества с вашей уважаемой организацией. + +Искренне Ваша, +\begin{flushleft} + Джессика Паркер \newline + Руководитель отдела маркетинга \newline + Pear Incorporated +\end{flushleft} + + +\subsection*{Письмо №2} + +\begin{flushleft} + Александр Хлебушкин, \newline + ул. Пушкина, 20, \newline + Саратов, 23456 \newline + 27 мая +\end{flushleft} + +\begin{flushleft} + Иван Улитин \newline + ул. Колотушкина, 95, \newline + Подольск, 76535 +\end{flushleft} + +Уважаемый Иван Владимирович, + +Я пишу Вам от имени компании "ABC", которая занимается производством электронных компонентов. Мы заинтересованы в закупке электронных чипов и хотели бы запросить у Вас дополнительную информацию по этому вопросу. + +Мы обратились к Вам, так как Ваша компания "XYZ" является одним из лидеров в производстве электронных компонентов, и мы уверены, что Ваш опыт и знания могут помочь нам в достижении наших целей. + +Мы были бы признательны, если бы Вы могли предоставить нам следующую информацию: + +\begin{itemize} + \item Цена на электронные чипы типа "A12-45" + \item Минимальный заказ и наличие на складе + \item Сроки доставки до нашего производства в г. Новосибирск +\end{itemize} + +Мы бы также хотели узнать, сможете ли Вы предоставить нам услуги или продукты, соответствующие нашим требованиям, а также информацию о стоимости и сроках выполнения работ. + +Мы понимаем, что Ваше время ценно, и поэтому будем благодарны за любую информацию, которую Вы можете предоставить в ответ на наш запрос. + +Если у Вас есть какие-либо вопросы или требуется дополнительная информация от нас, пожалуйста, не стесняйтесь обратиться к нам. + +\begin{flushleft} +С уважением, \newline +Александр Хлебушкин \newline +Компания "ABC" +\end{flushleft} + +\subsection*{Перевод письма №2} + +\begin{flushleft} + Alexander Khlebushkin, \newline + Pushkina street, 20, \newline + Saratov, 23456 \newline + 27th of May +\end{flushleft} + +\begin{flushleft} + Ivan Ulitin \newline + Kolotushkina street, 95, \newline + Podolsk, 76535 +\end{flushleft} + +Dear Mr. Ulitin, + +I am writing to you on behalf of the company "ABC", which is engaged in the production of electronic components. We are interested in purchasing electronic chips and would like to request more information from you on this matter. + +We have approached you as your company "XYZ" is one of the leaders in the manufacture of electronic components and we are confident that your experience and expertise can help us achieve our goals. + +We would appreciate if you could give us the following information: + +\begin{itemize} + \item Price of electronic chips such as "A12-45" + \item Minimum order and stock availability + \item Time of delivery to our production in Novosibirsk +\end{itemize} + +We would also like to know if you can provide us with services or products that meet our requirements, as well as information about costs and lead times. + +We understand that your time is valuable, so any information you can give us in response to our request would be greatly appreciated. + +If you have any questions or require additional information from us, please feel free to contact us. + +\begin{flushleft} +Regards, \newline +Alexander Khlebushkin \newline +ABC Company \newline +\end{flushleft} + +\section{Перевод статей профессиональной направленности} + +\subsection*{Статья} + +At Cloudflare, engineers spend a great deal of time refactoring or rewriting +existing functionality. When your company doubles the amount of traffic it +handles every year, what was once an elegant solution to a problem can quickly +become outdated as the engineering constraints change. Not only that, but when +you're averaging 40 million requests a second, issues that might affect 0.001\% +of requests flowing through our network are big incidents which may impact +millions of users, and one-in-a-trillion events happen several times a day. + +Recently, we've been working on a replacement to one of our oldest and +least-well-known components called cf-html, which lives inside the core reverse +web proxy of Cloudflare known as FL (Front Line). Cf-html is the framework in +charge of parsing and rewriting HTML as it streams back through from the website +origin to the website visitor. Since the early days of Cloudflare, we’ve offered +features which will rewrite the response body of web requests for you on the +fly. The first ever feature we wrote in this way was to replace email addresses +with chunks of JavaScript, which would then load the email address when viewed +in a web browser. Since bots are often unable to evaluate JavaScript, this +helps to prevent scraping of email addresses from websites. You can see this +in action if you view the source of this page and look for this email address: +foo@example.com. + +FL is where most of the application infrastructure logic for Cloudflare runs, +and largely consists of code written in the Lua scripting language, which runs +on top of NGINX as part of OpenResty. In order to interface with NGINX directly, +some parts (like cf-html) are written in lower-level languages like C and +C++. In the past, there were many such OpenResty services at Cloudflare, but +these days FL is one of the few left, as we move other components to Workers +or Rust-based proxies. The platform that once was the best possible blend of +developer ease and speed has more than started to show its age for us. + +When discussing what happens to an HTTP request passing through our network and +in particular FL, nearly all the attention is given to what happens up until +the request reaches the customer's origin. That’s understandable as this is +where most of the business logic happens: firewall rules, Workers, and routing +decisions all happen on the request. But it's not the end of the story. From +an engineering perspective, much of the more interesting work happens on the +response, as we stream the HTML response back from the origin to the site +visitor. + +The logic to handle this is contained in a static NGINX module, and runs in the +Response Body Filters phase in NGINX, as chunks of the HTTP response body are +streamed through. Over time, more features were added, and the system became +known as cf-html. cf-html uses a streaming HTML parser to match on specific HTML +tags and content, called Lazy HTML or lhtml, with much of the logic for both it +and the cf-html features written using the Ragel state machine engine. + +All the cf-html logic was written in C, and therefore was susceptible to memory +corruption issues that plague many large C codebases. In 2017 this led to a +security bug as the team was trying to replace part of cf-html. FL was reading +arbitrary data from memory and appending it to response bodies. This could +potentially include data from other requests passing through FL at the same +time. This security event became known widely as Cloudbleed. + +Since this episode, Cloudflare implemented a number of policies and safeguards +to ensure something like that never happened again. While work has been carried +out on cf-html over the years, there have been few new features implemented on +the framework, and we’re now hyper-sensitive to crashes happening in FL (and, +indeed, any other process running on our network), especially in parts that can +reflect data back with a response. + +Fast-forward to 2022 into 2023, and the FL Platform team have been getting +more and more requests for a system they can easily use to look at and rewrite +response body data. At the same time, another team has been working on a new +response body parsing and rewriting framework for Workers called lol-html or +Low Output Latency HTML. Not only is lol-html faster and more efficient than +Lazy HTML, but it’s also currently in full production use as part of the Worker +interface, and written in Rust, which is much safer than C in terms of its +handling of memory. It’s ideal, therefore, as a replacement for the ancient and +creaking HTML parser we’ve been using in FL up until now. + +So we started working on a new framework, written in Rust, that would +incorporate lol-html and allow other teams to write response body parsing +features without the threat of causing massive security issues. The new system +is called ROFL or Response Overseer for FL, and it’s a brand-new NGINX module +written completely in Rust. As of now, ROFL is running in production on millions +of responses a second, with comparable performance to cf-html. In building ROFL, +we’ve been able to deprecate one of the scariest bits of code in Cloudflare’s +entire codebase, while providing teams at Cloudflare with a robust system they +can use to write features which need to parse and rewrite response body data. +Writing an NGINX module in Rust + +While writing the new module, we learned a lot about how NGINX works, and how we +can get it to talk to Rust. NGINX doesn’t provide much documentation on writing +modules written in languages other than C, and so there was some work which +needed to be done to figure out how to write an NGINX module in our language +of choice. When starting out, we made heavy use of parts of the code from the +nginx-rs project, particularly around the handling of buffers and memory pools. +While writing a full NGINX module in Rust is a long process and beyond the scope +of this blog post, there are a few key bits that make the whole thing possible, +and that are worth talking about. + +The first one of these is generating the Rust bindings so that NGINX can +communicate with it. To do that, we used Rust’s library Bindgen to build the +FFI bindings for us, based on the symbol definitions in NGINX’s header files. +To add this to an existing Rust project, the first thing is to pull down a copy +of NGINX and configure it. Ideally this would be done in a simple script or +Makefile, but when done by hand it would look something like this: + +With NGINX in the right state, we need to create a build.rs file in our Rust +project to auto-generate the bindings at build-time of the module. We’ll now +add the necessary arguments to the build, and use Bindgen to generate us the +bindings.rs file. For the arguments, we just need to include all the directories +that may contain header files for clang to do its thing. We can then feed them +into Bindgen, along with some allowlist arguments, so it knows for what things +it should generate the bindings, and which things it can ignore. Adding a little +boilerplate code to the top, the whole file should look something like this: + +Hopefully this is all fairly self-explanatory. Bindgen traverses the NGINX +source and generates equivalent constructs in Rust in a file called bindings.rs, +which we can import into our project. There’s just one more thing to add- +Bindgen has trouble with a couple of symbols in NGINX, which we’ll need to fix +in a file called wrapper.h. + +With this in place and Bindgen set in the [build-dependencies] section of the +Cargo.toml file, we should be ready to build. + +With any luck, we should see a file called bindings.rs in the target/debug/build +directory, which contains Rust definitions of all the NGINX symbols. + +To be able to use them in the project, we can include them in a new file under +the src directory which we’ll call bindings.rs. + +With that set, we just need to add the usual imports to the top of the lib.rs +file, and we can access NGINX constructs from Rust. Not only does this make +bugs in the interface between NGINX and our Rust module much less likely than +if these values were hand-coded, but it’s also a fantastic reference we can +use to check the structure of things in NGINX when building modules in Rust, +and it takes a lot of the leg-work out of setting everything up. It’s really +a testament to the quality of a lot of Rust libraries such as Bindgen that +something like this can be done with so little effort, in a robust way. + +Once the Rust library has been built, the next step is to hook it into NGINX. +Most NGINX modules are compiled statically. That is, the module is compiled as +part of the compilation of NGINX as a whole. However, since NGINX 1.9.11, it has +supported dynamic modules, which are compiled separately and then loaded using +the load_module directive in the nginx.conf file. This is what we needed to use +to build ROFL, so that the library could be compiled separately and loaded-in +at the time NGINX starts up. Finding the right format so that the necessary +symbols could be found from the documentation was tricky, though, and although +it is possible to use a separate config file to set some of this metadata, it’s +better if we can load it as part of the module, to keep things neat. Luckily, it +doesn’t take much spelunking through the NGINX codebase to find where dlopen is +called. + +When writing an NGINX module, it’s crucial to get its order relative to the +other modules correct. Dynamic modules get loaded as NGINX starts, which means +they are (perhaps counterintuitively) the first to run on a response. Ensuring +your module runs after gzip decompression by specifying its order relative to +the gunzip module is essential, otherwise you can spend lots of time staring at +streams of unprintable characters, wondering why you aren’t seeing the response +you expected. Not fun. Fortunately this is also something that can be solved by +looking at the NGINX source, and making sure the relevant entities exist in your +module. + +We’re essentially saying we want our module rust_nginx_module to run just before +the ngx_http_headers_more_filter_module module, which should allow it to run in +the place we expect. + +One of the quirks of NGINX and OpenResty is how it is really hostile to making +calls to external services at the point that you’re dealing with the HTTP +response. It’s something that isn’t provided as part of the OpenResty Lua +framework, even though it would make working with the response phase of a +request much easier. While we could do this anyway, that would mean having to +fork NGINX and OpenResty, which would bring its own challenges. As a result, +we’ve spent a lot of time over the years thinking about ways to pass state from +the time when NGINX’s dealing with an HTTP request, over to the time when it’s +streaming through the response, and much of our logic is built around this style +of work. + +For ROFL, that means in order to determine if we need to apply a certain feature +for a response, we need to figure that out on the request, then pass that +information over to the response so that we know which features to activate. +To do that, we need to use one of the utilities that NGINX provides you with. +With the help of the bindings.rs file generated earlier, we can take a look at +the definition of the ngx_http_request_s struct, which contains all the state +associated with a given request. + +As we can see, there’s a member called ctx. As the NGINX Development Guide +mentions, it’s a place where you’re able to store any value associated with +a request, which should live for as long as the request does. In OpenResty +this is used heavily for the storing of state to do with a request over its +lifetime in a Lua context. We can do the same thing for our module, so that +settings initialised during the request phase are there when our HTML parsing +and rewriting is run in the response phase. + +Notice that ctx is at the offset of the ctx_index member of ngx_http_rofl_module +- this is the structure of type ngx_module_t that’s part of the module +definition needed to make an NGINX module. Once we have this, we can point it +to a structure containing any setting we want. + +The function is called get_or_init_ctx here- it performs the same job as +get_ctx, but also initialises the structure if it doesn’t exist yet. Once we’ve +set whatever data we need in ctx during the request, we can then check what +features need to be run in the response, without having to make any calls to +external databases, which might slow us down. + +One of the nice things about storing state on ctx in this way, and working with +NGINX in general, is that it relies heavily on memory pools to store request +content. This largely removes any need for the programmer to have to think about +freeing memory after use- the pool is automatically allocated at the start of +a request, and is automatically freed when the request is done. All that’s +needed is to allocate the memory using NGINX’s built-in functions for allocating +memory to the pool and then registering a callback that will be called to free +everything. + +This should allow us to allocate memory for whatever we want, safe in the +knowledge that NGINX will handle it for us. + +It is regrettable that we have to write a lot of unsafe blocks when dealing +with NGINX’s interface in Rust. Although we’ve done a lot of work to minimise +them where possible, unfortunately this is often the case with writing Rust +code which has to manipulate C constructs through FFI. We have plans to do more +work on this in the future, and remove as many lines as possible from unsafe. +Challenges encountered + +The NGINX module system allows for a massive amount of flexibility in terms of +the way the module itself works, which makes it very accommodating to specific +use-cases, but that flexibility can also lead to problems. One that we ran into +had to do with the way the response data is handled between Rust and FL. In +NGINX, response bodies are chunked, and these chunks are then linked together +into a list. Additionally, there may be more than one of these linked lists per +response, if the response is large. + +Efficiently handling these chunks means processing them and passing them on as +quickly as possible. When writing a Rust module for manipulating responses, it’s +tempting to implement a Rust-based view into these linked lists. However, if you +do that, you must be sure to update both the Rust-based view and the underlying +NGINX data structures when mutating them, otherwise this can lead to serious +bugs where Rust becomes out of sync with NGINX. Here’s a small function from an +early version of ROFL that caused headaches: + +What this code was supposed to do is take the output of lol-html’s HTMLRewriter, +and write it to the output chain of buffers. Importantly, the output can be +larger than a single buffer, so you need to take new buffers off the chain +in a loop until you’ve written all the output to buffers. Within this logic, +NGINX is supposed to take care of popping the buffer off the free chain and +appending the new chunk to the output chain, which it does. However, if you’re +only thinking in terms of the way NGINX handles its view of the linked list, you +may not notice that Rust never changes which buffer its free_chain.head points +to, causing the logic to loop forever and the NGINX worker process to lock-up +completely. This sort of issue can take a long time to track down, especially +since we couldn’t reproduce it on our personal machines until we understood it +was related to the response body size. + +Getting a coredump to perform some analysis with gdb was also hard because once +we noticed it happening, it was already too late and the process memory had +grown to the point the server was in danger of falling over, and the memory +consumed was too large to be written to disk. Fortunately, this code never made +it to production. As ever, while Rust’s compiler can help you to catch a lot of +common mistakes, it can’t help as much if the data is being shared via FFI from +another environment, even without much direct use of unsafe, so extra care must +be taken in these cases, especially when NGINX allows the kind of flexibility +that might lead to a whole machine being taken out of service. + +Another major challenge we faced had to do with backpressure from incoming +response body chunks. In essence, if ROFL increased the size of the response +due to having to inject some large amount of code into the stream (such as +replacing an email address with a large chunk of JavaScript), NGINX can feed the +output from ROFL to the other downstream modules faster than they could push +it along, potentially leading to data being dropped and HTTP response bodies +being truncated if the EAGAIN error from the next module is left unhandled. This +was another case where the issue was really hard to test, because most of the +time the response would be flushed fast enough for backpressure never to be a +problem. To handle this, we had to create a special chain to store these chunks +called saved_in, which required a special method for appending to it. + +Effectively we’re ‘queueing’ the data for a short period of time so that we +don’t overwhelm the other modules by feeding them data faster than they can +handle it. The NGINX Developer Guide has a lot of great information, but many +of its examples are trivial to the point where issues like this don’t come +up. Things such as this are the result of working in a complex NGINX-based +environment, and need to be discovered independently. A future without NGINX + +The obvious question a lot of people might ask is: why are we still using NGINX? +As already mentioned, Cloudflare is well on its way to replacing components +that either used to run NGINX/OpenResty proxies, or would have done without +heavy investment in home-grown platforms. That said, some components are easier +to replace than others and FL, being where most of the logic for Cloudflare’s +application services runs, is definitely on the more challenging end of the +spectrum. + +Another motivating reason for doing this work is that whichever platform we +eventually migrate to, we’ll need to run the features that make up cf-html, and +in order to do that we’ll want to have a system that is less heavily integrated +and dependent on NGINX. ROFL has been specifically designed with the intention +of running it in multiple places, so it will be easy to move it to another +Rust-based web proxy (or indeed our Workers platform) without too much trouble. +That said it’s hard to imagine we’d be in the same place without a language +like Rust, which offers speed at the same time as a high degree of safety, not +to mention high-quality libraries like Bindgen and Serde. More broadly, the +FL team are working to migrate other aspects of the platform over to Rust, +and while cf-html and the features of which make it up are a key part of our +infrastructure that needed work, there are many others. + +Safety in programming languages is often seen as beneficial in terms of +preventing bugs, but as a company we’ve found that it also allows you to do +things which would be considered very hard, or otherwise impossible to do +safely. Whether it be providing a Wireshark-like filter language for writing +firewall rules, allowing millions of users to write arbitrary JavaScript +code and run it directly on our platform or rewriting HTML responses on the +fly, having strict boundaries in place allows us to provide services we +wouldn’t be able to otherwise, all while safe in the knowledge that the kind of +memory-safety issues that used to plague the industry are increasingly a thing +of the past. + + +\subsection*{Перевод статьи} + +В Cloudflare инженеры тратят много времени на рефакторинг или переписывание +существующей функциональности. Когда ваша компания удваивает объем трафика, +который она обрабатывает каждый год, то, что когда-то было элегантным решением +проблемы, может быстро может быстро устареть по мере изменения технических +ограничений. Мало того, когда вы обрабатываете в среднем 40 миллионов запросов в +секунду, проблемы, которые могут повлиять на 0,001\% запросов, проходящих через +нашу сеть, становятся крупными инцидентами, которые могут повлиять на миллионы +пользователей, а события один на триллион происходят несколько раз в день. + +Недавно мы работали над заменой одного из наших самых старых и наименее +известных компонентов под названием cf-html, который находится внутри ядра +обратного веб-прокси Cloudflare, известного как FL (Front Line). Cf-html --- +это фреймворк, отвечающий за разбор и переписывание HTML по мере того, как он +передается от сайта к посетителю сайта. С первых дней существования Cloudflare +мы предлагаем функции, которые будут переписывать тело ответа веб-запросов для +вас на лету. Первой функцией, которую мы написали таким образом, была замена +адресов электронной почты фрагментами JavaScript, которые затем загружали адрес +электронной почты при просмотре в веб-браузере. Поскольку боты часто не могут +оценить JavaScript, это помогает предотвратить поиск адресов электронной почты +с веб-сайтов. Вы можете увидеть это в действии, если просмотреть источник этой +страницы и найти этот адрес электронной почты: foo@example.com. + +FL - это место, где работает большая часть логики инфраструктуры приложений +Cloudflare, и в основном состоит из кода, написанного на скриптовом языке +Lua, который работает поверх NGINX как часть OpenResty. Для того чтобы +взаимодействовать с NGINX напрямую, некоторые части (например, cf-html) написаны +на языках более низкого уровня, таких как C и C++. В прошлом было много подобных +сервисов OpenResty в Cloudflare, но в наши дни FL - один из немногих оставшихся, +поскольку мы переводим другие компоненты на Workers или прокси-серверы на основе +Rust. Платформа, которая когда-то была наилучшим возможным сочетанием простоты и +скорости работы разработчиков, уже более чем начала показывать свой возраст. + +При обсуждении того, что происходит с HTTP-запросом, проходящим через нашу сеть +и в частности FL, почти все внимание уделяется тому, что происходит до тех пор, +пока пока запрос не достигнет клиентского источника. Это понятно, поскольку +именно здесь происходит большая часть бизнес-логики: правила брандмауэра, +Workers и решения по маршрутизации принимаются на этапе запроса. Но это еще +не конец истории. С инженерной точки зрения, большая часть интересной работы +происходит на этапе ответа, когда мы передаем HTML-ответ обратно от источника к +посетителю сайта. + +Логика для обработки этого содержится в статическом модуле NGINX и выполняется +на этапе фильтрации тела ответа в NGINX, поскольку фрагменты тела ответа HTTP +передаются в потоковом режиме. Со временем были добавлены дополнительные +функции, и система стала называться cf-html. cf-html использует потоковый парсер +HTML для поиска определенных HTML тегов и содержимого, называемый Lazy HTML +или lhtml, причем большая часть логики для него и функций cf-html написана с +использованием механизма машин состояния Ragel. + +Вся логика cf-html была написана на C, и поэтому была подвержена проблемам +повреждения памяти, которые характерны для многих больших кодовых баз на языке +Си. В 2017 году это привело к ошибке безопасности, когда команда пыталась +заменить часть cf-html. FL считывал произвольные данные из памяти и добавлял +их в тело ответа. Это могло потенциально включать данные из других запросов, +проходящих через FL в то же самое время. Это событие безопасности стало широко +известно как Cloudbleed. + +После этого эпизода Cloudflare внедрила ряд политик и мер безопасности для +того, чтобы подобное никогда не повторилось. Несмотря на то, что работа над над +cf-html велась на протяжении многих лет, было реализовано мало новых функций в +фреймворке, и теперь мы очень чувствительны к сбоям, происходящим в FL (и любом +другом процессе, запущенном в нашей сети), особенно в тех частях, которые могут +отражать данные обратно с ответом. + +Переходя к 2022-2023 годам, команда FL Platform получает все больше и больше +запросов к системе, которую они могли бы легко использовать для просмотра +и перезаписи данных тела ответа. В то же время другая команда работала над +новой системой разбора и перезаписи тела ответа для Workers под названием +lol-html или Low Output Latency HTML. lol-html не только быстрее и эффективнее, +чем Lazy HTML, но он также в настоящее время полностью используется в +производстве как часть интерфейса Worker и написан на языке Rust, который +намного безопаснее языка Си с точки зрения его обращения с памятью. Поэтому он +идеально подходит для замены древнего и скрипучего парсера HTML, который мы до +сих пор использовали в FL. + +Поэтому мы начали работать над новым фреймворком, написанным на Rust, который +бы включил lol-html и позволил другим командам писать функции разбора тела +ответа без угрозы возникновения серьезных проблем с безопасностью. Новая система +называется ROFL или Response Overseer for FL, и это совершенно новый модуль +NGINX, полностью написанный на языке Rust. На данный момент ROFL работает в +продакшене и обрабатывает миллионы ответов в секунду, с производительностью, +сравнимой с cf-html. При создании ROFL, мы смогли снять с эксплуатации один +из самых страшных кусков кода во всей кодовой базе, в то же время предоставив +командам Cloudflare надежную систему, которую они могут использовать для +написания функций, нуждающихся в разборе и переработке данных тела ответа. + +В процессе написания нового модуля мы многое узнали о том, как работает NGINX, +и как мы можем заставить его общаться с Rust. NGINX не предоставляет много +документации по написанию модулей, написанных на языках, отличных от C, и +поэтому нам пришлось проделать некоторую работу, чтобы понять, как написать +модуль NGINX на языке программирования выбранном нами. Начиная работу, мы +активно использовали части кода из проекта nginx-rs, особенно в части работы с +буферами и пулами памяти. Хотя написание полноценного модуля NGINX на Rust --- +долгий процесс и выходит за рамки этой статьи, есть несколько ключевых моментов, +которые делают все это возможным, и о которых стоит поговорить. + +Первый из них - это создание привязки Rust, чтобы NGINX мог взаимодействовать с +ним. Для этого мы использовали библиотеку Rust Bindgen для создания FFI привязки +для нас, основываясь на определениях символов в заголовочных файлах NGINX. +Чтобы добавить это в существующий проект Rust, первым делом нужно достать копию +NGINX и настроить его. В идеале это должно быть сделано в простом скрипте или +Makefile, но при выполнении вручную это будет выглядеть примерно так: + +Когда NGINX находится в нужном состоянии, нам нужно создать файл build.rs в +нашем проекте Rust для автоматической генерации привязок во время сборки модуля. +Теперь мы добавим необходимые аргументы в сборку и воспользуемся Bindgen для +генерации файла bindings.rs. Для аргументов нам просто нужно включить все +директории, которые могут содержать заголовочные файлы для работы clang. Затем +мы можем передать их в Bindgen вместе с некоторыми аргументами разрешающего +списка, чтобы он знал, для каких вещей он должен генерировать привязки, а какие +вещи он может игнорировать. Добавив немного шаблонного кода, весь файл должен +выглядеть примерно так: + +Надеюсь, все это достаточно понятно. Bindgen просматривает источник NGINX и +генерирует эквивалентные конструкции на языке Rust в файле bindings.rs, который +мы можем импортировать в наш проект. Есть только одна вещь, которую нужно +добавить - У Bindgen есть проблемы с парой символов в NGINX, которые нам нужно +будет исправить в файле под названием wrapper.h. + +Когда все готово, а Bindgen установлен в разделе [build-dependencies] файла +Cargo.toml, мы должны быть готовы к сборке. + +Если повезет, мы должны увидеть файл bindings.rs в каталоге target/debug/build +который содержит Rust определения всех символов NGINX. + +Чтобы иметь возможность использовать их в проекте, мы можем включить их в новый +файл в каталоге каталоге src, который мы назовем bindings.rs. + +Когда все готово, нам остается только добавить обычные импорты в верхнюю часть +файла lib.rs и мы можем получить доступ к конструкциям NGINX из Rust. Это не +только делает ошибки в интерфейсе между NGINX и нашим модулем Rust гораздо +менее вероятными, чем если бы эти значения были закодированы вручную, но это +также фантастическая справка, которую мы можем использовать для проверки +структуры в NGINX при создании модулей на Rust, и это снимает много работы +по конфигурированию. То что подобное можно сделать с минимальными усилиями и +надежным способом, свидетельствует о качестве многих библиотек Rust, таких как +Bindgen. + +После того, как библиотека Rust собрана, следующим шагом будет подключение ее +к NGINX. Большинство модулей NGINX компилируются статически. То есть, модуль +компилируется как часть NGINX в целом. Однако, начиная с версии NGINX 1.9.11, +поддерживаются динамические модули, которые компилируются отдельно и затем +загружаются с помощью директивы директивы load_module в файле nginx.conf. Это +то, что нам нужно было использовать для сборки ROFL, чтобы библиотека могла +быть скомпилирована отдельно и загружена во время запуска NGINX. Было непросто +найти такой правильный формат, чтобы необходимые символы можно было найти в +документации, и хотя можно использовать отдельный конфигурационный файл для +установки некоторых из этих метаданных, будет лучше, если мы можем загрузить их +как часть модуля, чтобы все было аккуратно. К счастью, для этого не нужно долго +копаться в кодовой базе NGINX, чтобы найти, где вызывается dlopen. + +При написании модуля NGINX очень важно, чтобы его порядок относительно других +модулей был правильным. Динамические модули загружаются при запуске NGINX, +что означает, что они (возможно, нелогично) запускаются первыми при получении +ответа. Обеспечить запуск вашего модуля после декомпрессии gzip, указав его +порядок относительно модуля gunzip очень важно. Иначе вы можете потратить много +времени, глядя на потоки непечатаемых символов, недоумевая, почему вы не видите +ответа, который вы ожидали. Это не весело. К счастью, эту проблему также можно +решить, если взглянуть на исходный код NGINX и убедиться, что соответствующие +сущности существуют в вашем модуле. + +По сути, мы хотим, чтобы наш модуль rust_nginx_module выполнялся непосредственно +перед модулем ngx_http_headers_more_filter_module, что должно позволить ему +запускаться в том месте, где мы ожидаем. + +Одна из причуд NGINX и OpenResty заключается в том, что они очень недружелюбно +относятся к вызову внешних сервисов в тот момент, когда вы обрабатываете HTTP +ответ. Это то, что не предусмотрено как часть OpenResty Lua фреймворка OpenResty +Lua, хотя это сделало бы работу с фазой ответа на запрос намного проще. Хотя мы +могли бы сделать это в любом случае, это означало бы необходимость создавать +форк NGINX и OpenResty, что принесло бы свои проблемы. В результате мы потратили +много времени, размышляя о том, как передать состояние пока NGINX работает с +HTTP-запросом, до того момента, когда он обрабатывает ответ, и большая часть +нашей логики построена вокруг этого стиля работы. + +Для ROFL это означает, что для того, чтобы определить, нужно ли нам применить +определенную функцию для ответа, мы должны выяснить это в запросе, а затем +передать эту информацию информацию в ответ, чтобы мы знали, какие функции +активировать. Для этого нам нужно воспользоваться одной из утилит, которые +предоставляет NGINX. С помощью файла bindings.rs, созданного ранее, мы можем +взглянуть на определение структуры ngx_http_request_s, которая содержит все +состояние связанное с данным запросом. + +Как мы видим, в ней есть член под названием ctx. Как говорится в руководстве по +разработке NGINX упоминается, это место, где вы можете хранить любое значение, +связанное с запросом, которое должно жить столько же, сколько и запрос. В +OpenResty это место активно используется для хранения состояния, связанного с +запросом, в течение его в контексте Lua. Мы можем сделать то же самое для нашего +модуля, чтобы настройки, инициализированные на этапе запроса, сохранялись, когда +наш HTML парсинг и переписывания в фазе ответа. + +Обратите внимание, что ctx находится по смещению члена ctx_index модуля +ngx_http_rofl_module --- это структура типа ngx_module_t, которая является +частью модуля определения, необходимого для создания модуля NGINX. Как только +мы получим эту структуру, мы можем указать ее на структуру, содержащую любой +параметр, который нам нужен. + +Здесь функция называется get_or_init_ctx, которая выполняет ту же работу, что и +функция get_ctx, но также инициализирует структуру, если она еще не существует. +Как только мы установили все необходимые данные в ctx во время запроса, мы можем +проверить, какие какие функции должны быть запущены в ответе, без необходимости +делать какие-либо вызовы к внешним базам данных, что может замедлить работу. + +Одна из приятных особенностей хранения состояния в ctx таким образом и работы +с NGINX в целом, является то, что он в значительной степени полагается на пулы +памяти для хранения содержимого запросов. Это в значительной степени устраняет +необходимость для программиста думать об освобождении памяти после использования +--- пул памяти автоматически выделяется в начале запроса и автоматически +освобождается, когда запрос завершен. Все, что необходимо сделать --- это +выделить память, используя встроенные функции NGINX для выделения памяти в пул, +а затем зарегистрировать обратный вызов, который будет вызван для освобождения +всего. + +Это позволит нам выделять память под все, что мы хотим, будучи уверенными в том, +что NGINX справится с этим зная, что NGINX сделает это за нас. + +К сожалению, нам приходится писать много unsafe блоков, когда мы имеем дело +с интерфейсом NGINX в Rust. Хотя мы проделали большую работу, чтобы свести к +минимуму их, где это возможно, к сожалению, это часто случается при написании +Rust кода, который должен манипулировать конструкциями языка C через FFI. У нас +есть планы сделать больше работы над этим в будущем, и убрать как можно больше +строк из небезопасного кода. + +Система модулей NGINX позволяет проявлять огромную гибкость в том, что касается +того, как работает сам модуль, что делает его очень приспособленным к конкретным +сценариям использования, но эта гибкость также может привести к проблемам. Одна +из них, с которой мы столкнулись связана с тем, как обрабатываются данные ответа +между Rust и FL. В NGINX, тела ответов разбиваются на фрагменты, и эти фрагменты +затем соединяются вместе в список. Кроме того, на один ответ может приходиться +более одного такого связанного списка, если ответ большой. + +Эффективная работа с этими кусками означает их обработку и передачу как +можно быстрее. При написании модуля на языке Rust для манипулирования +ответами, очень заманчиво реализовать представление на основе Rust в этих +связанных списках. Однако, если вы сделаете это, вы должны быть уверены, что +обновите и представление на основе Rust, и базовые структуры NGINX при их +изменении, иначе это может привести к серьезным ошибкам, когда Rust становится +рассинхронизированным с NGINX. Вот небольшая функция из ранней версии ROFL, +которая вызывала головную боль: + +Этот код должен был делать следующее: брать вывод HTMLRewriter'а lol-html, и +записывать его в выходную цепочку буферов. Важно отметить, что вывод может +быть больше, чем один буфер, поэтому вам нужно брать новые буферы из цепочки +в цикле, пока не будет записан весь вывод в буферы. В рамках этой логики, +NGINX должен позаботиться о том, чтобы выдернуть буфер из свободной цепочки и +добавляя новый чанк в цепочку вывода, что он и делает. Однако, если вы думаете +только о том, как NGINX обрабатывает свое представление связного списка, вы +можете не заметить, что Rust никогда не меняет буфер, на который указывает +его free_chain.head, что приводит к вечному циклу логики и полной блокировке +рабочего процесса NGINX. Отслеживание такого рода проблемы может занять много +времени, тем более, поскольку мы не могли воспроизвести ее на наших персональных +машинах, пока не поняли, что она связана с размером тела ответа. + +Получить coredump для проведения анализа с помощью gdb было также сложно, потому +что как только мы заметили, что это происходит, было уже слишком поздно, и +память процесса выросла до такой степени, что сервер был в опасности падения, а +потребляемая память была слишком велика для записи на диск. К счастью, этот код +так и не попал в производство. Как всегда, хотя компилятор Rust может помочь +вам отловить множество распространенных ошибок, он не так сильно поможет, если +данные передаются через FFI из другого окружения, даже без прямого использования +unsafe, поэтому в таких случаях нужно быть особенно внимательным, особенно когда +NGINX позволяет такую гибкость, что может привести к выводу из строя целой +машины. + +Еще одна серьезная проблема, с которой мы столкнулись, была связана с обратным +давлением от входящих кусков тела ответа. По сути, если ROFL увеличивал +размер ответа из-за необходимости внедрить в поток большое количество кода +(например, замена адреса электронной почты на большой кусок JavaScript), NGINX +может передать вывод от ROFL другим модулям, расположенным ниже, быстрее, чем +они могли бы продвигать это далее. Потенциально это может привести к тому, +что данные будут потеряны, а тела HTTP-ответов обрезаны, если ошибка EAGAIN +следующего модуля останется необработанной. Это был еще один случай, когда +проблему было очень трудно протестировать, потому что в большинстве случаев +ответ удалялся достаточно быстро, чтобы обратное давление никогда не было +проблемой. Чтобы справиться с этим, мы должны были создать специальную цепочку +для хранения этих фрагментов называемую saved_in, которая требует специального +метода для добавления к ней. + +Эффективно мы "ставим в очередь" данные на короткий промежуток времени, чтобы не +перегружать другие модули, подавая им данные быстрее, чем они могут обработать +их. Руководство разработчика NGINX содержит много замечательной информации, +но многие примеры в нем тривиальны настолько, что такие вопросы, как этот, не +возникают. Такие вещи, как эта, являются результатом работы в сложной среде на +базе NGINX и должны быть обнаружены самостоятельно. + +Многие могут задать очевидный вопрос: почему мы до сих пор используем NGINX? +Как уже упоминалось, Cloudflare уже на пути к замене компонентов, которые либо +использовали прокси-серверы NGINX/OpenResty, либо могли бы это сделать без +больших инвестиций в собственные платформы. Тем не менее, некоторые компоненты +заменить легче, чем другие, и FL, где работает большая часть логики для сервисов +Cloudflare приложений, определенно находится на более сложном конце спектра. + +Другой мотивирующей причиной для выполнения этой работы является то, что на +какую бы платформу мы в конечном итоге не перешли, нам нужно будет запускать +функции, составляющие cf-html, и для этого мы хотим иметь систему, которая +менее сильно интегрирована и зависима от NGINX. ROFL был специально разработан +с намерением чтобы его можно было запускать в разных местах, поэтому его будет +легко перенести на другой веб-прокси на базе Rust (или на нашу платформу +Workers) без особых проблем. Тем не менее, трудно представить, что мы были бы +на том же месте, если бы не было такого языка, как Rust, который предлагает +скорость и одновременно высокую степень безопасности, не говоря уже о таких +высококачественных библиотеках, как Bindgen и Serde. В более широком смысле, +команда FL работает над переносом других частей платформы на Rust, и хотя +cf-html и функции, из которых он состоит, являются ключевой частью нашей +инфраструктуры, над которой необходимо поработать, есть и многие другие. + +Безопасность в языках программирования часто рассматривается как благо с +точки зрения предотвращения ошибок, но как компания мы обнаружили, что +она также позволяет вам делать вещи, которые считались бы очень трудными +или вообще невозможными для выполнения безопасно. Будь то предоставление +Wireshark-подобного языка фильтрации для написания правил брандмауэра, позволяя +миллионам пользователей писать произвольный код на JavaScript и запускать его +непосредственно на нашей платформе или переписывать HTML-ответы "на лету". +Наличие строгих границ позволяет нам предоставлять услуги, которые мы не смогли +бы предоставить в противном случае, при этом мы можем быть уверены в том, что +такие проблемы с безопасностью памяти, от которых раньше страдала индустрия, все +больше уходят в прошлое. + + +\section{Перевод аннотации к статье} + +\subsection{Аннотация №1} + +\begin{center} + \bf Арушанян И.О. Применение метода граничных интегральных уравнений для численного решения задачи Дирихле в областях с угловыми точками // Вычислительные методы и программирование. 2000. Т.1. С. 1-7. +\end{center} + +Аннотация + +Задача Дирихле на области с угловыми точками сводится к граничному интегральному уравнению, для численного решения которого предлагается метод, обладающий экспоненциальной скоростью сходимости. Рассматривается способ вычисления нормальной производной решения указанной задачи. Приводятся оценки количества арифметических операций. + +Ключевые слова: задача Дирихле, области с угловыми точками, граничные интегральные уравнения, экспоненциальная скорость сходимости, метод квадратур, аппроксимация, системы линейных алгебраических уравнений, разрывы в угловых точках. + +\subsection{Перевод аннотации №1} + +\begin{center} +\bf Arushanyan I.O. Application of the method of boundary integral equations for numerical solution of the Dirichlet problem in regions with angular points // Computational Methods and Programming. 2000. VOL.1. P. 1-7. +\end{center} + +Abstract + +The Dirichlet problem on the domain with angle points is reduced to the boundary integral equation. This paper is proposing method for numerical solution that possesses exponential speed of convergence for this equation. A method for calculating the normal derivative of the solution of the above problem is considered. Estimates of the number of arithmetic operations are given. + +Keywords: Dirichlet problem, regions with corner points, boundary integral equations, exponential convergence rate, quadrature method, approximation, systems of linear algebraic equations, discontinuities in corner points. + +\subsection{Аннотация №2} + +\begin{center} + \bf +Титаренко В.Н., Ягола А.Г. Метод отсечения выпуклых многогранников и его применение к некорректным задачам // Вычислительные методы и программирование. 2000. Т.1. С. 8-13. +\end{center} + +Аннотация + +Рассматриваются линейные некорректные задачи на компактных множествах специальной структуры. Предлагаются два подхода для оценки погрешности приближенного решения, основанные на методе отсечения выпуклых многогранников. Строится область, которой принадлежит точное решение обратной задачи для уравнения теплопроводности. + +Ключевые слова: некорректная задача, оценка погрешности, метод отсечения выпуклых многогранников, уравнение теплопроводности. + +\subsection{Перевод аннотации №2} + +\begin{center} + \bf +Titarenko V.N., Yagola A.G. The method of cutting off convex polyhedrons and its application to incorrect problems // Computational Methods and Programming. 2000. VOL. 1, P. 8-13. +\end{center} + +Abstract + +We consider linear incorrect problems on compact sets of special structure. Two approaches for the estimation of the error of approximate solution based on the method of cutting off convex polyhedrons are proposed. The domain, which the exact solution of the inverse problem for the heat conduction equation belongs to, is constructed. + +Keywords: incorrect problem, error estimation, convex polyhedron cutoff method, heat conduction equation. + +\subsection{Аннотация №3} + +\begin{center} +\bf Антонов Т.Ю., Фрик П.Г., Соколов Д.Д. Рост корреляций в свободно распадающейся МГД турбулентности // Вычислительные методы и программирование. 2000. Т.1. С. 14-18. +\end{center} + +Аннотация + +С помощью каскадных моделей турбулентности исследовалась долговременная +эволюция магнитного поля и поля скорости в условиях магнитогидродинами ческой +турбулентности с различными типами начального состояния. Для каждого типа +моделировались 24 реализации процесса со случайным шумом в начальных условиях. +Вычисления производились на кластере НИВЦ МГУ, состоящем из 24 параллельных +процессоров. В большинстве случаев развивалось когерентное состояние с высоким +уровнем корреляции между магнитным полем и полем скорости, для которого +характерен низкий уровень диссипации энергии. В то же время несколько реализаций +вели себя по-другому, показывая низкий уровень перекрестной спиральности и, как +следствие, быстрое вырождение процесса. + +Ключевые слова: каскадные модели турбулентности, магнитогидродинамическая турбулентность, число Рейнольдса, диссипация энергии, математическое моделирование, параллельные процессоры. + +\subsection{Перевод аннотации №3} + +\begin{center} +\bf Antonov T.Y., Frik P.G., Sokolov D.D. Correlation growth in freely decaying MHD turbulence // Computational Methods and Programming. 2000. VOL. 1. P. 14-18. +\end{center} + +Abstract + +The long-term evolution of the magnetic field and velocity field under +magnetohydrodynamic turbulence conditions with different types of initial +states was investigated using cascade turbulence models. For each type, 24 +implementations of the process with random noise in the initial conditions +were simulated. The computations were performed on a cluster of the NRWC of +Moscow State University consisting of 24 parallel processors. In most cases, a +coherent state with a high level of correlation between the magnetic field and +the velocity field developed, which is characterized by a low level of energy +dissipation. At the same time, a few realizations behaved differently, showing +a low level of cross-helixity and, as a consequence, rapid degeneracy of the +process. + +Keywords: cascade turbulence models, magnetohydrodynamic turbulence, Reynolds number, energy dissipation, mathematical simulation, parallel processors. + +\subsection{Аннотация №4} + +\begin{center} +\bf Зяббарова А.А. Дифференциальная рента как основная форма рентного дохода в современной экономике // Экономические науки. 2007. 1(26). С. 172-174. +\end{center} + +Аннотация + +Предложена авторская классификация форм и видов ренты, в основу которой положено +отношение форм рентного дохода и этапов процесса ресурсопользования. Таким +образом, предложенная классификация является наиболее эффективной как с точки +зрения изучения природы, причин формирования рентного дохода и построения +системы управления рентным доходом, так и с точки зрения возможностей переноса +понятий из смежных теорий. Один из наиболее сложных моментов при построении +данной классификации заключался в формализации понятий “чистая рента” и +“квазирента”. + +\subsection{Перевод аннотации №4} + +\begin{center} +\bf Ziabbarova A.A. Differential rent as the main form of rent income in the modern economy // Economic Sciences. 2007. 1(26). P. 172-174. +\end{center} + +Abstract + +The author's classification of the forms and kinds of rent, which is based on +the relation between the forms of rent incomes and the stages of the process +of resource use, is offered. Thus, the offered classification is the most +effective both from the point of view of studying the nature and reasons of +formation of the rent incomes and construction of the rent incomes management +system, and from the point of view of possibilities to transfer concepts from +the adjacent theories. One of the most difficult moments in the construction +of this classification was the formalization of the concepts of "net rent" and +"quasi-rent". + + +\subsection{Аннотация №5} + +\begin{center} +\bf Galby E. The complexity of blocking (semi)total dominating sets with edge contractions // Theoretical Computer Science. 2023. Vol. 950, #113678. https://doi.org/10.1016/j.tcs.2022.12.028. +\end{center} + +Abstract + +We consider the problem of reducing the (semi)total domination number of a graph +by one by contracting edges. It is known that this can always be done with at +most three edge contractions and that deciding whether one edge contraction +suffices is an NP-hard problem. We show that for every fixed $k \in \{2,3\}$, +deciding whether exactly k edge contractions are necessary is NP-hard and +further provide for k=2 complete complexity dichotomies on monogenic graph +classes. + +Keywords: Total domination number; Semitotal domination number; Edge contraction; Blocker problem; H-free graphs + +\subsection{Перевод аннотации №5} + +\begin{center} +\bf Гэлби Э. Сложность блокирования (полу)полных доминирующих множеств с сужениями краев // Теоретическая информатика. 2023. Т. 950, #113678. https://doi.org/10.1016/j.tcs.2022.12.028. +\end{center} + +Аннотация + +Мы рассматриваем проблему уменьшения числа (полу)полного доминирования графа +на единицу путем сокращения ребер. Известно, что это всегда можно сделать не +более чем тремя сокращениями ребер и что решение вопроса о том, достаточно ли +одного сокращения ребра, является NP-трудной задачей. Мы показываем, что для +каждого фиксированного $k \in \{2,3\}$ решение вопроса о необходимости ровно +k сокращений ребер является NP-трудной задачей, и далее приводим k=2 полные +дихотомии сложности для классов моногенных графов. + +Ключевые слова: Полное число доминирования; Полутотальное число доминирования; Сжатие ребер; Проблема блокировщика; H-свободные графы + +\subsection{Аннотация №6} + +\begin{center} +\bf Chang Y.-J., Studený J., Suomela J. Distributed graph problems through an automata-theoretic lens // Theoretical Computer Science. 2023. Vol. 951. #113710. +https://doi.org/10.1016/j.tcs.2023.113710. +\end{center} + +Abstract + +The locality of a graph problem is the smallest distance T such that each node +can choose its own part of the solution based on its radius-T neighborhood. In +many settings, a graph problem can be solved efficiently with a distributed +or parallel algorithm if and only if it has a small locality. In this work we +seek to automate the study of solvability and locality: given the description +of a graph problem Π, we would like to determine if Π is solvable and what +is the asymptotic locality of Π as a function of the size of the graph. Put +otherwise, we seek to automatically synthesize efficient distributed and +parallel algorithms for solving Π. We focus on locally checkable graph problems; +these are problems in which a solution is globally feasible if it looks feasible +in all constant-radius neighborhoods. Prior work on such problems has brought +primarily bad news: questions related to locality are undecidable in general, +and even if we focus on the case of labeled paths and cycles, determining +locality is PSPACE-hard (Balliu et al., PODC 2019). We complement prior negative +results with efficient algorithms for the cases of unlabeled paths and cycles +and, as an extension, for rooted trees. We study locally checkable graph +problems from an automata-theoretic perspective by representing a locally +checkable problem Π as a nondeterministic finite automaton M over a unary +alphabet. We identify polynomial-time-computable properties of the automaton M +that near-completely capture the solvability and locality of Π in cycles and +paths, with the exception of one specific case that is co-NP-complete. + +Keywords: Distributed algorithms; Computational complexity; Algorithm synthesis; Automata theory; LOCAL model; LCL problems + +\subsection{Перевод аннотации №6} + +\begin{center} +\bf Chang Y.-J., Studený J., Suomela J. Распределённые графовые задачи с точки зрения теории автоматов // Теоретическая информатика. 2023. Т. 951. #113710. +https://doi.org/10.1016/j.tcs.2023.113710. + +\end{center} + +Аннотация + +Локальность графовой задачи - это наименьшее расстояние T, такое, что каждый +узел может выбрать свою часть решения на основе своей окрестности радиуса-T. +Во многих случаях графовая задача может быть эффективно решена с помощью +распределенного или параллельного алгоритма тогда и только тогда, когда +она имеет малую локальность. В данной работе мы стремимся автоматизировать +исследование разрешимости и локальности: учитывая описание графовой задачи Π, +мы хотели бы определить, разрешима ли Π и какова асимптотическая локальность +Π как функция размера графа. Говоря иначе, мы стремимся автоматически +синтезировать эффективные распределенные и параллельные алгоритмы для решения +Π. Мы фокусируемся на локально проверяемых проблемах графов; это проблемы, +в которых решение глобально выполнимо, если оно выглядит выполнимым во всех +окрестностях постоянного радиуса. Предыдущие работы по таким проблемам принесли +в основном плохие новости: вопросы, связанные с локальностью, неразрешимы в +общем случае, и даже если мы сосредоточимся на случае маркированных путей и +циклов, определение локальности является PSPACE-трудным (Balliu et al., PODC +2019). Мы дополняем предыдущие отрицательные результаты эффективными алгоритмами +для случаев немаркированных путей и циклов и, в качестве расширения, для +деревьев с корнями. Мы изучаем локально проверяемые проблемы графов с точки +зрения теории автоматов, представляя локально проверяемую проблему Π в виде +недетерминированного конечного автомата M над унарным алфавитом. Мы определяем +вычислимые за полиномиальное время свойства автомата M, которые почти полностью +отражают разрешимость и локальность Π в циклах и путях, за исключением одного +конкретного случая, который является co-NP-полным. + +Ключевые слова: Распределенные алгоритмы; вычислительная сложность; синтез алгоритмов; теория автоматов; модель LOCAL; задачи LCL + + +\section{Редактирование машинного перевода} + +\subsection*{Текст оригинала} + +\begin{center} + \bf + «„Искусственный интеллект“ — это просто новостной хайповый термин» +\end{center} + +«„Искусственный интеллект“ — это просто новостной хайповый термин». Интервью +с Алексеем Тихоновым, специалистом по машинному обучению, о силе и слабости +современных нейросетей. + +Мясные машины ака живые люди морально устаревают не по дням, а по часам, зато +нейросети растут как грибы после дождя. Журнал «Нож» привык держать руку на +пульсе, поэтому мы решили провести смотр войск и выяснить, на что уже способны +искусственные нейроны и чему научатся в ближайшее время. За разъяснениями +мы обратились к специалисту по машинному обучению Алексею Тихонову, а он +рассказал нам о генерации киберпараноидального бреда, о сходстве нейросетей с +попугайчиками, о том, что искусственного интеллекта не существует, а также о +других любопытных вещах и феноменах. + +— Недавно в нью-йоркском издательстве Dead Alive вышла книга Paranoid +Transformer — дневник параноика, сгенерированный вами при помощи нейросетей. +Расскажите, пожалуйста, подробнее об этом проекте. + +— Есть такое ежегодное мероприятие NaNoGenMo, оно проводится уже много лет +подряд каждый ноябрь и привлекает людей из разных стран: они собираются онлайн +и в формате скорее коллаборации и обсуждения, чем соревнования, придумывают и +проверяют разные идеи и гипотезы по немодерируемой генерации и обработке текста. +Никакого утилитаризма в этом нет: грубо говоря, если вам нужны стихи, то проще +нанять поэта — выйдет дешевле и качественнее, чем генерировать нейросетью. + +Я давно собирался принять в этом мероприятии участие и в 2019 году наконец +нашел время. После того как NaNoGenMo закончился, ко мне обратились ребята, +которые, судя по всему, тоже в нем когда-то участвовали, а потом сделали журнал, +где публикуют всякие странные проекты, связанные с генерацией поэтических +и прозаических литературных текстов — надо понимать, что это очень нишевая +штука. Так вот, им понравился мой проект, и они предложили принять участие +в их конкурсе. Я подумал, что скучно два раза подавать одно и тоже, и решил +что-нибудь доделать в этом проекте: добавил нейросеть, рисующую на полях +картинки-каракули, а сам текст представил как «написанный от руки» с помощью еще +одной нейросети, причем дрожание почерка сделал зависимым от эмоциональности +записываемого текста. После того как я выиграл конкурс, мне предложили издать +текст в виде книги. + +— А на каких корпусах текстов вы обучали нейросети и как вообще осуществляется +их обучение? + +— Весь проект англоязычный, как и конкурс. Что касается обучения, сформулирую +так: есть современная парадигма в обучении нейросетей, которая называется +Transfer learning. В случае с текстами этот подход подразумевает использование +большого корпуса текстов для обучения базовой модели («большой» — это +максимально большой, условно говоря, «весь доступный интернет» или «вся +„Википедия“»). В результате эта предобученная модель получает информацию о +том, как вообще устроены человеческие тексты. Она может выучить морфологию, +синтаксис, пунктуацию, общие знания и т. д. А затем берется какая-то +относительно небольшая пачка данных под конкретную задачу, и на ней происходит +донастройка сети. + +Схожим образом, например, делался проект «Нейронная оборона»: не написал, к +сожалению, ни Егор Летов, ни даже Пушкин, столько текстов, чтобы на них можно +было с нуля обучить нейросеть. Когда объема текстов недостаточно, сеть может эти +тексты только вызубрить наизусть, но не научиться самостоятельно генерировать +похожие. + +В этом случае можно на большом универсальном корпусе один раз обучить базовую +языковую модель, а дальше она уже будет использоваться как основа для обучения +в разных задачах: желающие могут ее брать и с помощью относительно небольших +корпусов производить доучивание под конкретную ситуацию, например для генерации +текста в заданной стилистике. В процессе этой донастройки сеть предположительно +должна схватить суть того, что от нее требуется в данном конкретном случае, +какая задача перед ней ставится, и по факту она справляется с этим гораздо +лучше, чем непредобученная сеть. + +В проекте Paranoid Transformer было ровно это использовано: взята предобученная +сеть GPT (доступная для всех) и относительно небольшой корпус текстов, +состоящий из афоризмов, киберпанковских, шифропанковских и разных атмосферных +в определенном смысле текстов. Я специально настроил сеть на то, чтобы она, с +одной стороны, писала немного киберпанковские по тематике тексты, а с другой — +чтобы форма их была ближе к афоризмам или коротким высказываниям. В результате +получился поток каких-то странных мыслей, что достаточно хорошо вписывалось в +концепцию дневника. + +— Правильно ли я понимаю, что научить нейросеть писать «в стиле Льва Толстого», +например, проще, чем «в стиле Фонвизина», просто потому что Толстой написал +девяносто томов, а Фонвизин два? + +— Наверное, в каком-то смысле это могло бы быть правдой. Когда мы говорим о +постановке задачи «научить сеть писать что-то в стиле кого-то», речь же в +конечном счете идет о математической задаче. Нам нужно сначала четко определить, +что такое «стиль» и что такое «писать в стиле», а это не всегда очевидно. +Пока мы этого не сделаем, довольно сложно объективно оценить, кто у нас лучше +получается — Толстой или Фонвизин. Без такой детализации вопроса довольно сложно +на него ответить, потому что может оказаться, что, несмотря на то, что некий +автор написал гораздо больше текстов — то есть оставил нам большее количество +информации о своем стиле, — сам стиль у него в каком-то смысле более сложный, +и поэтому нужно еще больше текстов. То есть пока этот вопрос не приземлен на +какую-то количественную конкретику, он остается открытым. Но исходя из общих +соображений, общей логики, наверное, да: чем больше текстов — тем проще. + +— Что нейросеть схватывает в первую очередь во время обучения — морфологию? + +— Когда мы говорим про обучение сетей, это всегда компромисс между тем, как мы +об этом думаем, и тем, что на самом деле происходит. По правде говоря, в области +машинного обучения достаточно давно наступила эпоха, когда обучение не является +в чистом виде интерпретируемым. Модели учатся и дают хороший результат, а как +именно это происходит, в какой последовательности оно там, внутри, усваивается, +мы часто можем лишь гадать и оценивать по каким-то косвенным признакам, и, +кажется, это всегда будет некоторой спекуляцией. + +Подобно тому, как вы будете попугайчика учить разговаривать, и однажды +он заговорит, но определить, в какой момент он усвоил слова, в какой +последовательности и насколько он их понимает, довольно сложно. +Это отдельная наука — попытаться придумать, как понять, что происходит внутри +сложной нейросетевой модели, когда она обучается. Например, современные +английские модели типа GPT-3 читают при обучении сотни гигабайт текста. Это +гораздо больше, чем любой из нас прочитает за всю свою жизнь, но при этом +такая сеть ничего, кроме текстов, не изучает, не взаимодействует с миром и не +связывает слова с окружающими явлениями. Она лишь пытается, например, в каждый +момент предсказать следующее слово текста и, предсказывая неверно, учится на +своих ошибках. + +\subsection{Отредактированный машинный перевод} + +\begin{center} + \bf +"Artificial Intelligence is just a word hyped up by news" +\end{center} + +"'Artificial Intelligence' is just a word hyped up by news". Interview with +Alexey Tikhonov, a machine learning specialist, about the strengths and +weaknesses of modern neural networks. + +Meat machines aka living people are becoming obsolete by leaps and bounds, but +neural networks are growing like mushrooms after the rain. The Knife magazine is +used to keeping its finger on the pulse, so we decided to review the troops and +find out what artificial neurons are already capable of and what they will learn +in the near future. We turned to machine learning specialist Alexey Tikhonov +for clarification, and he told us about the generation of cyber-paranoid +delirium, about the similarity of neural networks with parrots, that artificial +intelligence does not exist, as well as about other curious things. + +— Recently, the New York publishing house "Dead Alive" published the book +"Paranoid Transformer" - the diary of a paranoid, generated by you with the help +of neural networks. Please tell us more about this project. + +— There is such an annual event NaNoGenMo, it has been held for many years +in a row every November and attracts people from different countries: they +gather online and in the format of collaboration and discussion rather than +competition, invent and test different ideas and hypotheses on unmoderated +generation and text processing. There is no utilitarianism in this: roughly +speaking, if you need poems, it is easier to hire a poet — it will be cheaper +and better than generating a neural network. + +I have been planning to take part in this event for a long time and in 2019 I +finally found the time. After NaNoGenMo ended, I was approached by guys who, +apparently, also participated in it once, and then made a magazine where they +publish all sorts of strange projects related to the generation of poetic and +prose literary texts - you have to understand that this is a very niche thing. +They liked my project, and offered to take part in their competition. I thought +it was boring to submit same thing twice, and decided to improve this project: I +added a neural network that is drawing doodles on the margins, and presented the +text itself as "handwritten" with the help of another neural network, and made +the trembling of the handwriting dependent on the emotionality of the written +text. After I won the contest, I was offered to publish the text in the form of +a book. + +— And on which corpus of texts did you train neural networks and how is their +training carried out in general? + +— The whole project is in English, as is the competition. As for training, I'll +say this way: there is a modern paradigm in training neural networks, which is +called Transfer learning. In the case of texts, this approach implies the use of +a large corpus of texts for teaching the basic model ("large" is the largest, +relatively speaking, "all available Internet" or "all Wikipedia"). As a result, +this pre-trained model receives information about how human texts are arranged +in general. It can learn morphology, syntax, punctuation, general knowledge, +etc. And then some relatively small bundle of data is taken for a specific task, +and the network is fine-tuned on it. + +In a similar way, for example, the Neural Defense project was done: +unfortunately, neither Egor Letov nor even Pushkin wrote so many texts that they +could be used to train a neural network from scratch. When the volume of texts +is not enough, the network can only memorize these texts by heart, but not learn +how to generate similar ones on its own. + +In this case, it is possible to train the basic language model once on a large +universal corpus, and then it will already be used as a basis for learning other +tasks: someone can take it and use relatively small corpus to complete training +for a specific situation. For example, to generate text in a given style. In the +process of this adjustment, the network is presumed to grasp the essence of what +is required of it in this particular case, understand the given task. And in +fact it handles tasks much better than an untrained network. + +In the Paranoid Transformer project, exactly this was used: a pre-trained +GPT network (accessible to everyone) and a relatively small corpus of texts +consisting of aphorisms, cyberpunk, cipherpunk and various texts with a certain +atmosphere were taken. I have specifically set up the network so that, on the +one hand, it writes a little cyberpunk texts on the subject, and on the other — +so that their form is closer to aphorisms or short statements. The result was a +stream of some strange thoughts, which fit well enough into the concept of the +diary. + +— Do I understand correctly that it is easier to teach a neural network to write +"in the style of Leo Tolstoy", for example, than "in the style of Fonvizin", +simply because Tolstoy wrote ninety volumes, and Fonvizin two? + +— Probably, in some sense it could be true. When we talk about setting the +task "to teach the network to write something in the style of someone", we are +ultimately talking about a mathematical problem. We need to first clearly define +what is "style" and what is "writing in style", and this is not always obvious. +Until we do this, it is quite difficult to objectively assess who we do better +— Tolstoy or Fonvizin. Without details, it is quite difficult to answer such +question. It may turn out that, despite the fact that a certain author wrote +much more texts — that is, he left us more information about his style — his +style itself is in some sense more complex, and therefore even more texts are +needed. That is, as long as this question is not grounded on some quantitative +specifics, it remains open. But based on general considerations and general +logic, probably yes: the more texts — the easier. + +— What does the neural network grasp first of all during training — morphology? + +— When we talk about training of networks, it's always a compromise between +how we think about it and what actually happens. To tell the truth, for quite +a while in the field of machine learning the learning itself is not purely +interpretable. Models learn and give a good result, and how exactly this +happens, in what sequence it is internalized there, inside, we can often only +guess and evaluate by some indirect signs, and it seems that there will always +be some speculation. + +You can teach a parrot to talk, and one day he will speak, but it is quite +difficult to determine at what point he learned the words, in what sequence and +how much he understands them. It is a separate science to try to figure out how +to understand what is happening inside a complex neural network model when it is +being trained. For example, modern English models like GPT-3 read hundreds of +gigabytes of text during training. This is much more than any of us will read in +our entire lives, but at the same time, such a network does not study anything +except texts, does not interact with the world and does not connect words with +surrounding phenomena. It only tries, for example, to predict the next word of +the text at every moment and, predicting incorrectly, learns from its mistakes. + + +% \bibliographystyle{gost780uv} +% \inputencoding{cp1251} +% \bibliography{sources} +% \inputencoding{utf8} + +\end{document} |